单向链表

和数组相同,链表也是一种线性表结构。作为非常基础、非常常用的两种数据结构,数组和链表经常被拿来比较。

链表定义
  1. 链表是一种线性表数据结构;
  2. 从底层存储结构上看,链表不需要一整块连续的存储空间,而是通过“指针”将一组零散的内存块串联起来使用;
  3. 链表中的每个内存块被称为链表的“结点”,每个结点除了要存储数据外,还需要记录上(下)一个结点的地址。
链表特点
  1. 插入、删除数据效率高,只需要考虑相邻结点的指针改变,不需要搬移数据,时间复杂度是 O(1)。
  2. 随机查找效率低,需要根据指针一个结点一个结点的遍历查找,时间复杂度为O(n)。
  3. 与内存相比,链表的空间消耗大,因为每个结点除了要存储数据本身,还要储存上(下)结点的地址。
实现

链表的每一个节点都有两个属性,一个是数据,一个是指向下一个节点的指针,我们需要创建一个节点类来辅助。

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
class Node<E>{//节点类
private E item;//数据
private Node<E> next;//下一个的元素的指针

public void setNext(Node<E> next) {
this.next = next;
}

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

public void setItem(E item) {
this.item = item;
}

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

public Node<E> getNext() {
return next;
}

public E getItem() {
return item;
}

public Node(){

}
}

为了方便我们遍历和查找,创建一个头结点,让他的next指向一个节点。那么单向链表的增加功能就基本可以实现了。

增:让最后一个的节点next指向要添加的元素即可

在实现类里,添加表示头结点、尾节点和长度的属性。添加的时候让last.next指向新节点、last指向新节点,last表示这是最后一个节点,并且长度+1

1
2
3
4
5
6
7
8
9
10
11
12
13
   private Node<Object> head;//头结点
private Node<Object> last; //最后一个结点
private int size;//长度,方便遍历和避免了处理null问题
public SinglyLinkedList(){
head = new Node<Object>();//实例化
last = head;//当第一次添加的时候,下一个节点和头节点一起用
}
public void add(E e){
Node<E> node = new Node<>(e);//实例化节点,并添加元素进去
last.setNext(node);
last=node;//最后一个节点
size++;
}

遍历:根据size的长度循环遍历

1
2
3
4
5
6
7
8
public void getList() {
Node temp = head;
for (int i = 0; i < size; i++) {
temp = temp.getNext();
System.out.println(temp);

}
}

查询第n个:循环遍历链表

1
2
3
4
5
6
7
8
public Node<E> select(int index){
if (index<=0||index>size) return null;
Node <E>temp = head;
for (int i = 0; i < index; i++) {
temp = head.getNext();
}
return temp;
}

删:单向链表是链接式的,并且通过“指针”指向下一个,如果我们要删除某个节点,只需要让要删除节点的上一个节点next指向要删除节点的下一个即可

1
2
3
4
5
6
7
8
9
10
11
12
public void delete(int index){
if (index<=0||index>size) return;
else if (index==1)//第一个节点
head.next = head.next.next;
else if (index==size)//最后一个节点
select(index-1).setNext(null);
else{
Node<E> n = select(index-1);
n.setNext(n.getNext().getNext());
}
size--;
}

改:实现原理和删相识,让要删除节点的上一个节点指向修改好的新节点,然后新节点指向需修改节点的下一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void change(int index,E e){
if (index<=0||index>size) return;
Node<E> node= new Node(e);
if (index==1){//第一个节点
node.setNext(head.getNext().getNext());
head.setNext(node);
}else if (index==size) {//最后一个节点
select(index - 1).setNext(node);
last = node;
}else{
Node<E> temp = select(index-1);
node.setNext(temp.getNext().getNext());
temp.setNext(node);
}

}

扩展:

有序增加,并且不能值重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void addOrderly(int e){
Node node = new Node(e);
Node temp = head;
for (int i = 0; i < size; i++) {
if (temp.getNext()==null)
break;
if ((int)temp.getNext().getItem()==e)
return;
else if((int)temp.getNext().getItem()>e)
break;
temp = temp.getNext();
}
if (size==0||temp.getNext()==null) last = node;
node.setNext(temp.getNext());
temp.setNext(node);
size++;
}

