Skip to content

Commit f14e523

Browse files
author
hojas
committed
linkedList
1 parent a4fa364 commit f14e523

File tree

11 files changed

+1075
-998
lines changed

11 files changed

+1075
-998
lines changed

‎package.json‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -3,17 +3,17 @@
33
"type": "module",
44
"version": "1.0.0",
55
"private": true,
6-
"packageManager": "pnpm@9.4.0",
6+
"packageManager": "pnpm@9.5.0",
77
"license": "MIT",
88
"scripts": {
99
"lint": "eslint .",
1010
"test": "vitest"
1111
},
1212
"devDependencies": {
13-
"@antfu/eslint-config": "^2.21.1",
14-
"eslint": "^9.5.0",
15-
"typescript": "^5.5.2",
16-
"vite": "^5.3.1",
17-
"vitest": "^1.6.0"
13+
"@antfu/eslint-config": "^2.22.0",
14+
"eslint": "^9.6.0",
15+
"typescript": "^5.5.3",
16+
"vite": "^5.3.3",
17+
"vitest": "^2.0.2"
1818
}
1919
}

‎pnpm-lock.yaml‎

Lines changed: 725 additions & 563 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

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

Lines changed: 73 additions & 111 deletions
Original file line numberDiff line numberDiff line change
@@ -1,151 +1,113 @@
11
import { describe, expect, it } from 'vitest'
22
import { DoublyLinkedList } from './DoublyLinkedList'
33

