Java · 链表概念以及结构 · 单链表接口实现 · 双向链表接口实现

一、链表

链表的概念以及结构

链表在物理存储结构上是非连续的，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

实际中链表的结构非常多样，以下情况组合起来就有 8 种：

单链表、双向链表：

不带头单链表、带头链表：

单链表、循环单链表：

虽然有这么多的链表结构，但是我们重点掌握两种：

• 无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际中更多是作为其它数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

• 无头双向链表：在 Java 的集合框架库中 LinkedList 底层实现就是无头双向循环链表（图中的400，200等本为地址，为了画图方便，这里简写）。

链表的接口

无头单向非循环链表：

// 1、无头单向非循环链表实现
public class SingleLinkedList {
  //头插法
  public void addFirst(int data);
  
  //尾插法
  public void addLast(int data);
  
  //任意位置插入,第一个数据节点为0号下标
  public boolean addIndex(int index,int data);
  
  //查找是否包含关键字key是否在单链表当中
  public boolean contains(int key);
  
  //删除第一次出现关键字为key的节点
  public void remove(int key);
  
  //删除所有值为key的节点
  public void removeAllKey(int key);
  
  //得到单链表的长度
  public int size();
  
  public void display();
  
  public void clear();
}
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

无头双向链表实现：

// 2、无头双向链表实现
public class DoubleLinkedList {
  //头插法
  public void addFirst(int data);
  
  //尾插法
  public void addLast(int data);

  //任意位置插入,第一个数据节点为0号下标
  public boolean addIndex(int index,int data);
  
  //查找是否包含关键字key是否在单链表当中
  public boolean contains(int key);
  
  //删除第一次出现关键字为key的节点
  public void remove(int key);
  
  //删除所有值为key的节点
  public void removeAllKey(int key);
  
  //得到单链表的长度
  public int size();
  
  public void display();
  
  public void clear();
  
}
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

链表接口实现

1.1 无头单向非循环链表实现

class ListNode{
    public int val; //链表的值
    public ListNode next;   //链表下一节点的地址

    public ListNode(int val) {
        this.val = val;
    }
}

public class MyLinkedList {
    //单链表的头节点
    public ListNode head;

