LinkedList

链表

链表是最基础的数据结构之一,简单可以理解为自行车上的车链,一个纽扣下一个扣,一个Node连着下一个Node。
相对于数组的好处是,方便扩充,不用提前分配内存。
链表的节点:链表的节点(Node)起码包含两个元素,键值和下个一个节点(Node)。

1
2
3
4
5
struct LinkedList_Node
{
int m_key;
LinkedList_Node* pNextNode;
}

链表的生成

由于链表是一环扣一环的,所以首节点即可表示整个链表。下面是如何生成一个链表(c++),以节点为10的链表为例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void CreateLinkedList(Linkedlist_Node* pHeadNode)
{

LinkedList_Node* p = pHeadnode;
for (int i=1; i<10; i++) //创建另外9个节点
{
ListNode* pNewNode = new LinkedList_Node;
pNewNode -> m_key = i;
pNewNode -> pNextNode = NULL;
p -> pNextNode = pNewNode;
p = pNewNode;
}
}

int main()
{

LinkedList_Node* head = NULL;
head = new LinkedList_Node; //c++中struct的初始化不用加(),毕竟不是class
head -> m_key =0; //初始化首节点
head -> pNextNode = NULL;
CreateLinkedList(head);

return 0;
}

以下链表的java实现,链表的节点:

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
package com.xtfggef.algo.linkedlist;

public class LinkedList<T> {

/**
* class node
* @author wanghuan
* @param <T>
*/

private static class Node<T> {
T data;
Node<T> next;

Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}

Node(T data) {
this(data, null);
}
}

// data
private Node<T> head, tail;

public LinkedList() {
head = tail = null;
}

/**
* judge the list is empty
*/

public boolean isEmpty() {
return head == null;
}

/**
* add head node
*/

public void addHead(T item) {
head = new Node<T>(item);
if (tail == null)
tail = head;
}

/**
* add the tail pointer
*/

public void addTail(T item) {
if (!isEmpty()) {
tail.next = new Node<T>(item);
tail = tail.next;
} else {
head = tail = new Node<T>(item);
}
}

/**
* print the list
*/

public void traverse() {
if (isEmpty()) {
System.out.println("null");
} else {
for (Node<T> p = head; p != null; p = p.next)
System.out.println(p.data);
}
}

/**
* insert node from head
*/

public void addFromHead(T item) {
Node<T> newNode = new Node<T>(item);
newNode.next = head;
head = newNode;
}

/**
* insert node from tail
*/

public void addFromTail(T item) {
Node<T> newNode = new Node<T>(item);
Node<T> p = head;
while (p.next != null)
p = p.next;
p.next = newNode;
newNode.next = null;
}

/**
* delete node from head
*/

public void removeFromHead() {
if (!isEmpty())
head = head.next;
else
System.out.println("The list have been emptied!");
}

/**
* delete frem tail, lower effect
*/

public void removeFromTail() {
Node<T> prev = null, curr = head;
while (curr.next != null) {
prev = curr;
curr = curr.next;
if (curr.next == null)
prev.next = null;
}
}

/**
* insert a new node
* @param appointedItem
* @param item
* @return
*/

public boolean insert(T appointedItem, T item) {
Node<T> prev = head, curr = head.next, newNode;
newNode = new Node<T>(item);
if (!isEmpty()) {
while ((curr != null) && (!appointedItem.equals(curr.data))) {
prev = curr;
curr = curr.next;
}
newNode.next = curr;
prev.next = newNode;
return true;
}
return false;
}

public void remove(T item) {
Node<T> curr = head, prev = null;
boolean found = false;
while (curr != null && !found) {
if (item.equals(curr.data)) {
if (prev == null)
removeFromHead();
else
prev.next = curr.next;
found = true;
} else {
prev = curr;
curr = curr.next;
}
}
}


public int indexOf(T item) {
int index = 0;
Node<T> p;
for (p = head; p != null; p = p.next) {
if (item.equals(p.data))
return index;
index++;

}
return -1;
}

/**
* judge the list contains one data
*/

public boolean contains(T item) {
return indexOf(item) != -1;
}
}

链表的删除

删除链表,遍历一下这个链表,使用delete删除即可。c++中所有new初始化的实例,都使用delete来删除。释放内存。