1.链表的定义



与数组有很大的区别,链表不用去申请一段连续的空间,而且他的存储是不连续的,可以真正地做到动态长度。在链表中,不但需要记录该元素的值,还需要记录下一个元素的地址。

数组在使用时需要申请一段连续空间,当内存不足时就会申请失败,使用链表就可以避免这个问题,不需要进行申请一段连续的内存空间,可以进行动态申请,用到的时候才需要申请。

2.什么时候用链表

当需要对数据进行大量的删除插入操作的时候,就可以选择使用链表,这两个操作对于链表来说他的时间复杂度可以说是 O(1)。严格意义来说还是 O(n)。因为进行插入数据的时候,还是需要通过遍历来找到插入的位置,但是这里不需要进行数据迁移,将数据插入即可。如下图所示:

链表插入

可以看到,找到位置后,修改其下一个指向元素指向即可,但是需要注意的是,两个指向的改变顺序不能变

1
2
n.next = node.next;
node.next = n;

变了之后就会使新插入的元素指向自己,这就会产生引用混乱了。

删除元素也是同理。

3.加入虚拟头结点的作用



在对链表进行插入和删除等操作时,都必须考虑头结点是否为空的情况,因为不为空才会有下一个节点的存在。

在加上了虚拟头结点,就可以节省这一步的操作,无论链表是否为空,都必定存在链表,只不过这个链表只有虚拟头结点的时候长度还是为 0, 这个时候就可以判断该节点的下一个节点是否为空即可。

注意:虚拟头结点不算入长度

4.需要的结构以及实现的基本方法



结构:
需要一个内部类,里面存储元素的值以及下一个元素的引用
同时在初始化链表的时候需要声明长度为 0 ,并且实现虚拟头结点

方法:

  • int getLength():获取链表长度
  • boolean isEmpty():判断链表是否为空
  • void add(int index, int data):向链表的 index 位置加入元素
  • int get(int index):获取 index 位置的元素
  • void set(int index, int data):修改 index 位置的元素
  • boolean contains(int data):判断该元素是否在链表中
  • int remove(int index):移除链表中 index 位置的元素
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
import java.util.Random;

// 单链表
public class SinglyLinkedlist {
// 节点结构
class Node{
int data;
Node next; // 记录下一节点

public Node(Node node, int data){
this.next = node;
this.data = data;
}
public Node(int data){
this(null, data);
}

public String toString(){
return data + "";
}

}

int length;
Node head; // 虚拟头结点

public SinglyLinkedlist(){
this.length = 0;
// 初始化头结点
head = new Node(null, 0);
}

// 获取长度
public int getLength(){
return length;
}

// 判断链表是否为空
public boolean isEmpty(){
return length == 0;
}

// 往链表头添加元素
public void addFirst(int data){
// 因为第一个节点是不存储数据的,所以不需要判断第一个节点是否为空
// Node node = new Node(data);
// node.next = head.next;
// head.next = node;
// length ++;

add(0, data);
}

// 往链尾添加元素
public void addLast(int data){

// Node node = head;
// for (;node.next != null; node = node.next) {
//
// }
// node.next = new Node(data);
// length ++;

add(length, data); // 直接调用自己的函数
}

// 往链表任意位置插入元素
public void add(int index, int data){
if(index < 0 || index >length)
throw new IllegalArgumentException("插入元素失败,index 非法");

Node node = head;
int i = 0;
// 找到插入元素位置的前一个节点即可
while(i < index){
node = node.next;
i ++;
}
Node n = new Node(data);
n.next = node.next;
node.next = n;

length ++;
}

// 获取链表index的位置
public int get(int index){
if(index < 0 || index >= length)
throw new IllegalArgumentException("获取元素失败,index 非法");
Node node = head;
for(int i = 0; i < index; i++){
node = node.next;
}
return node.next.data;
}

// 获取首位元素
public int getFirst(){
return get(0);
}

// 获取尾部元素
public int getLast(){
return get(length - 1);
}

// 修改链表中的 index 位置的元素
public void set(int index, int data){
if(index < 0 || index >= length)
throw new IllegalArgumentException("插入元素失败,index 非法");
Node node = head.next;
int i = 0;
while(i < index){
node = node.next;
i++;
}
node.data = data;
}

// 查询链表是否包含这个元素
public boolean contains(int data){
Node node = head.next;
while(node != null){
if(node.data == data)
return true;
node = node.next;
}
return false;
}

// 删除指定节点
public int remove(int index){
if(index < 0 || index >= length)
throw new IllegalArgumentException("删除元素失败,index 非法");
Node node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
Node n = node.next; // 准备被删除的元素
node.next = n.next;
int data = n.data;
n.next = null; // 释放
length--; // 必须记得这个
return data;
}

// 删除头结点
public int removeFirst(){
return remove(0);
}

// 删除尾节点
public int removeLast(){
return remove(length - 1);
}

@Override
public String toString(){
StringBuilder res = new StringBuilder();
Node node = head.next;
res.append(String.format("length: %d\n", length));
res.append("LinkedList: ");
for(int i = 0; i < length; i++){
res.append(node.data);
res.append(" --> ");
node = node.next;
}
res.append("NULL");

return res.toString();
}

5.以后补充