Skip to content

Commit 7a6ec3f

Browse files
hojashojas
committed
DoublyLinkedList testing
1 parent d079035 commit 7a6ec3f

File tree

5 files changed

+247
-302
lines changed

5 files changed

+247
-302
lines changed

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

Lines changed: 2 additions & 129 deletions
Original file line numberDiff line numberDiff line change
@@ -1,131 +1,4 @@
1-
import { describe, expect, it } from 'vitest'
1+
import { testList } from '../linked-list/test-list'
22
import { DoublyLinkedList } from './DoublyLinkedList'
33

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-
})
4+
testList(DoublyLinkedList)

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

Lines changed: 50 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -77,6 +77,52 @@ export class DoublyLinkedList {
7777
return this
7878
}
7979

80+
/**
81+
* insert a node to the doubly linked list
82+
* @param value
83+
* @param index
84+
*/
85+
insert(value: number, index: number) {
86+
if (index <= 0)
87+
return this.prepend(value)
88+
89+
const newNode = new DoublyLinkedListNode(value)
90+
let currentNode = this.head
91+
let currentIndex = 0
92+
93+
while (currentNode && currentIndex !== index - 1) {
94+
currentNode = currentNode.next
95+
currentIndex++
96+
}
97+
98+
if (currentNode) {
99+
newNode.next = currentNode.next
100+
currentNode.next = newNode
101+
}
102+
else {
103+
this.append(value)
104+
}
105+
106+
return this
107+
}
108+
109+
/**
110+
* find a node in the doubly linked list
111+
* @param value
112+
*/
113+
find(value: number) {
114+
let currentNode = this.head
115+
116+
while (currentNode) {
117+
if (currentNode.value === value)
118+
return currentNode
119+
120+
currentNode = currentNode.next
121+
}
122+
123+
return null
124+
}
125+
80126
/**
81127
* delete a node from the doubly linked list
82128
* @param value
@@ -92,12 +138,16 @@ export class DoublyLinkedList {
92138
this.head = currentNode.next
93139
if (this.head)
94140
this.head.previous = null
141+
else
142+
this.tail = null
95143
}
96144
// if tail is the node to be deleted
97145
else if (this.tail === currentNode) {
98146
this.tail = currentNode.previous
99147
if (this.tail)
100148
this.tail.next = null
149+
else
150+
this.head = null
101151
}
102152
// if node is in the middle
103153
else {
@@ -116,23 +166,6 @@ export class DoublyLinkedList {
116166
return deletedNode
117167
}
118168

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-
136169
/**
137170
* delete the head of the doubly linked list
138171
*/

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

Lines changed: 2 additions & 152 deletions
Original file line numberDiff line numberDiff line change
@@ -1,154 +1,4 @@
1-
import { describe, expect, it } from 'vitest'
1+
import { testList } from './test-list'
22
import { LinkedList } from './LinkedList'
33

