Chp4链表 LinkedList
一、基本概念
链表：最简单的动态数据结构
重要性：更深入的理解引用和递归，辅助组成其他数据结构
优点：真正的动态，不需要处理固定的容量
缺点：丧失了随机访问的能力
与数组对比：数组最好用于索引有语义的情况(例 score[2])，其最大的有点是支持快速查询；
特点：
图解：数据存储在 “节点”（Node）中，实际存储在 e 中，数据与数据之间的链接(对下一个链表的引用)由 next 完成；最后一个节点 next 存储的为 Null；如果为Null则证明是最后一个节点。
首先在链表类中定义私有内部类Node
而Node中next的定义类型也称作“自引用”式，因为Node中包含了一个和自己类型相同的字段（本例中为next）。类型Node的next字段仅仅是对另外的一个Node对象的“引用”，而不是一个对象。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| private class Node{
public E e;
public Node next;
public Node(E e,Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
@Override
public String toString(){
e.toString();
}
}
|
二、 在链表中添加元素
对于一个链表来说，想要访问存储在其中的所有节点，我们必须把链表的头 head 存储起来，
在链表头添加元素:
图解（要将 666【叫做node】 加入链表中而不破坏现有的链表结构）
步骤：1.让 node 的 next 指向现在链表的头，即执行 node.next = head
此时，666 成为新的链表头，让 head 指向新的 666 节点，即执行 head = node
在链表中间添加元素:
图解：将 666 插入到链表中 1 的位置
步骤：1.要插入节点 666 ，必须要找到插入666之后，这个节点之前的节点是谁，将其叫做 prev，其初始化和 head 在同一个地方,执行 Node prev = head;
步骤2：要找到 666 之前节点 ，因为插入 666 的索引为2【链表中并没有索引这个概念】故之前节点的索引为 1 ，从0开始遍历，遍历到索引为1的位置即可；
步骤3：将 node 的 next 指向 prev 的下一个元素，即执行 node.next = prev.next
步骤4：prev 的 next 指向 node, 即执行 node.next = prev.next,成功将 666 插入到链表中
关键：找到要添加的节点的前一个节点（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
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
| public class LinkedList<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@Override
public String toString(){
return e.toString();
}
}
private Node head;
private int size;
public LinkedList(){
head = null;
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
public void addFirst(E e){
head = new Node(e, head);
size ++;
}
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");
if(index == 0)
addFirst(e);
else{
Node prev = head;
for(int i = 0 ; i < index - 1 ; i ++)
prev = prev.next;
prev.next = new Node(e, prev.next);
size ++;
}
}
public void addLast(E e){
add(size, e);
}
}
|
三、使用链表的虚拟头结点
上面所述的方法中在链表头添加元素时存在特殊：为链表添加元素的过程要找到待添加位之前的节点，但对于链表头来说并没有之前的节点，所以在逻辑上特殊。通过使用链表的虚拟头节点即可将链表头添加元素与其他位置添加元素统一起来。
图解：创建个虚拟节点即可解决链表头添加元素时的问题，对链表来说，第一个元素是 dummyHead 的 next 对应的节点的元素，而不是 dummyHead 对应的节点的元素，dummyHead 这个位置的元素是根本不存在的，对用户来说也没有意义，只是为了逻辑编写方便设置的虚拟头结点。这样所有的元素都有前一个位置的节点，并且初始的时候 dummyHead 指向的就是 0 这个元素的前一个节点。
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
| public class LinkedList<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@Override
public String toString(){
return e.toString();
}
}
private Node dummyHead;
private int size;
public LinkedList(){
dummyHead = new Node();
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");
Node prev = dummyHead;
for(int i = 0 ; i < index ; i ++)
prev = prev.next;
prev.next = new Node(e, prev.next);
size ++;
}
public void addFirst(E e){
add(0, e);
}
public void addLast(E e){
add(size, e);
}
}
|
四、链表遍历，查询和修改
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
|
public E get(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Illegal index.");
Node cur = dummyHead.next;
for(int i = 0 ; i < index ; i ++)
cur = cur.next;
return cur.e;
}
public E getFirst(){
return get(0);
}
public E getLast(){
return get(size - 1);
}
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Illegal index.");
Node cur = dummyHead.next;
for(int i = 0 ; i < index ; i ++)
cur = cur.next;
cur.e = e;
}
public boolean contains(E e){
Node cur = dummyHead.next;
while(cur != null){
if(cur.e.equals(e))
return true;
cur = cur.next;
}
return false;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
for(Node cur = dummyHead.next ; cur != null ; cur = cur.next)
res.append(cur + "->");
res.append("NULL");
return res.toString();
}
}
|
测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Main {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
for(int i = 0 ; i < 5 ; i ++){
linkedList.addFirst(i);
System.out.println(linkedList);
}
linkedList.add(2, 666);
System.out.println(linkedList);
}
}
|
五、删除元素
删除元素和添加元素基本类似，都是定位之前一个删除元素之前的元素 修改元素指向才是改变链表的本质（修改元素并不能改变链表）
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
| public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
Node prev = dummyHead;
for(int i = 0 ; i < index ; i ++)
prev = prev.next;
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
size --;
return retNode.e;
}
public E removeFirst(){
return remove(0);
}
public E removeLast(){
return remove(size - 1);
}
public void removeElement(E e){
Node prev = dummyHead;
while(prev.next != null){
if(prev.next.e.equals(e))
break;
prev = prev.next;
}
if(prev.next != null){
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size --;
}
}
|
六、链表中的方法和对应的时间复杂度
