链表

定义

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续

分类

  • 单向链表：每个元素只知道下一个元素是谁
  • 双向链表：每个元素知道其上一个元素和下一个元素
  • 循环链表：通常的链表尾节点tail指向的都是null，而循环链表的尾tail指向的是头节点head

*链表内还有一种特殊的节点称为哨兵(Sentinel)节点，也叫做哑元(Dummy)节点，，它不存储数据，通常用作头尾，用来简化边界判断

性能

随机访问：
根据index查找，时间复杂度O(n)，数据越多随机访问性能越差

插入和删除：
·起始位置：O(1),和链表数据规模无关
·结束位置：如果已知tail尾节点是O(1),不知道tail尾节点是O(n)
·中间位置：根据index查找时间+O(1)

单向链表

构建单向链表类

这里要注意的是这个类的创建过程，有单链表类内部还有节点类

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
public class SinglyLinkedList implements Iterable<Integer> { // 整体
    private Node head = null;// 头指针

    //重写迭代器,实际上重写了增强for内部的方法
    @Override
    public Iterator<Integer> iterator() {
        //匿名内部类
        return new Iterator<Integer>() {
            Node p = head;

            @Override
            public boolean hasNext() {// 是否有下一个元素
                return p != null;
            }

            @Override
            public Integer next() { //返回当前值，并指向下一个元素
                //得到当前元素的值
                int v = p.value;
                //指向下一个元素
                p = p.next;
                //返回当前元素值
                return v;
            }
        };
    }

    /**
     * 节点类
     * 像这种类与类组合的方式一般都要考虑是否可以成为内部类，减少类的暴露
     * 什么时候加static？
     * 当匿名内部类中没有使用外部类的成员变量时就可以使用static，反之则不行。static随着类的加载而加载
     */
    private static class Node {
        int value;// 值
        Node next;//下一个节点指针

        //有参构造
        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

常见的单链表方法

有熟悉的增删改查方法，底层原理在代码中写的比较详细了

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

/**
 * 向链表头部添加链表元素(头插)
 *
 * @param value-待添加的值
 */
public void addFirst(int value) {
    //1、链表为空
    //head = new Node(value,null);
    //2、链表非空,下面这行包含了链表为空和不为空的情况，因为head一开始就是null，赋值为null
    head = new Node(value, head);
}

/**
 * 遍历链表(while版)
 *
 * @param consumer-由调用者决定该方法的作用，用accept方法实现
 */
public void loop1(Consumer<Integer> consumer) {
    Node p = head;
    while (p != null) {
        consumer.accept(p.value);
        //上面处理完当前节点值之后，将p地址赋值为下一个节点的地址
        p = p.next;
    }
}

/**
 * 遍历链表(for版)
 *
 * @param consumer-由调用者决定该方法的作用，用accept方法实现
 */
public void loop2(Consumer<Integer> consumer) {
    for (Node p = head; p != null; p = p.next) {
        consumer.accept(p.value);
    }
}

/**
 * 查找链表中的最后一个元素
 * @return
 */
private Node findLast() {
    if(head == null){//空链表情况
        return null;
    }
    Node p;
    for (p = head; p.next != null; p = p.next) {

    }
    return p;
}

/**
 * 向链表尾部添加
 * @param value-待添加值
 */
public void addLast(int value){
    Node last = findLast();
    if(last == null){
        addFirst(value);
        return;
    }
    last.next = new Node(value,null);
}

/*public void test(){
    int i = 0;
    for(Node p = head; p.next != null; p = p.next, i++){//第三个部分可以有多行操作(Java语法)
        System.out.println(p.value + "索引是" + i);
    }
}*/

/**
 * 查找节点
 * @param index
 * @return
 */
private Node findNode(int index){
    int i = 0;
    for(Node p = head; p != null; p = p.next, i++){//第三个部分可以有多行操作(Java语法)
        if(i == index){
            return p;
        }
    }
    return null;//没找到
}

/**
 * 根据索引查找
 * @param index-索引
 * @return 找到，返回该索引位置节点的值
 * @throws IllegalArgumentException-找不到，抛出index非法异常
 */
public int get(int index){
    Node node = findNode(index);
    if(node == null){
        throw illegalIndex(index);
    }
    return node.value;
}

/**
 * 抽取出来的异常类
 * @param index
 * @return
 */
private static IllegalArgumentException illegalIndex(int index) {
    return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
}

/**
 * 向索引位置插入
 * @param index-索引
 * @param value-待插入值
 * @throws IllegalArgumentException-找不到，抛出index非法异常
 */
public void insert(int index, int value){
    if(index == 0){
        addFirst(value);
        return;
    }
    //直接调用上面写好的方法查询要插入位置的上一个节点
    Node prev = findNode(index - 1);//找到下一个节点
    if(prev == null){
        throw illegalIndex(index);
    }
    //新添加的下一个节点地址就是先前的下一个节点地址
    //新添加前面的节点的下一个节点地址要改为新添加的节点地址
    prev.next = new Node(value, prev.next);//太优雅了！！！
}

/**
 * 删除第一个节点
 */
public void removeFirst(){
    if(head == null){
        throw illegalIndex(0);
    }
    //将把第二个节点当作第一个节点
    head = head.next;
}

/**
 * 从索引位置删除
 * @param index-索引
 * @throws IllegalArgumentException-找不到，抛出index非法异常
 */
public void removeByIndex(int index){
    if(index == 0){
        removeFirst();
        return;
    }
    Node prev = findNode(index - 1);//上一个节点
    if(prev == null){
        throw illegalIndex(index);
    }
    //获取当前要删除的节点对象
    Node removed = prev.next;
    if(removed == null){
        throw illegalIndex(index);
    }
    //将前一个节点的下一个指针指向删除节点的下一个指针
    prev.next = removed.next;
}

带哨兵的单向链表

个人理解哨兵:哨兵节点实际上就是省去了考虑大量的边界问题，一开始链表就存在一个哨兵节点，占着索引0的位置，但我们书写代码的时候可以把哨兵的索引写成-1这样其它的代码都可以不需要改变。哨兵节点是只读，不可操作的隐藏节点，设计非常巧妙，省去了很多在头部的判断情况,充分的简化了代码。
*需要注意遍历的时候起始遍历点是哨兵.next 这样就可以正常遍历。

双向链表(带哨兵)

和单向链表大差不差，多了一个往前指的指针，好处在于在尾部可以直接根据尾哨兵从尾遍历

构建双向链表类

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
46
47
48
49
50
/**
 * 双向链表
 */
public class DoublyLinkedListSentinel implements Iterable<Integer>{
    //重写迭代器
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            //设置起始位置
            Node p = head.next;
            @Override
            public boolean hasNext() { // 是否有下一个元素
                //当节点地址不等于尾哨兵的时候就继续遍历
                return p != tail;
            }