4-
describe('linkedList', () => {
5-
it('should create an empty linked list', () => {
6-
const linkedList = new LinkedList()
7-
expect(linkedList.head).toBe(null)
8-
expect(linkedList.tail).toBe(null)
9-
expect(linkedList.toString()).toBe('')
10-
})
11-
12-
it('should append a node to the linked list', () => {
13-
const linkedList = new LinkedList()
14-
linkedList.append(1)
15-
linkedList.append(2)
16-
linkedList.append(3)
17-
expect(linkedList.head?.value).toBe(1)
18-
expect(linkedList.tail?.value).toBe(3)
19-
expect(linkedList.toString()).toBe('1,2,3')
20-
})
21-
22-
it('should prepend a node to the linked list', () => {
23-
const linkedList = new LinkedList()
24-
linkedList.prepend(1)
25-
linkedList.prepend(2)
26-
linkedList.prepend(3)
27-
expect(linkedList.head?.value).toBe(3)
28-
expect(linkedList.tail?.value).toBe(1)
29-
expect(linkedList.toString()).toBe('3,2,1')
30-
})
31-
32-
it('should insert a node to the linked list', () => {
33-
const linkedList = new LinkedList()
34-
linkedList.insert(4, 3)
35-
expect(linkedList.head?.value).toBe(4)
36-
expect(linkedList.tail?.value).toBe(4)
37-
38-
linkedList.insert(3, 2)
39-
linkedList.insert(2, 1)
40-
linkedList.insert(1, -7)
41-
linkedList.insert(10, 9)
42-
expect(linkedList.head?.value).toBe(1)
43-
expect(linkedList.tail?.value).toBe(10)
44-
expect(linkedList.toString()).toBe('1,4,2,3,10')
45-
})
46-
47-
it('should delete a node by value from the linked list', () => {
48-
const linkedList = new LinkedList()
49-
50-
expect(linkedList.delete(5)).toBeNull()
51-
52-
linkedList.append(1)
53-
linkedList.append(1)
54-
linkedList.append(2)
55-
linkedList.append(3)
56-
linkedList.append(3)
57-
linkedList.append(3)
58-
linkedList.append(4)
59-
linkedList.append(5)
60-
61-
expect(linkedList.head?.toString()).toBe('1')
62-
expect(linkedList.tail?.toString()).toBe('5')
63-
64-
const deletedNode = linkedList.delete(3)
65-
expect(deletedNode?.value).toBe(3)
66-
expect(linkedList.toString()).toBe('1,1,2,4,5')
67-
68-
linkedList.delete(3)
69-
expect(linkedList.toString()).toBe('1,1,2,4,5')
70-
71-
linkedList.delete(1)
72-
expect(linkedList.toString()).toBe('2,4,5')
73-
74-
expect(linkedList.head?.toString()).toBe('2')
75-
expect(linkedList.tail?.toString()).toBe('5')
76-
77-
linkedList.delete(5)
78-
expect(linkedList.toString()).toBe('2,4')
79-
80-
expect(linkedList.head?.toString()).toBe('2')
81-
expect(linkedList.tail?.toString()).toBe('4')
82-
83-
linkedList.delete(4)
84-
expect(linkedList.toString()).toBe('2')
85-
86-
expect(linkedList.head?.toString()).toBe('2')
87-
expect(linkedList.tail?.toString()).toBe('2')
88-
89-
linkedList.delete(2)
90-
expect(linkedList.toString()).toBe('')
91-
})
92-
93-
it('should delete linked list head', () => {
94-
const linkedList = new LinkedList()
95-
96-
linkedList.append(1)
97-
linkedList.append(2)
98-
linkedList.append(3)
99-
100-
expect(linkedList.head?.toString()).toBe('1')
101-
expect(linkedList.tail?.toString()).toBe('3')
102-
103-
const deletedNode1 = linkedList.deleteHead()
104-
expect(deletedNode1?.value).toBe(1)
105-
expect(linkedList.toString()).toBe('2,3')
106-
107-
const deletedNode2 = linkedList.deleteHead()
108-
expect(deletedNode2?.value).toBe(2)
109-
expect(linkedList.toString()).toBe('3')
110-
111-
const deletedNode3 = linkedList.deleteHead()
112-
expect(deletedNode3?.value).toBe(3)
113-
expect(linkedList.toString()).toBe('')
114-
})
115-
116-
it('should delete linked list tail', () => {
117-
const linkedList = new LinkedList()
118-
119-
linkedList.append(1)
120-
linkedList.append(2)
121-
linkedList.append(3)
122-
123-
expect(linkedList.head?.toString()).toBe('1')
124-
expect(linkedList.tail?.toString()).toBe('3')
125-
126-
const deletedNode1 = linkedList.deleteTail()
127-
expect(deletedNode1?.value).toBe(3)
128-
expect(linkedList.toString()).toBe('1,2')
129-
130-
const deletedNode2 = linkedList.deleteTail()
131-
expect(deletedNode2?.value).toBe(2)
132-
expect(linkedList.toString()).toBe('1')
133-
134-
const deletedNode3 = linkedList.deleteTail()
135-
expect(deletedNode3?.value).toBe(1)
136-
expect(linkedList.toString()).toBe('')
137-
})
138-
139-
it('should find a node by value', () => {
140-
const linkedList = new LinkedList()
141-
142-
expect(linkedList.find(5)).toBeNull()
143-
144-
linkedList.append(1)
145-
expect(linkedList.find(1)?.value).toBe(1)
146-
147-
linkedList.append(2)
148-
linkedList.append(3)
149-
150-
const node = linkedList.find(2)
151-
expect(node?.value).toBe(2)
152-
expect(linkedList.find(5)).toBeNull()
153-
})
154-
})
4+
testList(LinkedList)

0 commit comments

Comments
 (0)