Fancy DSA Fancy DSA
数据结构
算法
LeetCode
  • 关于
  • 导航 (opens new window)
  • 分类
  • 标签
  • 归档
设计模式 (opens new window)
博客 (opens new window)
GitHub (opens new window)

Jonsam NG

想的更多,也要想的更远
数据结构
算法
LeetCode
  • 关于
  • 导航 (opens new window)
  • 分类
  • 标签
  • 归档
设计模式 (opens new window)
博客 (opens new window)
GitHub (opens new window)
  • 开始上手
  • Plan 计划
  • Roadmap 路线
  • 术语表
  • 数据结构简介
  • queue 队列

  • heap 堆

  • linked-list 链表

    • LinkedList [链表]
    • DoublyLinkedList [双向链表]
      • 介绍
      • 实现
      • 参考
    • SinglyCircularLinkedList [单项循环链表]
  • stack 栈

  • set 集合

  • graph 图

  • tree 树

  • vectors 矢量

  • 数据结构
  • linked-list 链表
jonsam
2022-04-26
目录

DoublyLinkedList [双向链表]

# 介绍

双向链表,又称为双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

image

# 实现

# JavaScript

class DoublyLinkedListNode {
  /**
   * Creates a doubly linked list node.
   * @param {any} value
   * @param {DoublyLinkedListNode} [prev]
   * @param {DoublyLinkedListNode} [next]
   */
  constructor(value, prev, next) {
    this._value = value;
    this.setPrev(prev);
    this.setNext(next);
  }

  /**
   * @public
   * @param {object} value
   */
  setValue(value) {
    this._value = value;
    return this;
  }

  /**
   * @public
   * @returns {object}
   */
  getValue() {
    return this._value;
  }

  /**
   * @public
   * @param {DoublyLinkedListNode} [next]
   * @returns {DoublyLinkedListNode}
   */
  setNext(next) {
    if (next && !(next instanceof DoublyLinkedListNode)) {
      throw new Error('setNext expects a DoublyLinkedListNode or null');
    }
    this._next = next || null;
    return this;
  }

  /**
   * @public
   * @returns {DoublyLinkedListNode}
   */
  getNext() {
    return this._next;
  }

  /**
   * @public
   * @returns {boolean}
   */
  hasNext() {
    return this._next instanceof DoublyLinkedListNode;
  }

  /**
   * @public
   * @param {DoublyLinkedListNode} [prev]
   * @returns {DoublyLinkedList}
   */
  setPrev(prev) {
    if (prev && !(prev instanceof DoublyLinkedListNode)) {
      throw new Error('setPrev expects a DoublyLinkedListNode or null');
    }
    this._prev = prev || null;
    return this;
  }

  /**
   * @public
   * @returns {DoublyLinkedListNode}
   */
  getPrev() {
    return this._prev;
  }

  /**
   * @public
   * @returns {boolean}
   */
  hasPrev() {
    return this._prev instanceof DoublyLinkedListNode;
  }
}

class DoublyLinkedList {
  constructor() {
    this._head = null;
    this._tail = null;
    this._count = 0;
  }

  /**
   * Adds a node at the beginning of the list.
   * @public
   * @param {any} value
   * @returns {DoublyLinkedListNode}
   */
  insertFirst(value) {
    const newNode = new DoublyLinkedListNode(value);

    if (this.isEmpty()) {
      this._head = newNode;
      this._tail = newNode;
    } else {
      this._head.setPrev(newNode);
      newNode.setNext(this._head);
      this._head = newNode;
    }
    this._count += 1;
    return newNode;
  }

  /**
   * Adds a node at the end of the list.
   * @public
   * @param {any} value
   * @returns {DoublyLinkedListNode}
   */
  insertLast(value) {
    const newNode = new DoublyLinkedListNode(value);
    if (this.isEmpty()) {
      this._head = newNode;
      this._tail = newNode;
    } else {
      newNode.setPrev(this._tail);
      this._tail.setNext(newNode);
      this._tail = newNode;
    }
    this._count += 1;
    return newNode;
  }

