Java版-数据结构-链表

原创
顾立剑
数据结构
0 ℃

####概要

之前我们分别学习了解了动态数组、栈、队列，其实他们的底层都是依托静态数组来实现的、只是通过我们定义的resize方法来动态扩容解决固定容量的问题，那么我们即将学习的链表，它其实是一种真正的动态数据结构。

介绍

链表是一种最简单的动态数据结构，它能够辅助组成其它的数据结构，链表中的元素可存储在内存中的任何地方（不需要连续的内存，这一点和我们的数组具有很大的区别，数组需要连续的内存），链表中的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串接在一起。

存储链表的数据的我们一般称为节点（Node），节点一般分为两部分，一部分存储我们真正的数据，而另外一部分存储的是下一个节点的引用地址。

1
2
3
4
class Node{
    private E e; // 存储的真正元素
    private Node next;  // 存储下一个node的引用地址(指向下一个node)
}

比如现在我们将元素A、B、C三个节点添加到链表中，示意图如下：

image-20190327213801994

从图中节点A到节点B之间的箭头代表，节点A指向了节点B（NodeA.next = NodeB），因为在实际业务中我们的链表长度不可能是无穷无尽的，基本上都是有限个节点，通常定义链表中的最后一个元素它的next存储的是NULL（空），换句话说，如果在链表中，一个节点的next是空（NULL）的话，那么它一定是最后一个节点（对应我们图中的C节点）。

根据我们上面介绍的链表基本结构，下面我们用代码定义一下链表的基本骨架（这里我们引入了一个虚拟的头结点，下面我们会作说明）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class LinkedList<E> {
    /**
     * 虚拟的头结点
     */
    private Node dummyHead;
    /**
     * 链表中节点的个数
     */
    private int size;

    public LinkedList() {
        // 创建一个虚拟的头结点
        dummyHead = new Node();
    }


    // 节点定义
    private class Node {
        // 存储节点的元素
        public E e;
        // 存储下一个节点的地址
        public Node next;

        public Node() {

        }

        public Node(E e) {
            this.e = e;
        }

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", next=" + next +
                    '}';
        }
    }
}

后面我们对链表的添加节点、删除节点以及查询节点，代码实现都会基于这个基本骨架

向链表中添加节点

思路分析：

一般我们向链表中添加节点，基本思路：找到添加节点位置的前一个节点preNode，然后再改变链表的地址引用；由于链表的第一个节点也就是头结点没有前节点，此时我们为了操作方便，为链表新增了不存储任何元素的一个虚拟的头结点dummyHead（不是必须的，对用户来讲是不可见的），其实链表中真正的第一个节点是节点A（dummyHead.next），这样我们就能保证了，链表中存储元素的节点都有前一个节点。

image-20190328144225867

下面我们来看一下，如果现在有一个节点D，我们准备把它插入到节点B的位置，我们需要做哪些操作

第一步：我们首先要找到节点B的前一个节点，也就是节点A

第二步：将新节点D的指向指到节点B（NodeD.next = NodeA.next），然后再将节点A的指向，指到节点D（NodeA.next = NodeD），这样我们的节点就能串接起来了

image-20190330090951086

代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
  * 向链表中指定位置插入节点（学习使用，真正插入不会指定索引）
  *
  * @param index 索引的位置
  * @param e 节点元素
  */
public void add(int index, E e) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }

    Node prev = dummyHead;

    // 找到index位置的前一个节点
    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }

    // 新建一个节点，进行挂接
    Node node = new Node(e);
    node.next = prev.next;
    prev.next = node;

    size++;
}

链表的遍历

进行链表遍历，我们需要从链表中真正的第一个元素开始，也就是dummyHead.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
  * 获取链表中index位置的元素
  *
  * @param index  索引的位置
  * @return  节点的元素
  */
public E get(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    return cur.e;
}

修改链表中元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
  * 修改链表中index位置节点的元素
  *
  * @param index 索引的位置
  * @param e 节点的元素
  */
public void set(int index, E e) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    cur.e = e;
}

查找链表中是否包含某元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
  * 查找链表中是否包含元素e
  *
  * @param e
  * @return
  */
public boolean contains(E e) {
    Node cur = dummyHead.next;
    while (cur != null) {
        if (cur.e.equals(e)) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

删除链表中的元素

image-20190330093907204

在链表中删除元素，与在链表中添加元素有点类似

第一步：我们首先找到删除节点位置的前一个节点，我们用prev表示，被删除的节点我们用delNode表示

第二步：改变链表的引用地址：prev.next = delNode.next（等同于，将节点在链表中删除）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
  * 删除链表中index位置的节点
  *
  * @param index
  */
public void remove(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }

    Node prev = dummyHead;

    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }

    Node delNode = prev.next;
    prev.next = delNode.next;
    delNode.next = null;
    size--;
}

完整版代码GitHub仓库地址：Java版数据结构-链表 欢迎大家【关注】和【Star】

至此笔者已经为大家带来了数据结构：静态数组、动态数组、栈、数组队列、循环队列、链表；接下来，笔者还会一一的实现其它常见的数组结构，大家一起加油!

  • 静态数组
  • 动态数组
  • 栈
  • 数组队列
  • 循环队列
  • 链表
  • 循环链表
  • 二分搜索树
  • 优先队列
  • 堆
  • 线段树
  • 字典树
  • AVL
  • 红黑树
  • 哈希表
  • ….

持续更新中，欢迎大家关注公众号：小白程序之路（whiteontheroad），第一时间获取最新信息！！！


小白程序之路

数据结构