            @Override
            public Integer next() { //返回当前值，并指向下一个元素
                Integer value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    static class Node {
        Node prev;//上一个节点指针
        Integer value;//值
        Node next;//下一个节点指针

        public Node(Node prev, Integer value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    //双向链表加入两个哨兵，头尾各一个
    private Node head; //头哨兵
    private Node tail; //尾哨兵

    public DoublyLinkedListSentinel() {
        //初始化链表头哨兵不需要prev，值无所谓，next初始化为尾节点
        //初始化链表尾哨兵不需要next，值无所谓，prev初始化为头节点
        head = new Node(null,666,null);
        tail = new Node(null,888,null);
        head.next = tail;
        tail.prev = head;
    }
}

常用带哨兵方法

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
     * 根据索引查找指定节点
     * @param index-索引值
     * @return 节点对象
     */
    private Node findNode(int index){//工具类不给外界使用设为私有
        int i = -1;
        for (Node p = head; p != tail; p = p.next,i++){
            if(index == i){
                return p;
            }
        }
        return null;
    }

    /**
     * 根据索引插入节点
     * @param index-索引值
     * @param value-待添加值
     * @throws IllegalArgumentException-索引越界
     */
    public void insert(int index,int value){
        //获取待添加的位置的上一个节点和下一个节点地址
        Node prev = findNode(index - 1);
        if(prev == null){
            throw illegalIndex(index);
        }
        Node next = prev.next;
        Node inserted = new Node(prev,value,next);
        //上一个节点的next改为添加的节点地址值
        //下一个节点的prev改为添加的节点地址值
        prev.next = inserted;
        next.prev = inserted;
    }

    /**
     * 抽取出来的异常类
     * @param index
     * @return
     */
    private static IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }

    /**
     * 通过索引删除
     * @param index-索引值
     */
    public void remove(int index){
        Node prev = findNode(index - 1);
        if(prev == null){
            throw illegalIndex(index);
        }
        Node removed = prev.next;
        if(removed == tail){
            throw illegalIndex(index);
        }
        Node next = removed.next;
        //待删除的前后两个节点前后互指即可
        prev.next = next;
        next.prev = prev;
    }

    /**
     * 尾插入值
     * @param value-值
     */
    public void addLast(int value){
        //逻辑很简单，有尾哨兵更简单直接操作
        Node last = tail.prev;
        Node added = new Node(last,value,tail);
        last.next = added;
        tail.prev = added;
    }

    /**
     * 尾删除值
     */
    public void removeLast(){
        Node removed = tail.prev;
        //如果链表除了哨兵之外没有值了，这个时候不能删除头哨兵
        if(removed == head){
            throw illegalIndex(0);
        }
        Node prev = removed.prev;
        //上一个节点指向尾哨兵
        prev.next = tail;
        //尾哨兵prev指向待删除的上一个节点值
        tail.prev = prev;
    }

环形链表(带哨兵)

双向环形链表带哨兵，这时哨兵既作为头，也作为尾(优雅)

创建环形双向链表类

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 RingLinkedListSentinel implements Iterable<Integer>{
    //重写迭代器
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = sentinel.next;
            @Override
            public boolean hasNext() { // 是否有下一个元素
                //等于哨兵的地址值表示刚好转了一圈，此时结束遍历
                return p != sentinel;
            }

            @Override
            public Integer next() { //返回当前值，并指向下一个元素
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    /**
     * 节点类
     */
    private static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    //创建哨兵
    private Node sentinel = new Node(null,-1,null);

    public RingLinkedListSentinel() {
        //环形双向链表的哨兵初始化prev和next都要指向自己
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }
}

常见的环形链表方法

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
    * 添加到第一个
    * @param value
    */
   public void addFirst(int value){
       //通过哨兵指针获取哨兵对象已经它的下一个对象
       //当环形链表只存在哨兵时，a和b都是指的哨兵地址
       Node a = sentinel;
       Node b = sentinel.next;
       //创建带添加的节点，前后就是哨兵(a)和初始第一个节点(b)
       Node inserted = new Node(a,value,b);
       //哨兵指向下一位为新添加节点，原来第一个节点上一位指向新节点
       a.next = inserted;
       b.prev = inserted;
   }

   /**
    * 添加到最后一个
    * @param value
    */
   public void addLast(int value){
       //自己想想就知道了，不用注释啦
       //核心就把环形拆成正常的双向链表，只不过尾哨兵和头哨兵一样
       Node a = sentinel.prev;
       Node b = sentinel;

       Node inserted = new Node(a,value,b);

       a.next = inserted;
       b.prev = inserted;
   }

   /**
    * 删除第一个节点
    */
   public void removeFirst(){
       Node removed = sentinel.next;
       //如果哨兵的上一个节点还是哨兵，那么说明这个链表没有任何值了，不能删除
       if(removed == sentinel){
           throw new IllegalArgumentException("非法");
       }
       Node a = sentinel;
       Node b =removed.next;
       a.next = b;
       b.prev = a;
   }

   /**
    * 删除最后一个节点
    */
   public void removeLast(){
       Node removed = sentinel.prev;
       //如果哨兵的上一个节点还是哨兵，那么说明这个链表没有任何值了，不能删除
       if(removed == sentinel){
           throw new IllegalArgumentException("非法");
       }
       Node a = removed.prev;
       Node b = sentinel;
       a.next = b;
       b.prev = a;
   }

   /**
    * 根据值删除(新)
    * @param value
    */
   public void removeByValue(int value){
       Node removed = findByValue(value);
       if(removed == null){
           return; //没找到不用删
       }
       Node a =removed.prev;
       Node b =removed.next;
       a.next = b;
       b.prev = a;
   }

   /**
    * 根据值查找(私有内部方法)
    * @param value
    * @return
    */
   private Node findByValue(int value){
       Node p =sentinel.next;
       while(p != sentinel){
           if(p.value == value){
               return p;
           }
           p = p.next;
       }
       return null;
   }

链表递归遍历法

下面以单向链表(带哨兵)来展示递归遍历，下一节就会讲递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void loop3(Consumer<Integer> before,
                      Consumer<Integer> after){
        //以单向链表为例，有哨兵的话参数地址就是哨兵.next
        recursion(head.next,before,after);
    }

    private void recursion(Node curr,
                           Consumer<Integer> before, Consumer<Integer> after){ //某个节点要进行的操作
        if(curr == null){
            return;
        }
        before.accept(curr.value);
        //将下一个节点地址当作参数值传递实现递归
        recursion(curr.next, before, after);
        after.accept(curr.value);
    }

实现的结果:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
list.loop3(value -> {
            System.out.println("before" + value);
        }, value ->{
            System.out.println("after" + value);
        });

/*
    before:1
    before:2
    before:3
    before:4
    after:1
    after:2
    after:3
    after:4
*/

由结果不难发现执行递归的上下遍历出来的链表顺序互为逆序
究其原因应该是发生了递归回溯，根据出入栈的规则导致结果的不同
跟spring特性中的AOP(面向切面编程)的原理很类似
详细的解释等下一章学递归就好解释了
解释：只有内层方法调用完了，外层才能继续运行，意思就是外层从一开始调用就不会停止，直到回到最外层走完。
将递归打开更加直观(没有用到的判断被我删去了)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void f(Node node = 1) {
    System.out.println("before" + node.value);
    void f(Node node = 2) {
        System.out.println("before" + node.value);
        void f(Node node = 3) {
            System.out.println("before" + node.value);
            void f(Node node = null) {
                if(node == null) {
                    return;
                }
            }
            System.out.println("after" + node.value);
        }
        System.out.println("after" + node.value);
    }
    System.out.println("after" + node.value);
}