本文实例讲述了Java数据结构之双端链表原理与实现方法。分享给大家供大家参考，具体如下：
一、概述：
1、什么时双端链表：
链表中保持这对最后一个连点引用的链表
2、从头部插入
要对链表进行判断，如果为空则设置尾节点为新添加的节点
3、从尾部进行插入
如果链表为空，则直接设置头节点为新添加的节点，否则设置尾节点的后一个节点为新添加的节点
4、从头部删除
判断节点是否有下个节点，如果没有则设置节点为null
二、具体实现
|
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
173
174
175
|
/** * @描述 头尾相接的链表 * @项目名称 Java_DataStruct * @包名 com.struct.linklist * @类名 LinkList * @author chenlin * @date 2010年6月26日 上午8:00:28 * @version 1.0 */public class FirstLastLinkList { //头 private Node first; //尾 private Node last; public FirstLastLinkList(){ first = null; last = null; } /** * 插入数据 * @param value */ public void insertFirst(long value){ Node newNode = new Node(value); if (first == null) { last = newNode; }else { //把first节点往下移动 newNode.next = first; } //把插入的节点作为新的节点 first = newNode; } /** * 插入数据 * @param value */ public void insertLast(long value){ Node newNode = new Node(value); if (first == null) { first = newNode; }else { last.next = newNode; } //把最后个节点设置为最新的节点 last = newNode; } public boolean isEmpty(){ return first == null; } /** * 删除头节点 * @param value * @return */ public Node deleteFirst(){ if (first == null) { throw new RuntimeException("链表数据不存在"); } if (first.next == null) { last = null; } Node temp = first; first = temp.next; return temp; } public Node deleteByKey(long key){ Node current = first; Node last = first; while(current.data != key){ if (current.next == null) { System.out.println("没找到节点"); return null; } last = current; current = current.next; } if (current == first) { //return deleteFirst(); //指向下个就表示删除第一个 first = first.next; }else { last.next = current.next; } return current; } /** * 显示所有的数据 */ public void display(){ if (first == null) { //throw new RuntimeException("链表数据不存在"); return; } Node current = first; while(current != null){ current.display(); current = current.next; } System.out.println("---------------"); } /** * 查找节点1 * @param value * @return */ public Node findByValue(long value){ Node current = first; while(current != null){ if (current.data != value) { current = current.next; }else { break; } } if (current == null) { System.out.println("没找到"); return null; } return current; } /** * 查找节点2 * * @param key * @return */ public Node findByKey(long key) { Node current = first; while (current.data != key) { if (current.next == null) { System.out.println("没找到"); return null; } current = current.next; } return current; } /** * 根据索引查找对应的值 * @param position * @return */ public Node findByPosition(int position){ Node current = first; //为什么是position - 1，因为要使用遍历，让current指向下一个， 所以position - 1的下个node就是要找的值 for (int i = 0; i < position - 1 ; i++) { current = current.next; } return current; } public static void main(String[] args) { FirstLastLinkList linkList = new FirstLastLinkList(); linkList.insertFirst(21); linkList.insertFirst(22); linkList.insertFirst(23); linkList.insertLast(24); linkList.insertLast(25); linkList.insertLast(26); linkList.insertLast(27); linkList.display(); System.out.println("---查找-------------------------------------"); linkList.findByKey(25).display(); System.out.println("--删除first-------------------------------------"); //linkList.deleteFirst().display(); ///linkList.deleteFirst().display(); //linkList.deleteFirst().display(); //linkList.deleteFirst().display(); System.out.println("-删除指定值---------------------------------------"); linkList.deleteByKey(27).display(); linkList.deleteByKey(21).display(); System.out.println("----------------------------------------"); linkList.display(); }} |
希望本文所述对大家java程序设计有所帮助。
原文链接：http://blog.csdn.net/lovoo/article/details/51762164