  /**
   * Adds a node at a specific position.
   * @public
   * @param {number} position
   * @param {any} value
   * @returns {DoublyLinkedListNode}
   */
  insertAt(position, value) {
    if (
      Number.isNaN(+position)
      || position < 0 || position > this._count
    ) {
      throw new Error('.insertAt expects a position num <= linked list size');
    }

    if (position === 0) {
      return this.insertFirst(value);
    }

    if (position === this._count) {
      return this.insertLast(value);
    }

    let currentPosition = 1;
    let prev = this._head;
    while (currentPosition < position) {
      currentPosition += 1;
      prev = prev.getNext();
    }

    const newNode = new DoublyLinkedListNode(value);
    newNode.setNext(prev.getNext());
    newNode.setPrev(prev);
    newNode.getNext().setPrev(newNode);
    newNode.getPrev().setNext(newNode);
    this._count += 1;
    return newNode;
  }

  /**
   * Removes the head node.
   * @public
   * @returns {DoublyLinkedListNode}
   */
  removeFirst() {
    if (this.isEmpty()) return null;

    const removedNode = this._head;
    if (this._head.hasNext()) {
      this._head = this._head.getNext();
      this._head.setPrev(null);
    } else {
      this._head = null;
      this._tail = null;
    }
    this._count -= 1;
    return removedNode.setNext(null);
  }

  /**
   * Removes the tail node.
   * @public
   * @returns {DoublyLinkedListNode}
   */
  removeLast() {
    if (this.isEmpty()) return null;

    const removedNode = this._tail;
    if (this._tail.hasPrev()) {
      this._tail = this._tail.getPrev();
      this._tail.setNext(null);
    } else {
      this._head = null;
      this._tail = null;
    }
    this._count -= 1;
    return removedNode.setPrev(null);
  }

  /**
   * Removes a node in a specific position.
   * @public
   * @param {number} position
   * @returns {DoublyLinkedListNode}
   */
  removeAt(position) {
    if (
      Number.isNaN(+position)
      || position < 0
      || position >= this._count
    ) {
      return null;
    }

    if (position === 0) {
      return this.removeFirst();
    }

    if (position === this._count - 1) {
      return this.removeLast();
    }

    let currentPosition = 1;
    let current = this._head.getNext();
    while (currentPosition < position) {
      currentPosition += 1;
      current = current.getNext();
    }
    return this.remove(current);
  }

  /**
   * Removes a node from the list by its reference.
   * @public
   * @param {DoublyLinkedListNode} node
   * @returns {DoublyLinkedListNode}
   */
  remove(node) {
    if (node && !(node instanceof DoublyLinkedListNode)) {
      throw new Error('remove: expects a DoublyLinkedListNode node');
    }

    if (!node) {
      return null;
    }

    if (!node.hasPrev()) {
      return this.removeFirst();
    }

    if (!node.hasNext()) {
      return this.removeLast();
    }

    node.getPrev().setNext(node.getNext());
    node.getNext().setPrev(node.getPrev());
    this._count -= 1;
    return node.setPrev(null).setNext(null);
  }

  /**
   * Removes all nodes based on a callback.
   * @public
   * @param {function} cb
   * @returns {number} number of removed nodes
   */
  removeEach(cb) {
    if (typeof cb !== 'function') {
      throw new Error('.removeEach(cb) expects a callback');
    }

    let removedCount = 0;
    let position = 0;
    let current = this._head;
    while (current instanceof DoublyLinkedListNode) {
      if (cb(current, position)) {
        const next = current.getNext();
        this.remove(current);
        removedCount += 1;
        current = next;
      } else {
        current = current.getNext();
      }
      position += 1;
    }
    return removedCount;
  }

  /**
   * Traverses the list from beginning to end.
   * @public
   * @param {function} cb
   */
  forEach(cb) {
    if (typeof cb !== 'function') {
      throw new Error('.forEach(cb) expects a callback');
    }

    let current = this._head;
    let position = 0;
    while (current instanceof DoublyLinkedListNode) {
      cb(current, position);
      position += 1;
      current = current.getNext();
    }
  }

