服务器之家

服务器之家 > 正文

Java中双向链表详解及实例

时间:2020-09-21 17:11     来源/作者:Dylansuns

Java双向链表详解及实例

写在前面:

  双向链表是一种对称结构,它克服了单链表上指针单向性的缺点,其中每一个节点即可向前引用,也可向后引用,这样可以更方便的插入、删除数据元素。

  由于双向链表需要同时维护两个方向的指针,因此添加节点、删除节点时指针维护成本更大;但双向链表具有两个方向的指针,因此可以向两个方向搜索节点,因此双向链表在搜索节点、删除指定索引处节点时具有较好的性能。

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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
package com.ietree.basic.datastructure.dublinklist;
 
/**
 * 双向链表
 *
 * @author Dylan
 */
public class DuLinkList<T> {
 
  // 定义一个内部类Node,Node实例代表链表的节点
  private class Node {
 
    // 保存节点的数据
    private T data;
    // 保存上个节点的引用
    private Node prev;
    // 指向下一个节点的引用
    private Node next;
 
    // 无参构造器
    public Node() {
    }
 
    // 初始化全部属性的构造器
    public Node(T data, Node prev, Node next) {
 
      this.data = data;
      this.prev = prev;
      this.next = next;
 
    }
 
  }
 
  // 保存该链表的头节点
  private Node header;
  // 保存该链表的尾节点
  private Node tail;
  // 保存该链表中已包含的节点数
  private int size;
 
  // 创建空链表
  public DuLinkList() {
 
    // 空链表,header和tail都是null
    header = null;
    tail = null;
 
  }
 
  // 以指定数据元素来创建链表,该链表只有一个元素
  public DuLinkList(T element) {
 
    header = new Node(element, null, null);
    // 只有一个节点,header、tail都指向该节点
    tail = header;
    size++;
 
  }
 
  // 返回链表的长度
  public int length() {
 
    return size;
 
  }
 
  // 获取链式线性表中索引为index处的元素
  public T get(int index) {
 
    return getNodeByIndex(index).data;
 
  }
 
  // 根据索引index获取指定位置的节点
  public Node getNodeByIndex(int index) {
 
    if (index < 0 || index > size - 1) {
 
      throw new IndexOutOfBoundsException("线性表索引越界");
 
    }
    if (index <= size / 2) {
 
      // 从header节点开始
      Node current = header;
      for (int i = 0; i <= size / 2 && current != null; i++, current = current.next) {
        if (i == index) {
 
          return current;
 
        }
      }
 
    } else {
 
      // 从tail节点开始搜索
      Node current = tail;
      for (int i = size - 1; i > size / 2 && current != null; i++, current = current.prev) {
        if (i == index) {
 
          return current;
 
        }
      }
 
    }
 
    return null;
  }
 
  // 查找链式线性表中指定元素的索引
  public int locate(T element) {
 
    // 从头结点开始搜索
    Node current = header;
    for (int i = 0; i < size && current != null; i++, current = current.next) {
 
      if (current.data.equals(element)) {
        return i;
      }
 
    }
    return -1;
 
  }
 
  // 向线性链表的指定位置插入一个元素
  public void insert(T element, int index) {
 
    if (index < 0 || index > size) {
      throw new IndexOutOfBoundsException("线性表索引越界");
    }
 
    // 如果还是空链表
    if (header == null) {
 
      add(element);
 
    } else {
 
      // 当index为0时,也就是在链表头处插入
      if (index == 0) {
 
        addAtHeader(element);
 
      } else {
 
        // 获取插入点的前一个节点
        Node prev = getNodeByIndex(index - 1);
        // 获取插入点的节点
        Node next = prev.next;
        // 让新节点的next引用指向next节点,prev引用指向prev节点
        Node newNode = new Node(element, prev, next);
        // 让prev的next节点指向新节点
        prev.next = newNode;
        // 让prev的下一个节点的prev指向新节点
        next.prev = newNode;
        size++;
      }
 
    }
 
  }
 