4-
describe('list', () => {
4+
describe('doubleLinkedList', () => {
55
it('should create an empty linked list', () => {
66
const list = new DoublyLinkedList()
77

8-
expect(list.head).toBe(null)
8+
expect(list.head?.next).equals(list.tail)
9+
expect(list.tail?.next).toBe(null)
910
expect(list.toString()).toBe('')
1011
})
1112

12-
it('should prepend a node to the linked list', () => {
13+
it('should find a node by index', () => {
1314
const list = new DoublyLinkedList()
1415

15-
list.prepend(1)
16-
expect(list.head?.value).toBe(1)
17-
expect(list.toString()).toBe('1')
16+
list.addAtTail(1)
17+
list.addAtTail(2)
18+
list.addAtTail(3)
1819

19-
list.prepend(2)
20-
expect(list.head?.value).toBe(2)
21-
expect(list.head?.next?.value).toBe(1)
22-
expect(list.head?.next?.previous?.value).toBe(2)
23-
expect(list.toString()).toBe('2,1')
20+
expect(list.toString()).toBe('1,2,3')
21+
expect(list.get(-1)).toBe(null)
22+
expect(list.get(0)?.value).toBe(1)
23+
expect(list.get(1)?.value).toBe(2)
24+
expect(list.get(2)?.value).toBe(3)
25+
expect(list.get(3)).toBe(null)
26+
})
27+
28+
it('should add a node at the head of the linked list', () => {
29+
const list = new DoublyLinkedList()
30+
31+
list.addAtHead(1)
32+
list.addAtHead(2)
33+
list.addAtHead(3)
2434

25-
list.prepend(3)
26-
expect(list.head?.value).toBe(3)
27-
expect(list.head?.next?.value).toBe(2)
28-
expect(list.head?.next?.previous?.value).toBe(3)
2935
expect(list.toString()).toBe('3,2,1')
3036
})
3137

32-
it('should append a node to the linked list', () => {
38+
it('should add a node at the tail of the linked list', () => {
3339
const list = new DoublyLinkedList()
3440

35-
list.append(1)
36-
expect(list.head?.value).toBe(1)
37-
expect(list.toString()).toBe('1')
38-
39-
list.append(2)
40-
expect(list.head?.value).toBe(1)
41-
expect(list.head?.next?.value).toBe(2)
42-
expect(list.head?.next?.previous?.value).toBe(1)
43-
expect(list.toString()).toBe('1,2')
44-
45-
list.append(3)
46-
expect(list.head?.value).toBe(1)
47-
expect(list.head?.next?.value).toBe(2)
48-
expect(list.head?.next?.previous?.value).toBe(1)
49-
expect(list.head?.next?.next?.value).toBe(3)
50-
expect(list.head?.next?.next?.previous?.value).toBe(2)
41+
list.addAtTail(1)
42+
list.addAtTail(2)
43+
list.addAtTail(3)
44+
5145
expect(list.toString()).toBe('1,2,3')
5246
})
5347

54-
it('should insert a node to the linked list', () => {
48+
it('should add a node at a specific index of the linked list', () => {
5549
const list = new DoublyLinkedList()
5650

57-
list.insert(4, 3)
58-
expect(list.head?.value).toBe(4)
59-
60-
list.insert(3, 2)
61-
list.insert(2, 1)
62-
list.insert(1, -7)
63-
list.insert(10, 9)
51+
list.addAtIndex(0, 1)
52+
list.addAtIndex(1, 2)
53+
list.addAtIndex(2, 3)
54+
list.addAtIndex(3, 5)
55+
list.addAtIndex(3, 4)
6456

65-
expect(list.head?.value).toBe(1)
66-
expect(list.head?.next?.value).toBe(4)
67-
expect(list.head?.next?.next?.value).toBe(2)
68-
expect(list.head?.next?.next?.previous?.value).toBe(4)
69-
expect(list.toString()).toBe('1,4,2,3,10')
57+
expect(list.toString()).toBe('1,2,3,4,5')
7058
})
7159

72-
it('should find a node by value', () => {
60+
it('should delete a node by index', () => {
7361
const list = new DoublyLinkedList()
7462

75-
expect(list.find(1)).toBeNull()
63+
list.addAtTail(1)
64+
list.addAtTail(2)
65+
list.addAtTail(3)
66+
list.addAtTail(4)
67+
list.addAtTail(5)
68+
69+
expect(list.toString()).toBe('1,2,3,4,5')
70+
list.deleteAtIndex(0)
71+
expect(list.toString()).toBe('2,3,4,5')
72+
list.deleteAtIndex(1)
73+
expect(list.toString()).toBe('2,4,5')
74+
list.deleteAtIndex(2)
75+
expect(list.toString()).toBe('2,4')
76+
list.deleteAtIndex(2)
77+
expect(list.toString()).toBe('2,4')
78+
list.deleteAtIndex(0)
79+
expect(list.toString()).toBe('4')
80+
list.deleteAtIndex(0)
81+
expect(list.toString()).toBe('')
82+
})
7683

77-
list.append(1)
78-
expect(list.find(1)?.value).toBe(1)
84+
it('should find a node by value', () => {
85+
const list = new DoublyLinkedList()
7986

80-
list.append(2)
81-
expect(list.find(2)?.value).toBe(2)
87+
list.addAtTail(1)
88+
list.addAtTail(2)
89+
list.addAtTail(3)
8290

83-
list.append(3)
8491
expect(list.find(1)?.value).toBe(1)
8592
expect(list.find(2)?.value).toBe(2)
8693
expect(list.find(3)?.value).toBe(3)
8794
})
8895

89-
it('should delete a node by value from the linked list', () => {
90-
const list = new DoublyLinkedList()
91-
92-
list.append(1)
93-
list.append(1)
94-
list.append(2)
95-
list.append(2)
96-
list.append(3)
97-
list.append(4)
98-
list.append(5)
99-
100-
list.delete(3)
101-
expect(list.head?.value).toBe(1)
102-
expect(list.head?.next?.value).toBe(1)
103-
expect(list.head?.next?.next?.value).toBe(2)
104-
expect(list.toString()).toBe('1,1,2,2,4,5')
105-
106-
list.delete(1)
107-
expect(list.head?.value).toBe(2)
108-
expect(list.head?.previous).toBe(null)
109-
expect(list.toString()).toBe('2,2,4,5')
110-
111-
list.delete(4)
112-
expect(list.head?.value).toBe(2)
113-
expect(list.head?.next?.value).toBe(2)
114-
expect(list.head?.next?.next?.value).toBe(5)
115-
expect(list.head?.next?.next?.previous?.value).toBe(2)
116-
expect(list.toString()).toBe('2,2,5')
117-
118-
list.delete(5)
119-
expect(list.head?.value).toBe(2)
120-
expect(list.toString()).toBe('2,2')
121-
122-
list.delete(2)
123-
expect(list.head).toBe(null)
124-
expect(list.toString()).toBe('')
125-
})
126-
127-
it('should delete linked list head', () => {
96+
it('should delete a node by value', () => {
12897
const list = new DoublyLinkedList()
12998

130-
list.append(1)
131-
list.append(2)
132-
list.append(3)
133-
134-
list.deleteHead()
135-
expect(list.head?.value).toBe(2)
136-
expect(list.head?.previous).toBe(null)
137-
expect(list.head?.next?.value).toBe(3)
138-
expect(list.head?.next?.previous?.value).toBe(2)
139-
expect(list.toString()).toBe('2,3')
140-
141-
list.deleteHead()
142-
expect(list.head?.value).toBe(3)
143-
expect(list.head?.previous).toBe(null)
144-
expect(list.head?.next).toBe(null)
145-
expect(list.toString()).toBe('3')
146-
147-
list.deleteHead()
148-
expect(list.head).toBe(null)
149-
expect(list.toString()).toBe('')
99+
list.addAtTail(1)
100+
list.addAtTail(2)
101+
list.addAtTail(3)
102+
list.addAtTail(4)
103+
list.addAtTail(5)
104+
105+
expect(list.toString()).toBe('1,2,3,4,5')
106+
list.deleteValue(1)
107+
expect(list.toString()).toBe('2,3,4,5')
108+
list.deleteValue(3)
109+
expect(list.toString()).toBe('2,4,5')
110+
list.deleteValue(5)
111+
expect(list.toString()).toBe('2,4')
150112
})
151113
})

0 commit comments

Comments
 (0)