Skip to content

Commit d079035

Browse files
hojashojas
committed
DoublyLinkedList
1 parent 8f87b1e commit d079035

File tree

9 files changed

+329
-37
lines changed

9 files changed

+329
-37
lines changed

‎.nvmrc

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
20

‎index.html

Lines changed: 0 additions & 13 deletions
This file was deleted.

‎package.json

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -4,10 +4,9 @@
44
"version": "1.0.0",
55
"private": true,
66
"packageManager": "pnpm@8.14.0",
7+
"license": "MIT",
78
"scripts": {
8-
"dev": "vite",
9-
"build": "tsc && vite build",
10-
"preview": "vite preview",
9+
"lint": "eslint .",
1110
"test": "vitest"
1211
},
1312
"devDependencies": {

‎public/vite.svg

Lines changed: 0 additions & 1 deletion
This file was deleted.

‎src/data-structures/doubly-linked-list/DoublyLinkedList.test.ts

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { DoublyLinkedList } from './DoublyLinkedList'
3+
4+
describe('doublyLinkedList', () => {
5+
it('should create empty doubly linked list', () => {
6+
const doublyLinkedList = new DoublyLinkedList()
7+
8+
expect(doublyLinkedList.toString()).toBe('')
9+
})
10+
11+
it('should prepend node to doubly linked list', () => {
12+
const doublyLinkedList = new DoublyLinkedList()
13+
14+
doublyLinkedList.prepend(1)
15+
expect(doublyLinkedList.toString()).toBe('1')
16+
17+
doublyLinkedList.prepend(2)
18+
expect(doublyLinkedList.toString()).toBe('2,1')
19+
})
20+
21+
it('should append node to doubly linked list', () => {
22+
const doublyLinkedList = new DoublyLinkedList()
23+
24+
doublyLinkedList.append(1)
25+
expect(doublyLinkedList.toString()).toBe('1')
26+
27+
doublyLinkedList.append(2)
28+
expect(doublyLinkedList.toString()).toBe('1,2')
29+
})
30+
31+
it('should delete node by value from doubly linked list', () => {
32+
const doublyLinkedList = new DoublyLinkedList()
33+
doublyLinkedList.append(1)
34+
doublyLinkedList.append(1)
35+
doublyLinkedList.append(2)
36+
doublyLinkedList.append(2)
37+
doublyLinkedList.append(3)
38+
doublyLinkedList.append(3)
39+
doublyLinkedList.append(4)
40+
doublyLinkedList.append(4)
41+
42+
expect(doublyLinkedList.delete(1)?.toString()).toBe('1')
43+
expect(doublyLinkedList.toString()).toBe('2,2,3,3,4,4')
44+
45+
expect(doublyLinkedList.delete(3)?.toString()).toBe('3')
46+
expect(doublyLinkedList.toString()).toBe('2,2,4,4')
47+
48+
expect(doublyLinkedList.delete(4)?.toString()).toBe('4')
49+
expect(doublyLinkedList.toString()).toBe('2,2')
50+
51+
expect(doublyLinkedList.delete(2)?.toString()).toBe('2')
52+
expect(doublyLinkedList.toString()).toBe('')
53+
})
54+
55+
it('should find node by value from doubly linked list', () => {
56+
const linkedList = new DoublyLinkedList()
57+
58+
expect(linkedList.find(1)).toBeNull()
59+
60+
linkedList.append(1)
61+
expect(linkedList.find(1)?.value).toBe(1)
62+
63+
linkedList.append(2)
64+
expect(linkedList.find(2)?.value).toBe(2)
65+
66+
linkedList.append(3)
67+
expect(linkedList.find(2)?.value).toBe(2)
68+
expect(linkedList.find(3)?.value).toBe(3)
69+
})
70+
71+
it('should delete head from doubly linked list', () => {
72+
const linkedList = new DoublyLinkedList()
73+
linkedList.append(1)
74+
linkedList.append(2)
75+
linkedList.append(3)
76+
linkedList.append(4)
77+
78+
expect(linkedList.head?.toString()).toBe('1')
79+
expect(linkedList.tail?.toString()).toBe('4')
80+
81+
const deletedNodeHead = linkedList.deleteHead()
82+
expect(deletedNodeHead?.value).toBe(1)
83+
expect(linkedList.head?.value).toBe(2)
84+
expect(linkedList.tail?.value).toBe(4)
85+
expect(linkedList.toString()).toBe('2,3,4')
86+
87+
linkedList.deleteHead()
88+
expect(linkedList.head?.value).toBe(3)
89+
expect(linkedList.tail?.value).toBe(4)
90+
expect(linkedList.toString()).toBe('3,4')
91+
92+
linkedList.deleteHead()
93+
expect(linkedList.head?.value).toBe(4)
94+
expect(linkedList.tail?.value).toBe(4)
95+
expect(linkedList.toString()).toBe('4')
96+
97+
linkedList.deleteHead()
98+
expect(linkedList.head).toBe(null)
99+
expect(linkedList.tail).toBe(null)
100+
expect(linkedList.toString()).toBe('')
101+
})
102+
103+
it('should delete tail from doubly linked list', () => {
104+
const linkedList = new DoublyLinkedList()
105+
linkedList.append(1)
106+
linkedList.append(2)
107+
linkedList.append(3)
108+
linkedList.append(4)
109+
110+
const deletedNodeTail = linkedList.deleteTail()
111+
expect(deletedNodeTail?.value).toBe(4)
112+
expect(linkedList.tail?.value).toBe(3)
113+
expect(linkedList.head?.value).toBe(1)
114+
expect(linkedList.toString()).toBe('1,2,3')
115+
116+
linkedList.deleteTail()
117+
expect(linkedList.tail?.value).toBe(2)
118+
expect(linkedList.head?.value).toBe(1)
119+
expect(linkedList.toString()).toBe('1,2')
120+
121+
linkedList.deleteTail()
122+
expect(linkedList.tail?.value).toBe(1)
123+
expect(linkedList.head?.value).toBe(1)
124+
expect(linkedList.toString()).toBe('1')
125+
126+
linkedList.deleteTail()
127+
expect(linkedList.tail).toBe(null)
128+
expect(linkedList.head).toBe(null)
129+
expect(linkedList.toString()).toBe('')
130+
})
131+
})

‎src/data-structures/doubly-linked-list/DoublyLinkedList.ts

Lines changed: 187 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,187 @@
1+
export class DoublyLinkedListNode {
2+
value: number
3+
next: DoublyLinkedListNode | null
4+
previous: DoublyLinkedListNode | null
5+
6+
/**
7+
* DoublyLinkedListNode constructor
8+
* @param value
9+
* @param next
10+
* @param previous
11+
*/
12+
constructor(
13+
value: number,
14+
next?: DoublyLinkedListNode | null,
15+
previous?: DoublyLinkedListNode | null,
16+
) {
17+
this.value = value
18+
this.next = next === undefined ? null : next
19+
this.previous = previous === undefined ? null : previous
20+
}
21+
22+
toString() {
23+
return `${this.value}`
24+
}
25+
}
26+
27+
export class DoublyLinkedList {
28+
head: DoublyLinkedListNode | null
29+
tail: DoublyLinkedListNode | null
30+
31+
/**
32+
* DoublyLinkedList constructor
33+
*/
34+
constructor() {
35+
this.head = null
36+
this.tail = null
37+
}
38+
39+
/**
40+
* prepend a node to the doubly linked list
41+
* @param value
42+
*/
43+
prepend(value: number) {
44+
const newNode = new DoublyLinkedListNode(value, this.head)
45+
46+
// if head exists
47+
if (this.head)
48+
this.head.previous = newNode
49+
this.head = newNode
50+
51+
// if tail is null
52+
if (!this.tail)
53+
this.tail = newNode
54+
55+
return this
56+
}
57+
58+
/**
59+
* append a node to the doubly linked list
60+
* @param value
61+
*/
62+
append(value: number) {
63+
const newNode = new DoublyLinkedListNode(value)
64+
65+
// if tail exists
66+
if (this.tail) {
67+
this.tail.next = newNode
68+
newNode.previous = this.tail
69+
this.tail = newNode
70+
}
71+
// if tail is null
72+
else {
73+
this.head = newNode
74+
this.tail = newNode
75+
}
76+
77+
return this
78+
}
79+
80+
/**
81+
* delete a node from the doubly linked list
82+
* @param value
83+
*/
84+
delete(value: number) {
85+
let currentNode = this.head
86+
let deletedNode: DoublyLinkedListNode | null = null
87+
88+
while (currentNode) {
89+
// if head is the node to be deleted
90+
if (currentNode?.value === value) {
91+
if (this.head === currentNode) {
92+
this.head = currentNode.next
93+
if (this.head)
94+
this.head.previous = null
95+
}
96+
// if tail is the node to be deleted
97+
else if (this.tail === currentNode) {
98+
this.tail = currentNode.previous
99+
if (this.tail)
100+
this.tail.next = null
101+
}
102+
// if node is in the middle
103+
else {
104+
if (currentNode.previous)
105+
currentNode.previous.next = currentNode.next
106+
if (currentNode.next)
107+
currentNode.next.previous = currentNode.previous
108+
}
109+
110+
deletedNode = currentNode
111+
}
112+
113+
currentNode = currentNode.next
114+
}
115+
116+
return deletedNode
117+
}
118+
119+
/**
120+
* find a node in the doubly linked list
121+
* @param value
122+
*/
123+
find(value: number) {
124+
let currentNode = this.head
125+
126+
while (currentNode) {
127+
if (currentNode.value === value)
128+
return currentNode
129+
130+
currentNode = currentNode.next
131+
}
132+
133+
return null
134+
}
135+
136+
/**
137+
* delete the head of the doubly linked list
138+
*/
139+
deleteHead() {
140+
if (!this.head)
141+
return null
142+
143+
const deletedHead = this.head
144+
145+
this.head = this.head.next
146+
if (this.head?.previous)
147+
this.head.previous = null
148+
149+
// if head is null
150+
if (!this.head)
151+
this.tail = null
152+
153+
return deletedHead
154+
}
155+
156+
/**
157+
* delete the tail of the doubly linked list
158+
*/
159+
deleteTail() {
160+
if (!this.tail)
161+
return null
162+
163+
const deletedTail = this.tail
164+
165+
this.tail = this.tail.previous
166+
if (this.tail)
167+
this.tail.next = null
168+
169+
// if tail is null
170+
if (!this.tail)
171+
this.head = null
172+
173+
return deletedTail
174+
}
175+
176+
toString() {
177+
const arr = []
178+
let currentNode = this.head
179+
180+
while (currentNode) {
181+
arr.push(currentNode.toString())
182+
currentNode = currentNode.next
183+
}
184+
185+
return arr.join(',')
186+
}
187+
}

‎src/data-structures/linked-list/LinkedList.test.ts

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,6 @@ describe('linkedList', () => {
4141
linkedList.insert(10, 9)
4242
expect(linkedList.head?.value).toBe(1)
4343
expect(linkedList.tail?.value).toBe(10)
44-
console.log(linkedList.toString())
4544
expect(linkedList.toString()).toBe('1,4,2,3,10')
4645
})
4746

0 commit comments

Comments
 (0)