什么是链表?

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。   

什么是单向链表?

单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分,第一个部分(data)保存或者显示关于节点的信息,另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。(其实就是上一篇中提到的ListNode)

单向链表只可向一个方向遍历,一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置。而插入一个节点,对于单向链表,我们只提供在链表头插入,只需要将当前插入的节点设置为头节点,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
package LinkedList;

import java.util.LinkedList;


public class SingleLinkedList {
private int size;
private Node head;

public SingleLinkedList() {
size = 0;
head = null;
}

private class Node{
private Object data;//每个节点的数据
private Node next; //每个节点指向下一个节点的连接

public Node(Object data) {
this.data = data;
}
}

//在链表头添加元素
public Object addhead(Object obj) {
Node newHead = new Node(obj);
if(size == 0)
head = newHead;
else {
newHead.next = head;
head = newHead;
}
size++;
return obj;
}

//在链表头删除元素
public Object deleteHead() {
Object obj = head.data;
head = head.next;
size--;
return obj;
}

//查找指定元素,找到了返回节点Node,找不到返回null
public Node find(Object obj) {
Node current = head;
int tempSize = size;
while(tempSize > 0){
if(obj.equals(current.data)){
return current;
}else{
current = current.next;
}
tempSize--;
}
return null;
}

//删除指定的元素,删除成功返回true
public boolean delete(Object value){
if(size == 0){
return false;
}
Node current = head;
Node previous = head;
while(current.data != value){
if(current.next == null){
return false;
}else{
previous = current;
current = current.next;
}
}
//如果删除的节点是第一个节点
if(current == head){
head = current.next;
size--;
}else{//删除的节点不是第一个节点
previous.next = current.next;
size--;
}
return true;
}


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

//在链表尾部添加元素
public Object addTail(Object obj) {
Node newTail = new Node(obj);
Node current = head;
int temSize = size;
while (temSize > 0) {
if (current.next == null) {
//需要先增加链表的容量,才能进行添加
size++;
current.next = newTail;
newTail.next = null;

return current;
}else {
current = current.next;
}
temSize--;
}

return obj;
}

//显示节点信息
public void display() {
if (size > 0) {
Node node = head;
int tempSize = size;
if (tempSize == 1) {
System.out.print("[" + node.data + "]");
}
while (tempSize > 0) {
if (node.equals(head)) {
System.out.print("[" + node.data + "->");
}else if (node.next == null) {
System.out.print(node.data+"]");
}else {
System.out.print(node.data+"->");
}

node = node.next;
tempSize--;
}
System.out.println();
}else {
System.out.println("[]");
}
}
}

测试源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main(String[] args) {
// TODO Auto-generated method stub
SingleLinkedList sLinkedList = new SingleLinkedList();
sLinkedList.addhead("A");
sLinkedList.addhead("B");
sLinkedList.addhead("C");
sLinkedList.addhead("D");
sLinkedList.display();

sLinkedList.addTail("O");
sLinkedList.display();

sLinkedList.deleteHead();
sLinkedList.display();

sLinkedList.delete("B");
sLinkedList.display();
}

测试结果:

1
2
3
4
[D->C->B->A]
[D->C->B->A->O]
[C->B->A->O]
[C->A->O]

这边注意一个地方,addTail()是往链表的末尾添加一个元素,在进行判断current.next == null 后,要先将整体链表的size + 1,不要将size + 1放在循环外进行,才能够使current.next = newTail,否则将无法添加成功,因为容量不够。