  // 采用尾插法为链表添加新节点
  public void add(T element) {
 
    // 如果该链表还是空链表
    if (header == null) {
 
      header = new Node(element, null, null);
      // 只有一个节点,header、tail都指向该节点
      tail = header;
 
    } else {
 
      // 创建新节点,新节点的pre指向原tail节点
      Node newNode = new Node(element, tail, null);
      // 让尾节点的next指向新增的节点
      tail.next = newNode;
      // 以新节点作为新的尾节点
      tail = newNode;
 
    }
    size++;
  }
 
  // 采用头插法为链表添加新节点
  public void addAtHeader(T element) {
    // 创建新节点,让新节点的next指向原来的header
    // 并以新节点作为新的header
    header = new Node(element, null, header);
    // 如果插入之前是空链表
    if (tail == null) {
 
      tail = header;
 
    }
    size++;
  }
 
  // 删除链式线性表中指定索引处的元素
  public T delete(int index) {
 
    if (index < 0 || index > size - 1) {
 
      throw new IndexOutOfBoundsException("线性表索引越界");
 
    }
    Node del = null;
    // 如果被删除的是header节点
    if (index == 0) {
 
      del = header;
      header = header.next;
      // 释放新的header节点的prev引用
      header.prev = null;
 
    } else {
 
      // 获取删除节点的前一个节点
      Node prev = getNodeByIndex(index - 1);
      // 获取将要被删除的节点
      del = prev.next;
      // 让被删除节点的next指向被删除节点的下一个节点
      prev.next = del.next;
      // 让被删除节点的下一个节点的prev指向prev节点
      if (del.next != null) {
 
        del.next.prev = prev;
 
      }
 
      // 将被删除节点的prev、next引用赋为null
      del.prev = null;
      del.next = null;
 
    }
    size--;
    return del.data;
  }
 
  // 删除链式线性表中最后一个元素
  public T remove() {
 
    return delete(size - 1);
 
  }
 
  // 判断链式线性表是否为空表
  public boolean empty() {
 
    return size == 0;
 
  }
 
  // 清空线性表
  public void clear() {
 
    // 将底层数组所有元素赋为null
    header = null;
    tail = null;
    size = 0;
 
  }
 
  public String toString() {
 
    // 链表为空链表
    if (empty()) {
 
      return "[]";
 
    } else {
 
      StringBuilder sb = new StringBuilder("[");
      for (Node current = header; current != null; current = current.next) {
 
        sb.append(current.data.toString() + ", ");
 
      }
      int len = sb.length();
      return sb.delete(len - 2, len).append("]").toString();
 
    }
 
  }
 
  // 倒序toString
  public String reverseToString() {
 
    if (empty()) {
 
      return "[]";
 
    } else {
 
      StringBuilder sb = new StringBuilder("[");
      for (Node current = tail; current != null; current = current.prev) {
 
        sb.append(current.data.toString() + ", ");
 
      }
      int len = sb.length();
      return sb.delete(len - 2, len).append("]").toString();
 
    }
 
  }
 
}
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
package com.ietree.basic.datastructure.dublinklist;
 
/**
 * 测试类
 *
 * @author Dylan
 */
public class DuLinkListTest {
 
  public static void main(String[] args) {
 
    DuLinkList<String> list = new DuLinkList<String>();
    list.insert("aaaa", 0);
    list.add("bbbb");
    list.insert("cccc", 0);
    // 在索引为1处插入一个新元素
    list.insert("dddd", 1);
    // 输出顺序线性表的元素
    System.out.println(list);
    // 删除索引为2处的元素
    list.delete(2);
    System.out.println(list);
    System.out.println(list.reverseToString());
    // 获取cccc字符串在顺序线性表中的位置
    System.out.println("cccc在顺序线性表中的位置:" + list.locate("cccc"));
    System.out.println("链表中索引1处的元素:" + list.get(1));
    list.remove();
    System.out.println("调用remove方法后的链表:" + list);
    list.delete(0);
    System.out.println("调用delete(0)后的链表:" + list);
 
  }
 
}
1
2
3
4
5
6
7
[cccc, dddd, aaaa, bbbb]
[cccc, dddd, bbbb]
[bbbb, dddd, cccc]
cccc在顺序线性表中的位置:0
链表中索引1处的元素:dddd
调用remove方法后的链表:[cccc, dddd]
调用delete(0)后的链表:[dddd]

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
返回顶部