    //穷举法 创建链表
    public void createList() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(5);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        this.head = node1;
    }

    //打印链表
    public void show() {
        //定义一个cur节点记录头节点
        ListNode cur = this.head;
        //只要cur节点不为null
        while (cur != null) {
            //就一直打印节点
            System.out.print(cur.val + " ");
            //打印完就后移cur节点
            cur = cur.next;
        }
        System.out.println();
    }

    //获取链表的长度
    public int size() {
        //判断链表是否有值
        if (this.head == null) {
            return 0;
        }
        //头节点不宜移动，定义cur节点
        ListNode cur = this.head;
        int count = 0;
        //只要cur节点不为空
        while (cur != null) {
            count++;
            //节点cur后移
            cur = cur.next;
        }
        return count;
    }

    //查找链表是否包含关键字key
    public boolean contains(int key) {
        //判断链表是否有值
        if (this.head == null) {
            return false;
        }
        //头节点不宜移动，定义cur节点代替
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //添加节点 - 头插法
    public void addFirst(int data) {
        //新建节点
        ListNode node = new ListNode(data);
        //判断是否第一次插入数据
        if (this.head == null) {
            //直接指向即可
            this.head = node;
        }else {
            //新节点的下一节点next 指向现在链表的头节点
            node.next = this.head;
            //更新头节点
            this.head = node;
        }
    }

    //添加节点-尾插法
    public void addLast(int data) {
        //新建节点
        ListNode node = new ListNode(data);
        //头节点为空，直接指向新节点
        if (this.head == null) {
            this.head = node;
        }else {
            //cur代替头节点后移到末尾
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            //把末尾节点的next指向新节点即可
            cur.next = node;
        }
    }

    //通过下标index找到指定数据的前驱节点
    public ListNode searchPrev(int index) {
        // 定义cur代替头节点
        ListNode cur = this.head;
        // 遍历次数比链表长度少一
        // 就可以找到index位置的前驱
        for (int i = 0; i < index-1; i++) {
            cur = cur.next;
        }
        return cur;
    }

    //任意位置插入数据
    public void addIndex(int index, int data) {
        //判断index位置是否合法
        if (index < 0 || index > size()) {
            System.out.println("index有问题");
            return;
        }
        //头插法
        if (index == 0) {
            addFirst(data);
            return;
        }
        //尾插法
        if (index == size()) {
            addLast(data);
            return;
        }
        //中间插入数据
        ListNode prev = searchPrev(index);
        ListNode node = new ListNode(data);
        // 先让前驱节点的next指向node的next
        node.next = prev.next;
        prev.next = node;
    }

    //通过key值，找到关键字为key的节点的前驱
    public ListNode searchPrevNode(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //判断链表是否为空
        if (this.head == null) {
            System.out.println("链表空~");
            return;
        }
        //判断是否有该节点
        if (!contains(key)){
            System.out.println("没有key为" + key + "的节点");
            return;
        }
        //删除的节点是头节点
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        //前驱节点
        ListNode prev = searchPrevNode(key);
        ListNode cur = prev.next;
        //删除的节点在尾巴
        prev.next = cur.next;
        //删除的节点在中间
        if (cur.next != null) {
            cur.next = null;
        }
    }

    //方法一：删除所有值为key的节点
    public void removeAllKey1(int key) {
        if (this.head == null) {
            System.out.println("头节点为空");
            return;
        }
        if (!contains(key)) {
            System.out.println("链表中没有" + key);
            return;
        }

        while (contains(key)) {
            //判断头节点
            if (key == this.head.val) {
                this.head = this.head.next;
                continue;
            }
            //尾节点删除
            ListNode prev = searchPrevNode(key);
            ListNode cur = prev.next;
            prev.next = cur.next;
            if (cur.next != null) {
                cur.next = null;
            }
        }
    }

    //方法二：删除所有值为key的节点
    public void removeAllKey2(int key) {
        //判断链表是否空
        if (this.head == null) {
            System.out.println("链表空");
            return;
        }
        //判断key是否存在
        if (!contains(key)) {
            System.out.println("key不存在");
            return;
        }
        //使用前后指针prev和cur删除
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        //遍历链表判断是否需要删除
        while (cur != null) {
            if (key == cur.val) {
                prev.next = cur.next;
                cur.next = null;
                cur = prev.next;
            }else {
                cur = cur.next;
                prev = prev.next;
            }
        }
        //单独判断头节点
        if (this.head.val == key) {
            this.head = this.head.next;
        }
    }

    //清除链表
    public void clear() {
        //定义一个清理指向的节点cur
        ListNode cur = null;
        //只要头节点非空就清理
        while (this.head != null) {
            //找到头节点位置
            cur = this.head;
            //让头节点先润
            this.head = this.head.next;
            //置空
            cur.next = null;
        }
    }
}
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259

1.2 代码图解

---

2.1无头双向链表实现

class ListNodeD {
    public int data;    //数据域
    public ListNodeD prev;  //前驱
    public ListNodeD next;  //后续

    public ListNodeD(int data) {
        this.data = data;
    }
}

public class MyRealLinkedList {
    //头尾节点事关全局，不建议改变位置
    public ListNodeD head;  //头
    public ListNodeD last;  //尾

