-
Notifications
You must be signed in to change notification settings - Fork 0
/
DoubleLinkedList.ts
98 lines (85 loc) · 1.96 KB
/
DoubleLinkedList.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
import AbstractLinkedList from "../AbstractLinkedList/AbstractLinkedList";
import DoubleLinkedNode from "./DoubleLinkedNode";
/**
* Linear data structure
* Each node has next and prev sibling
* Head and tail are linked to each other
*/
export default class DoubleLinkedList<T> extends AbstractLinkedList<T> {
/**
* Override types
*/
protected _head: DoubleLinkedNode<T> | null;
protected _tail: DoubleLinkedNode<T> | null;
/**
* @inheritDoc
*/
public constructor(capacity?: number) {
super(capacity);
this._head = null;
this._tail = null;
}
/**
* @inheritDoc
*/
protected createNode(value: T): DoubleLinkedNode<T> {
return new DoubleLinkedNode<T>(value);
}
/**
* @inheritDoc
*/
protected insertNodeBetweenTwoNodesImpl(
targetNode: DoubleLinkedNode<T>,
leftNode: DoubleLinkedNode<T>,
rightNode: DoubleLinkedNode<T>
): void {
targetNode.next = rightNode;
targetNode.prev = leftNode;
if (targetNode.prev) {
targetNode.prev.next = targetNode;
}
if (targetNode.next) {
targetNode.next.prev = targetNode;
}
}
/**
* @inheritDoc
*/
protected deleteNodeImpl(node: DoubleLinkedNode<T>): void {
node!.prev!.next = node!.next;
node!.next!.prev = node!.prev;
node!.next = null;
node!.prev = null;
}
/**
* @inheritDoc
*/
protected popImpl(): void {
this._head = this._tail?.prev || null;
}
/**
* @inheritDoc
*/
protected shiftImpl(): void {
this._tail = this._head?.next || null;
}
/**
* @inheritDoc
*/
public reverse(): void {
let currentNode = this._tail;
let i = 0;
while (currentNode && i < this._length) {
const newPrev = currentNode.next;
const newNext = currentNode.prev;
currentNode.prev = newPrev;
currentNode.next = newNext;
i++;
currentNode = newNext;
}
if (currentNode) {
this._tail = currentNode.next;
this._head = currentNode;
}
}
}