  /**
   * Traverses the list backward from end to beginning
   * @public
   * @param {function} cb
   */
  forEachReverse(cb) {
    if (typeof cb !== 'function') {
      throw new Error('.forEachReverse(cb) expects a callback');
    }

    let current = this._tail;
    let position = this._count - 1;
    while (current instanceof DoublyLinkedListNode) {
      cb(current, position);
      position -= 1;
      current = current.getPrev();
    }
  }

  /**
   * Finds a node in the list using a callback
   * @public
   * @param {function} cb
   * @param {DoublyLinkedListNode} [startingNode]
   * @returns {DoublyLinkedListNode}
   */
  find(cb, startingNode = this._head) {
    if (typeof cb !== 'function') {
      throw new Error('.find(cb) expects a callback');
    }

    if (startingNode && !(startingNode instanceof DoublyLinkedListNode)) {
      throw new Error('.find(cb) expects to start from a DoublyLinkedListNode');
    }

    let current = startingNode;
    while (current instanceof DoublyLinkedListNode) {
      if (cb(current)) {
        return current;
      }
      current = current.getNext();
    }
    return null;
  }

  /**
   * Finds a node in the list using a callback in reverse order
   * @public
   * @param {function} cb
   * @param {DoublyLinkedListNode} [startingNode]
   * @returns {DoublyLinkedListNode}
   */
  findReverse(cb, startingNode = this._tail) {
    if (typeof cb !== 'function') {
      throw new Error('.findReverse(cb) expects a callback');
    }

    if (startingNode && !(startingNode instanceof DoublyLinkedListNode)) {
      throw new Error('.findReverse(cb) expects to start from a DoublyLinkedListNode');
    }

    let current = startingNode;
    while (current instanceof DoublyLinkedListNode) {
      if (cb(current)) {
        return current;
      }
      current = current.getPrev();
    }
    return null;
  }

  /**
   * Filters the list based on a callback.
   * @public
   * @param {function} cb
   * @returns {LinkedList}
   */
  filter(cb) {
    if (typeof cb !== 'function') {
      throw new Error('.filter(cb) expects a callback');
    }

    const result = new DoublyLinkedList();
    this.forEach((node, position) => {
      if (!cb(node, position)) return;
      result.insertLast(node.getValue());
    });
    return result;
  }

  /**
   * Returns the head node.
   * @public
   * @returns {DoublyLinkedListNode}
   */
  head() {
    return this._head;
  }

  /**
   * Returns the tail node.
   * @public
   * @returns {DoublyLinkedListNode}
   */
  tail() {
    return this._tail;
  }

  /**
   * Returns the nodes count in the list.
   * @public
   * @returns {number}
   */
  count() {
    return this._count;
  }

  /**
   * Converts the doubly linked list into an array.
   * @public
   * @returns {array}
   */
  toArray() {
    const result = [];
    this.forEach((node) => result.push(node.getValue()));
    return result;
  }

  /**
   * Checks if the list is empty.
   * @public
   * @returns {boolean}
   */
  isEmpty() {
    return this._head === null;
  }

  /**
   * Clears the list
   * @public
   */
  clear() {
    this._head = null;
    this._tail = null;
    this._count = 0;
  }

  /**
   * Creates a doubly linked list from an array
   * @public
   * @static
   * @param {array} values
   * @return {DoublyLinkedList}
   */
  static fromArray(values) {
    if (!Array.isArray(values)) {
      throw new Error('cannot create DoublyLinkedList from none-array values');
    }

    const doublyLinkedList = new DoublyLinkedList();
    values.forEach((value) => {
      doublyLinkedList.insertLast(value);
    });
    return doublyLinkedList;
  }
}
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
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490

或者:

class Node {
  constructor (element) {
    this.element = element
    this.next = null
    this.prev = null
  }
}

class DoubleLinkedList {
  constructor () {
    this.length = 0
    this.head = null
    this.tail = null
  }