用数组实现的单向链表

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
public class StaticLinkedList <E>{
private final int MAX_SIZE = 1000;
private E data;//数据项
private int cur;//游标
private StaticLinkedList []ls = null;

public StaticLinkedList(){
ls = new StaticLinkedList[MAX_SIZE];
InitLinkedList();

}
enum Status{//状态
OK,ERROR,TRUE,FLASE;
}
//返回长度
public int ListLength(){
int j = 0;
int i = ls[MAX_SIZE-1].cur;//第一个元素的下标
while (i!=0)//一直遍历到最后一个元素
{
i = ls[i].cur;
}
return j;
}

//初始化
public void InitLinkedList(){
for (int i = 0; i < MAX_SIZE-1; i++) {
ls[i].cur = i+1;
}
ls[MAX_SIZE-1].cur = 0;//目前静态链表为空,最后一个元素游标为0

}
//返回空闲分量的下标并自增
public int Malloc_SLL(){
int i = ls[0].cur;
if (i == MAX_SIZE-2)
return 0;
if (ls[0].cur !=0)
ls[0].cur = ls[i].cur;//+1
return i;

}
//增加
public Status ListAppend(E e){
int i = Malloc_SLL();
if (i == 0)//超出范围
return Status.ERROR;
if(i == 1)//第一次
ls[i].cur = 0;
else{
ls[i-1].cur = i;//让前一个元素游标指向后一个元素的下标
ls[i].cur = 0;//最后一个元素游标为0
}
ls[i].data = e;
return Status.OK;
}
/*
插入;
i为第几个元素
*/
public Status ListInsert(int i, E e){
int k = MAX_SIZE-1,j;//最后元素下标
if (i< 1 || i> ListLength()+1)//越界
return Status.ERROR;
j = Malloc_SLL(); //获得闲分量的下标、更新空闲分量下标
if (j!=0){//如果j等于说明当前链表为空
ls[j].data = e;
for (int l = 1; l < i-1; l++)
k = ls[k].cur;//找到第i个元素的前一个元素
ls[j].cur = ls[k].cur;//互换游标,让插入元素的游标指向第i个元素
ls[k].cur = j;//将插入位置的前一个元素的游标变成插入元素的下标

return Status.OK;
}
return Status.ERROR;
}
/*
删除
*/
public Status ListDelete(int i){
int k = MAX_SIZE-1,j;
if (i< 1 || i> ListLength()+1)//越界
return Status.ERROR;
for (int l = 1; l < i-1; l++)
k = ls[k].cur;//找到要删除的元素的前一个元素下标
j = ls[k].cur;//要删除的元素
ls[k].cur = ls[j].cur;//将前一个元素的游标变成删除元素的游标
Free_SSL( j);//更改空闲分量
return Status.OK;
}
/*

*/
public Status ListChange(int i,E e){
int k = MAX_SIZE-1;//最后元素下标
for (int j = 1; j < i; j++)
k = ls[k].cur;
ls[k].data = e;

return Status.OK;
}

/*

*/
public E ListFind(int i){
int k = MAX_SIZE-1;//最后元素下标
for (int j = 1; j < i; j++)
k = ls[k].cur;
return (E) ls[k].data;


}
//释放节点
public void Free_SSL( int k){
ls[k].cur = ls[0].cur;//把下一个空闲分量的下标赋值给删除元素的游标
ls[0].cur = k;//让删除元素变成空闲分量:优先空位
}

}
测试
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
public class SingLinkedList<E> {
private Node<E> head;//头结点
private Node<E> last; //最后一个结点
private int size;//长度
public SingLinkedList(){
head = new Node<E>();//实例化
last = head;//当第一次添加的时候,下一个节点和头节点一起用
}
//链表长度
public int Size() {
return size;
//添加
public void add(E e){
//实例化节点,并添加元素进去
add(new Node<>(e));
}
public void add(Node<E> node){//添加元素进去
last.setNext(node);
last=node;//最后一个节点
size++;
}
//有序添加
public void addOrderly(int e){
Node node = new Node(e);
Node temp = head;
for (int i = 0; i < size; i++) {
if (temp.getNext()==null)
break;
if ((int)temp.getNext().getItem()==e)
return;
else if((int)temp.getNext().getItem()>e)
break;
temp = temp.getNext();
}
if (size==0||temp.getNext()==null) last = node;
node.setNext(temp.getNext());
temp.setNext(node);
size++;
}
//插入

public void insert(int index,E e){
if (index<=0||index>size) return;
Node<E> node= new Node(e);
if (index==1){//第一个节点
node.setNext(head.getNext());
head.setNext(node);
size++;
}else{
Node<E> temp = select(index-1);
node.setNext(temp.getNext());
temp.setNext(node);
size++;
}
}
public void insert(Node last,Node next,Node node,int index){
if (index==size){
add(node);
return;
}
last.setNext(node);
node.setNext(next);
size++;
}

//删除
public void delete(int index){
if (index<=0||index>size) return;
else if (index==1)//第一个节点
head.next = head.next.next;
else if (index==size)//最后一个节点
select(index-1).setNext(null);
else{
Node<E> n = select(index-1);
n.setNext(n.getNext().getNext());
}
size--;
}
//修改
public void change(int index,E e){
if (index<=0||index>size) return;
Node<E> node= new Node(e);
if (index==1){//第一个节点
node.setNext(head.getNext().getNext());
head.setNext(node);
}else if (index==size) {//最后一个节点
select(index - 1).setNext(node);
last = node;
}else{
Node<E> temp = select(index-1);
node.setNext(temp.getNext().getNext());
temp.setNext(node);
}

}
//查询
public Node<E> select(int index){
if (index<=0||index>size) return null;
Node <E>temp = head;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
public String getList() {
Node<E> temp = head;
String l = "[";
for (int i = 0; i < size; i++) {
temp = temp.getNext();
l+=temp.getItem()+" ";
}
return l+"]";
}
//获取最后一个节点数据
public E getEnd(){
return last.getItem();
}

class Node<E>{//节点类
private E item;//数据
private Node<E> next;//下一个的元素的指针

public void setNext(Node<E> next) {
this.next = next;
}

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


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

public Node<E> getNext() {
return next;
}

public E getItem() {
return item;
}

public Node(){

}
}

public static void main(String[] args) {
SingLinkedList list = new SingLinkedList();
list.addOrderly(3);
list.addOrderly(5);
list.addOrderly(4);
list.addOrderly(7);
list.addOrderly(7);
list.addOrderly(8);
System.out.println(list.getList());
list.delete(2);
System.out.println(list.getList());
list.change(4, 18);
System.out.println(list.getList());
list.insert(4, 66);
System.out.println(list.getList());
}

}

输出

[3 4 5 7 8 ]
[3 5 7 8 ]
[3 5 7 18 ]
[3 5 7 66 18 ]

Process finished with exit code 0