1.链表
一个链结点是某个类的对象，这个类叫做Link。每个Link对象中都包含一个对下一个链结点引用的字段（叫做next）
|
1
2
3
4
5
|
public
class
Link {
public
int
iData;
public
double
dData;
public
Link next;
}
|
它包含了一些数据和下一个链结点的引用。
通常，用一个包含这些数据的类的对象来代替这些数据项。
|
1
2
3
4
|
public
class
Link {
public
inventoryItem iI;
public
Link next;
}
|
引用和基本类型
类型为Link的next字段仅仅是对另一个Link对象的“引用”，而不是一个对象。Link对象并没有真正包含另一个Link对象。
|
1
|
Link someLink =
new
Link();
|
somelink字段没有真正的一个对象，它是一个引用。
|
1
|
Link aLink = someLink;
|
2.单链表
|
1
2
3
|
public
class
LinkList {
private
Link first;
}
|
Link first表示指向链表中的第一个链结点。
在链表头出入一个数据项
为了插入新链结点，只需要使新创建的链结点的next字段指向原来的first，然后改变first，使它指向新创建的链结点。
|
1
2
3
4
5
|
public
void
insertFirst() {
Link newLink =
new
Link();
newLink.next = first;
// newLink > old first
first = newLink;
// first > newLink
}
|
在链表头删除一个数据项
通过把first指向第二个链接点，断开和第一个连接点的连接。
|
1
2
3
4
5
|
public
Link deleteFirst() {
Link temp = first;
first = first.next;
// delete it:firts > old next
return
temp;
// return deleted link
}
|
遍历链表显示它的内容
从first开始，沿着引用链从一个链结点到下一个连接点。变量current按顺序指向每一个链结点。
|
1
2
3
4
5
6
7
|
public
void
display() {
Link current = first;
while
(current !=
null
) {
current = current.next;
System.out.println(current.iI);
}
}
|
3.双端链表
双端链表增加了对最后一个链结点的引用。双端链表类叫做FirstLastList，它由两个项，first和last，一个指向链表中的第一个链结点，另一个指向最后一个链结点。如果链表只有一个链结点，first和last都指向它，如果没有连接点，两者都为null。
双向链表很形象个U。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public
class
FirstLastList {
private
Link first;
private
Link last;
public
void
insertFirst() {
Link newLink =
new
Link();
if
(first ==
null
)
last = newLink;
newLink.next = first;
first = newLink;
}
public
void
insertLast() {
Link newLink =
new
Link();
if
(first ==
null
)
first = newLink;
else
last.next = newLink;
last = newLink;
}
}
|
链表的效率
在表头插入和删除速度很快快，时间复杂度O(1)。
4.有序链表
有序链表：数据是按照关键值有序排序的。
有序链表优于有序数组的地方是插入速度（因为元素不需要移动），另外链表可以扩展到全部有效地使用内存。
有序链表是优先级队列和堆的常用实现方法。
在有序链表中插入一个数据项
为了在一个有序链表中插入数据项，算法必须首先搜索链表，找到合适的位置：它恰好在第一个比它大的数据想的前面。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public
class
SortedList {
private
Link first;
public
void
insert(
long
key) {
Link newLink =
new
Link();
Link previous =
null
;
Link current = first;
while
(current !=
null
&& key > current.dData) {
previous = current;
current = current.next;
}
if
(previous ==
null
)
first = newLink;
else
previous.next = current;
}
}
|
有序链表的效率
在有序链表插入和删除某一项最多需要O(N)次比较。
5.双向链表
双向链表即允许向前遍历，也允许向后遍历整个链表。每个链结点都有两个指向其他连接点的引用，一个指向下一个链结点，另一个指向前一个链结点。
|
1
2
3
4
5
|
public
class
Link {
public
double
dData;
public
Link next;
public
Link previous;
}
|
双向链表的缺点是每次插入或删除一个链结点的时候，都要处理四个链结点的引用。双向链表不必是双端链表。
|
1
2
3
4
|
class
doublyLinked {
private
Link first;
private
Link last;
}
|
Link first表示指向链表中的第一个链结点。对first的操作就是对链表第一个连接点的操作，因为他们都指向同一个对象。
Link last表示指向链表中的最后一个链结点。
插入
|
1
2
3
4
5
6
7
8
9
|
public
void
insertFirst() {
Link newLink =
new
Link();
if
(first ==
null
)
last = newLink;
else
first.previous = newLink;
newLink.next = first;
first = newLink;
}
|
insertFirst方法把原来first指向的链结点的previous字段指向新链结点，并把新链结点的next字段指向前者。最后把first指向新连接点。
|
1
2
3
4
5
6
7
8
9
10
|
public
void
insertLast() {
Link newLink =
new
Link();
if
(first ==
null
)
first = newLink;
else
{
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}
|
删除
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public
Link deleteFirst() {
Link temp = first;
if
(first.next ==
null
)
last =
null
;
else
first.next.previous =
null
;
first = first.next;
return
temp;
}
public
Link deleteLast() {
Link temp = last;
if
(first.next ==
null
)
first =
null
;
else
last.previous.next =
null
;
last = last.previous;
return
temp;
}
|
