-
Notifications
You must be signed in to change notification settings - Fork 3
/
ExtendedDoublyLinkedList.ts
121 lines (96 loc) · 2.71 KB
/
ExtendedDoublyLinkedList.ts
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
import { DoublyLinkedList, DoublyLinkedListNode } from '@datastructures-js/linked-list';
export class ExtendedDoublyLinkedList<T> extends DoublyLinkedList<T> {
setHead(newHead: DoublyLinkedListNode<T> | null) {
// @ts-ignore
this._head = newHead;
}
setTail(newTail: DoublyLinkedListNode<T> | null) {
// @ts-ignore
this._tail = newTail;
}
setCount(newCount: number) {
// @ts-ignore
this._count = newCount;
}
insertBeforeForNode(value: DoublyLinkedListNode<T>, node: DoublyLinkedListNode<T> | null): DoublyLinkedListNode<T> {
if (node === null) {
return this.insertLastForNode(value);
}
if (node === this.head()) {
return this.insertFirstForNode(value);
}
value.setNext(node);
value.setPrev(node.getPrev());
value.getNext().setPrev(value);
value.getPrev().setNext(value);
this.setCount(this.count() + 1);
return value;
}
insertBefore(value: T, node: DoublyLinkedListNode<T> | null): DoublyLinkedListNode<T> {
if (node === null) {
return this.insertLast(value);
}
if (node === this.head()) {
return this.insertFirst(value);
}
const newNode = new DoublyLinkedListNode(value);
newNode.setNext(node);
newNode.setPrev(node.getPrev());
newNode.getNext().setPrev(newNode);
newNode.getPrev().setNext(newNode);
this.setCount(this.count() + 1);
return newNode;
}
insertAfter(value: T, node: DoublyLinkedListNode<T> | null): DoublyLinkedListNode<T> {
if (node === null || node === this.tail()) {
return this.insertLast(value);
}
const newNode = new DoublyLinkedListNode(value);
newNode.setPrev(node);
newNode.setNext(node.getNext());
newNode.getNext().setPrev(newNode);
newNode.getPrev().setNext(newNode);
this.setCount(this.count() + 1);
return newNode;
}
insertFirstForNode(newNode: DoublyLinkedListNode<T>) {
if (this.isEmpty()) {
this.setHead(newNode);
this.setTail(newNode);
} else {
this.head().setPrev(newNode);
newNode.setNext(this.head());
this.setHead(newNode);
}
this.setCount(this.count() + 1);
return newNode;
}
countAfterNode(node: DoublyLinkedListNode<T> | null, before?: DoublyLinkedListNode<T>): number {
let count = 0;
let currentNode = node;
while (currentNode !== null && (!before || currentNode !== before)) {
count++;
currentNode = currentNode.getNext();
}
return count;
}
/**
* Adds a node at the end of the list.
*
* @public
* @param {any} value
* @returns {DoublyLinkedListNode}
*/
insertLastForNode(newNode: DoublyLinkedListNode<T>) {
if (this.isEmpty()) {
this.setHead(newNode);
this.setTail(newNode);
} else {
newNode.setPrev(this.tail());
this.tail().setNext(newNode);
this.setTail(newNode);
}
this.setCount(this.count() + 1);
return newNode;
}
}