2022.1.6

15832144755

2022-01-06 7b4c8991dca9cf2a809a95e239d144697d3afb56

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
import defined from "./defined.js";
 
/**
 * @private
 */
function DoublyLinkedList() {
  this.head = undefined;
  this.tail = undefined;
  this._length = 0;
}
 
Object.defineProperties(DoublyLinkedList.prototype, {
  length: {
    get: function () {
      return this._length;
    },
  },
});
 
/**
 * @private
 */
function DoublyLinkedListNode(item, previous, next) {
  this.item = item;
  this.previous = previous;
  this.next = next;
}
 
/**
 * Adds the item to the end of the list
 * @param {*} [item]
 * @return {DoublyLinkedListNode}
 */
DoublyLinkedList.prototype.add = function (item) {
  var node = new DoublyLinkedListNode(item, this.tail, undefined);
 
  if (defined(this.tail)) {
    this.tail.next = node;
    this.tail = node;
  } else {
    this.head = node;
    this.tail = node;
  }
 
  ++this._length;
 
  return node;
};
 
function remove(list, node) {
  if (defined(node.previous) && defined(node.next)) {
    node.previous.next = node.next;
    node.next.previous = node.previous;
  } else if (defined(node.previous)) {
    // Remove last node
    node.previous.next = undefined;
    list.tail = node.previous;
  } else if (defined(node.next)) {
    // Remove first node
    node.next.previous = undefined;
    list.head = node.next;
  } else {
    // Remove last node in the linked list
    list.head = undefined;
    list.tail = undefined;
  }
 
  node.next = undefined;
  node.previous = undefined;
}
 
/**
 * Removes the given node from the list
 * @param {DoublyLinkedListNode} node
 */
DoublyLinkedList.prototype.remove = function (node) {
  if (!defined(node)) {
    return;
  }
 
  remove(this, node);
 
  --this._length;
};
 
/**
 * Moves nextNode after node
 * @param {DoublyLinkedListNode} node
 * @param {DoublyLinkedListNode} nextNode
 */
DoublyLinkedList.prototype.splice = function (node, nextNode) {
  if (node === nextNode) {
    return;
  }
 
  // Remove nextNode, then insert after node
  remove(this, nextNode);
 
  var oldNodeNext = node.next;
  node.next = nextNode;
 
  // nextNode is the new tail
  if (this.tail === node) {
    this.tail = nextNode;
  } else {
    oldNodeNext.previous = nextNode;
  }
 
  nextNode.next = oldNodeNext;
  nextNode.previous = node;
};
export default DoublyLinkedList;