双向链表的代码实现

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
package com.liuzhen;
//双向链表
public class Linked2<E> {
Node<E> first;// 头节点
Node<E> last;// 尾节点
int size;// 链表长度
/*
* 添加新结点（头插法）
*/
public void linkerFirst(E e) {
// 获取当前头结点
final Node<E> f = first;
// 创建新的头结点
final Node<E> newNode = new Node<E>(null, e, f);
// 设置链表的新头结点
first = newNode;
if (f == null) {
// 同时设置尾节点
last = newNode;
} else {
// 设置旧头结点的前驱=>新头结点
f.prev = newNode;
// 链表长度自增
size++;
}
}
// 尾插法
public void linkLast(E e) {
// 获取当前链表尾节点
final Node<E> l = last;
// 创建新的尾节点
final Node<E> newNode = new Node<E>(l, e, null);
// 设置新的尾结点
last = newNode;
if (l == null) {
// 同时设置头结点
first = newNode;
} else {
// 设置旧的尾结点的后继为新为新尾结点
l.next = newNode;
size++;
}
}
/*
* 根据下标位置查找结点
*/
public Node<E> node(int index) {
// 判断下标位置在上半区或下半区，进行折半查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
// 下半区
Node<E> x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}
/*
* 删除头结点
*/
public void removeFirst() {
// 获取头结点
final Node<E> f = first;
// 获取头节点的下一个结点
final Node<E> next = f.next;
// 清空头结点
f.iem = null;
f.next = null;
// 设置链表的头结点
first = next;
if (next == null) {
last = null;
} else {
next.prev = null;
// 链表长度自减
size--;
}
}
/*
* 删除尾巴节点
*/
public void removeLast() {
// 获取尾巴节点
final Node<E> l = last;
// 获取尾结点的前驱结点
final Node<E> prev = l.prev;
// 清空尾节点
l.iem = null;
l.prev = null;
// 设置尾节点
last = prev;
if (prev == null) {
first = null;
} else {
prev.next = null;
size--;
}
}
static class Node<E> {
E iem;// 数据域
Node<E> next;// 后继结点
Node<E> prev;// 前驱结点
// 构造方法
// 参数1：前驱结点
// 参数2：数据域
// 参数3：后继结点
public Node(Node<E> prev, E iem, Node<E> next) {
this.iem = iem;
this.next = next;
this.prev = prev;
}
}
}

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
package com.liuzhen;
import com.liuzhen.Linked2.Node;
public class Text2 {
public static void main(String[] args) {
Linked2<String> link = new Linked2<String>();
link.linkerFirst("A");// 头插法
link.linkerFirst("B");
link.linkerFirst("C");
link.linkerFirst("D");
link.linkerFirst("E");
link.linkLast("天");// 尾插法
link.linkLast("王");
link.linkLast("盖");
link.linkLast("地");
link.linkLast("虎");
//删除头结点
link.removeFirst();
//删除尾巴结点
link.removeLast();
for (Linked2.Node<String> node = link.first; node != null; node = node.next) {
System.out.println(node.iem);
}
Node<String> s = link.node(6);
System.out.println("第六个元素："+s.iem);
Node<String> s2 = link.node(9);
System.out.println("第9个元素："+s2.iem);
}
}