概念
链表不需要连续的内存，通过指针将零散的内存块关联起来。
数组与链表的比较
最直观的比较是数组是连续的内存块，而链表不需要连续。
性能比较：
常见分类
常见的链表有单链表，双向链表，循环链表，双向循环链表等。
单链表
顾名思义，单链表是单方向的，链表由数据结点和后继指针组成。
特点
循环链表
双向链表
双向循环链表
特性
编码
实现一个简单的单链表。
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
|
case class NodeT
class HiLinkedList[T >: Null] {
var head: Node[T] = _
var tail: Node[T] = _
var size = 0
def add(data: T): Unit = {
if (head == null) {
head = Node(data, null)
tail = head
} else {
val node = Node(data, null)
tail.next = node
tail = node
}
size += 1
println(“Adding Action succeed！size is “, size)
}
def find(data: T): Node[T] = {
var tmp = head
while (tmp != null) {
println(“loop..”)
println(tmp.data)
if (tmp.data == data) {
return tmp
} else {
tmp = tmp.next
}
}
null
}
def remove(data: T): Node[T] = {
val node = find(data)
var tmp = head
if (tmp.data == data) {
head = tmp.next
size -= 1
} else {
if (node != null) {
while (tmp != null) {
println(“remove loop..”)
if (tmp.next == node) {
tmp.next = node.next
size -= 1
return node
}
tmp = tmp.next
}
}
}
node
}
}
|
样例
此处使用scala实现常见的链表样例。
LRU
回文