    //输出链表数据
    public void display(){
        if (this.head == null) {
            System.out.println("链表为空");
            return;
        }
        ListNodeD cur = this.head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //获取链表长度
    public int size(){
        int count = 0;
        if (this.head == null) {
            return count;
        }
        ListNodeD cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法
    public void addFirst(int data) {
        ListNodeD node = new ListNodeD(data);
        if (this.head == null) {
            this.head = node;
            this.last = node;
        }else {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }

    //尾插法
    public void addLast(int data) {
        ListNodeD node = new ListNodeD(data);
        if (this.head == null) {
            this.last = node;
            this.head = node;
        }else {
            this.last.next = node;
            node.prev = this.last;
            this.last = node;
        }
    }


    //找index位置的前一位节点
    public ListNodeD findIndex(int index) {
        int count = 0;
        ListNodeD cur = this.head;
        while (count < index-1) {
            count++;
            cur = cur.next;
        }
        return cur;
    }

    //任意位置插入，第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        //判断index是否合法
        if (index < 0 || index > size()) {
            System.out.println("index有问题");
            return;
        }
        //判断链表是否有数据
        if (this.head == null) {
            System.out.println("链表数据为空");
            return;
        }
        //头插法
        if (index == 0) {
            addFirst(data);
            return;
        }
        //尾插法
        if (index == size()) {
            addLast(data);
            return;
        }
        //插入链表中间位置
        ListNodeD cur = findIndex(index);
        ListNodeD node = new ListNodeD(data);
        node.prev = cur;
        node.next = cur.next;
        cur.next.prev = node;
        cur.next = node;
    }

    //查找是否包含关键字key.是否在单链表当中
    public boolean contains(int key) {
        //链表为空
        if (this.head == null) {
            return false;
        }
        ListNodeD cur = this.head;
        while (cur != null){
            if (key == cur.data) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //判断空表
        if (this.head == null) {
            System.out.println("空表");
            return;
        }
        //判断是否有key在链表中
        if (!contains(key)) {
            System.out.println("key不存在");
            return;
        }
        ListNodeD cur = this.head;
        //删除节点在头节点
        if (this.head.data == key) {
            this.head = this.head.next;
            this.head.prev = null;
            cur.next = null;
            return;
        }
        //删除节点在尾节点
        if (this.last.data == key) {
            this.last = this.last.prev;
            this.last.next = null;
            cur.prev = null;
            return;
        }
        //删除节点在中间
        while (cur != null){
            if (cur.data == key) {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                return;
            }
            cur = cur.next;
        }
        return;
    }


    //删除所有值为key的节点
    public void removeAllKey(int key) {
        //判断空表
        if (this.head == null) {
            System.out.println("空表");
            return;
        }
        //判断是否有key在链表中
        if (!contains(key)) {
            System.out.println("key不存在");
            return;
        }

        //判断链表中只有key就进入循环
        while (contains(key)) {
            //创建cur代替头节点去删除key
            ListNodeD cur = this.head;
            //删除节点在头节点
            if (this.head.data == key) {
                this.head = this.head.next;
                this.head.prev = null;
                cur.next = null;
            }
            //删除节点在尾节点
            if (this.last.data == key) {
                this.last = this.last.prev;
                this.last.next = null;
                cur.prev = null;
            }
            //删除节点在中间
            while (cur != null){
                if (cur.data == key) {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    //删除一个就溜，不然容易空指针异常
                    break;
                }
                cur = cur.next;
            }
        }
    }

    //清除双向链表的数据
    public void clear(){
        ListNodeD cur = this.head;
        while (this.head != null) {
            this.head = this.head.next;
            cur.next = null;
            cur.prev = null;
            cur = this.head;
        }
        this.head = null;
        this.last = null;
    }
}
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223

2.2 代码图解

---

链表测试类

public class Test {
    //双向链表测试
    public static void main(String[] args) {
        MyRealLinkedList mr = new MyRealLinkedList();
        mr.addLast(1);
        mr.addLast(2);
        mr.addLast(2);
        mr.addLast(4);
        mr.addLast(2);
        mr.addLast(2);
        mr.addLast(2);
        mr.display();

        mr.clear();
        mr.display();

//        mr.removeAllKey(2);
//        mr.display();

//        mr.remove(2);
//        mr.display();

//        System.out.println(mr.contains(6));

//        mr.addIndex(5,99);
//        mr.display();

//        System.out.println(mr.size());
    }


    //单链表测试
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.createList();
        myLinkedList.show();

//        myLinkedList.clear();
//        myLinkedList.show();

//        myLinkedList.removeAllKey1(4);
//        myLinkedList.removeAllKey2(1);
//        myLinkedList.show();

//        myLinkedList.remove(4);
//        myLinkedList.show();

//        myLinkedList.show();
//        myLinkedList.addIndex(0,0);
//        myLinkedList.show();
//        myLinkedList.addIndex(myLinkedList.size(),myLinkedList.size());
//        myLinkedList.show();
//        myLinkedList.addIndex(3,999);
//        myLinkedList.show();

//        myLinkedList.addFirst(11);
//        myLinkedList.addFirst(22);
//        myLinkedList.addLast(11);
//        myLinkedList.addLast(22);
//        myLinkedList.show();

//        myLinkedList.show();
//        System.out.println(myLinkedList.size());
//        System.out.println(myLinkedList.contains(4));
    }
}
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

---

二、顺序表和链表的区别和联系

顺序表

优势：空间连续，支持随机访问。
缺点：中间或者前面的数据，需要插入或者删除操作的时候，时间复杂度高，效率低；增容的代价比较大。

链表

优势：任意位置插入删除数据，时间复杂度为O(1)；没有增容问题，插入一个开辟一个空间。
缺点：以节点为单位存储，不支持随机访问。