  // Add new element
  append (element) {
    const node = new Node(element)

    if (!this.head) {
      this.head = node
      this.tail = node
    } else {
      node.prev = this.tail
      this.tail.next = node
      this.tail = node
    }

    this.length++
  }

  // Add element
  insert (position, element) {
    // Check of out-of-bound values
    if (position >= 0 && position <= this.length) {
      const node = new Node(element)
      let current = this.head
      let previous = 0
      let index = 0

      if (position === 0) {
        if (!this.head) {
          this.head = node
          this.tail = node
        } else {
          node.next = current
          current.prev = node
          this.head = node
        }
      } else if (position === this.length) {
        current = this.tail
        current.next = node
        node.prev = current
        this.tail = node
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }

        node.next = current
        previous.next = node

        // New
        current.prev = node
        node.prev = previous
      }

      this.length++
      return true
    } else {
      return false
    }
  }

  // Remove element at any position
  removeAt (position) {
    // look for out-of-bounds value
    if (position > -1 && position < this.length) {
      let current = this.head
      let previous = 0
      let index = 0

      // Removing first item
      if (position === 0) {
        this.head = current.next

        // if there is only one item, update this.tail //NEW
        if (this.length === 1) {
          this.tail = null
        } else {
          this.head.prev = null
        }
      } else if (position === this.length - 1) {
        current = this.tail
        this.tail = current.prev
        this.tail.next = null
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }

        // link previous with current's next - skip it
        previous.next = current.next
        current.next.prev = previous
      }

      this.length--
      return current.element
    } else {
      return null
    }
  }

  // Get the indexOf item
  indexOf (elm) {
    let current = this.head
    let index = -1

    // If element found then return its position
    while (current) {
      if (elm === current.element) {
        return ++index
      }

      index++
      current = current.next
    }

    // Else return -1
    return -1
  }

  // Find the item in the list
  isPresent (elm) {
    return this.indexOf(elm) !== -1
  }

  // Delete an item from the list
  delete (elm) {
    return this.removeAt(this.indexOf(elm))
  }

  // Delete first item from the list
  deleteHead () {
    this.removeAt(0)
  }

  // Delete last item from the list
  deleteTail () {
    this.removeAt(this.length - 1)
  }

  // Print item of the string
  toString () {
    let current = this.head
    let string = ''

    while (current) {
      string += current.element + (current.next ? '\n' : '')
      current = current.next
    }

    return string
  }

  // Convert list to array
  toArray () {
    const arr = []
    let current = this.head

    while (current) {
      arr.push(current.element)
      current = current.next
    }

    return arr
  }

  // Check if list is empty
  isEmpty () {
    return this.length === 0
  }

  // Get the size of the list
  size () {
    return this.length
  }

  // Get the this.head
  getHead () {
    return this.head
  }

  // Get the this.tail
  getTail () {
    return this.tail
  }

  // Method to iterate over the LinkedList
  iterator () {
    let currentNode = this.getHead()
    if (currentNode === null) return -1

    const iterate = function * () {
      while (currentNode) {
        yield currentNode.element
        currentNode = currentNode.next
      }
    }
    return iterate()
  }

  // Method to log the LinkedList, for debugging
  // it' a circular structure, so can't use stringify to debug the whole structure
  log () {
    let currentNode = this.getHead()
    while (currentNode) {
      console.log(currentNode.element)
      currentNode = currentNode.next
    }
  }
}
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

# 参考

  • 双向链表 - 维基百科,自由的百科全书 (opens new window)
编辑 (opens new window)
上次更新: 2022/10/11, 17:42:20
LinkedList [链表]
SinglyCircularLinkedList [单项循环链表]

← LinkedList [链表] SinglyCircularLinkedList [单项循环链表]→

最近更新
01
0-20题解
10-31
02
本章导读
10-31
03
算法与转换:Part1
10-28
更多文章>
Theme by Vdoing | Copyright © 2022-2022 Fancy DSA | Made by Jonsam by ❤
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式