Skip to content

Commit 4f9400c

Browse files
author
hojas
committed
LinkedList
1 parent 56ab713 commit 4f9400c

File tree

10 files changed

+504
-564
lines changed

10 files changed

+504
-564
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.5.0",
6+
"packageManager": "pnpm@9.6.0",
77
"license": "MIT",
88
"scripts": {
99
"lint": "eslint .",
1010
"test": "vitest"
1111
},
1212
"devDependencies": {
13-
"@antfu/eslint-config": "^2.22.0",
14-
"eslint": "^9.7.0",
15-
"typescript": "^5.5.3",
16-
"vite": "^5.3.3",
17-
"vitest": "^2.0.2"
13+
"@antfu/eslint-config": "^2.24.1",
14+
"eslint": "^9.8.0",
15+
"typescript": "^5.5.4",
16+
"vite": "^5.3.5",
17+
"vitest": "^2.0.5"
1818
}
1919
}

‎pnpm-lock.yaml

Lines changed: 345 additions & 439 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: 9 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -97,17 +97,22 @@ describe('doubleLinkedList', () => {
9797
const list = new DoublyLinkedList()
9898

9999
list.addAtTail(1)
100+
list.addAtTail(1)
101+
list.addAtTail(2)
100102
list.addAtTail(2)
101103
list.addAtTail(3)
104+
list.addAtTail(3)
102105
list.addAtTail(4)
106+
list.addAtTail(4)
107+
list.addAtTail(5)
103108
list.addAtTail(5)
104109

105-
expect(list.toString()).toBe('1,2,3,4,5')
110+
expect(list.toString()).toBe('1,1,2,2,3,3,4,4,5,5')
106111
list.deleteValue(1)
107-
expect(list.toString()).toBe('2,3,4,5')
112+
expect(list.toString()).toBe('2,2,3,3,4,4,5,5')
108113
list.deleteValue(3)
109-
expect(list.toString()).toBe('2,4,5')
114+
expect(list.toString()).toBe('2,2,4,4,5,5')
110115
list.deleteValue(5)
111-
expect(list.toString()).toBe('2,4')
116+
expect(list.toString()).toBe('2,2,4,4')
112117
})
113118
})

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

Lines changed: 45 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,4 @@
1-
import type { LinkedListNode } from './LinkedList.ts'
2-
3-
export class DoublyLinkedListNode<T> {
4-
value: T | null
5-
previous: DoublyLinkedListNode<T> | null
6-
next: DoublyLinkedListNode<T> | null
7-
8-
constructor(value: T | null = null) {
9-
this.value = value
10-
this.previous = null
11-
this.next = null
12-
}
13-
14-
toString() {
15-
return `${this.value}`
16-
}
17-
}
1+
import { DoublyLinkedListNode } from './DoublyLinkedListNode'
182

193
export class DoublyLinkedList<T> {
204
head: DoublyLinkedListNode<T>
@@ -39,21 +23,11 @@ export class DoublyLinkedList<T> {
3923
return null
4024
}
4125

42-
let currentNode: DoublyLinkedListNode<T>
43-
if (index < this.size - index - 1) {
44-
currentNode = this.head
45-
for (let i = 0; i <= index; i++) {
46-
currentNode = currentNode.next as DoublyLinkedListNode<T>
47-
}
48-
}
49-
else {
50-
currentNode = this.tail
51-
for (let i = 0; i < this.size - index; i++) {
52-
currentNode = currentNode.previous as DoublyLinkedListNode<T>
53-
}
26+
let currentNode = this.head
27+
while (index--) {
28+
currentNode = currentNode.next as DoublyLinkedListNode<T>
5429
}
55-
56-
return currentNode
30+
return currentNode.next
5731
}
5832

5933
/**
@@ -83,7 +57,6 @@ export class DoublyLinkedList<T> {
8357
}
8458

8559
let prev: DoublyLinkedListNode<T>, found: DoublyLinkedListNode<T>
86-
8760
if (index === this.size) {
8861
found = this.tail
8962
prev = this.tail.previous as DoublyLinkedListNode<T>
@@ -126,44 +99,61 @@ export class DoublyLinkedList<T> {
12699
* @returns the node with the specified value, or null if the value is not found.
127100
*/
128101
find(value: number) {
129-
let currentNode = this.head.next
130-
131-
while (currentNode !== null && currentNode.value !== value) {
132-
currentNode = currentNode.next
102+
let node = this.head
103+
while (node.next !== null && node.value !== value) {
104+
node = node.next
133105
}
134-
135-
return currentNode
106+
return node
136107
}
137108

138109
/**
139-
* Delete the first occurrence of the specified value from the list.
110+
* Delete all occurrences of the specified value from the list.
140111
* @param value
141112
*/
142113
deleteValue(value: number) {
143-
let prevNode: DoublyLinkedListNode<T> | null = null
144-
let currentNode: DoublyLinkedListNode<T> | null = this.head
114+
// let prevNode: DoublyLinkedListNode<T> | null = null
115+
// let currentNode: DoublyLinkedListNode<T> | null = this.head
116+
//
117+
// while (currentNode !== null && currentNode.value !== value) {
118+
// prevNode = currentNode
119+
// currentNode = currentNode.next
120+
// }
121+
//
122+
// if (currentNode) {
123+
// if (prevNode) {
124+
// prevNode.next = currentNode.next
125+
// }
126+
// else {
127+
// this.head.next = currentNode.next
128+
// }
129+
//
130+
// currentNode.previous!.next = currentNode.next
131+
// currentNode.next!.previous = currentNode.previous
132+
// this.size--
133+
// }
145134

146-
while (currentNode !== null && currentNode.value !== value) {
147-
prevNode = currentNode
148-
currentNode = currentNode.next
149-
}
150-
151-
if (currentNode) {
152-
if (prevNode) {
153-
prevNode.next = currentNode.next
135+
let currentNode = this.head
136+
while (currentNode.next !== null) {
137+
if (currentNode.next.value === value) {
138+
currentNode.next = currentNode.next.next
139+
140+
if (currentNode.next) {
141+
currentNode.next.previous = currentNode
142+
}
143+
else {
144+
this.tail.previous = currentNode
145+
this.tail = currentNode
146+
}
147+
this.size--
154148
}
155149
else {
156-
this.head.next = currentNode.next
150+
currentNode = currentNode.next as DoublyLinkedListNode<T>
157151
}
158-
159-
currentNode.previous!.next = currentNode.next
160-
currentNode.next!.previous = currentNode.previous
161-
this.size--
162152
}
163153
}
164154

165155
toString() {
166-
const arr: LinkedListNode<T>[] = []
156+
const arr: DoublyLinkedListNode<T>[] = []
167157

168158
let currentNode = this.head
169159
while (currentNode.next && currentNode.next.value !== null) {

‎src/1-data-structures/1-linked-list/DoublyLinkedListNode.ts

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
export class DoublyLinkedListNode<T> {
2+
value: T | null
3+
previous: DoublyLinkedListNode<T> | null
4+
next: DoublyLinkedListNode<T> | null
5+
6+
constructor(
7+
value: T | null = null,
8+
previous: DoublyLinkedListNode<T> | null = null,
9+
next: DoublyLinkedListNode<T> | null = null,
10+
) {
11+
this.value = value
12+
this.previous = previous
13+
this.next = next
14+
}
15+
16+
toString() {
17+
return `${this.value}`
18+
}
19+
}

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

Lines changed: 9 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -96,17 +96,22 @@ describe('linkedList', () => {
9696
const list = new LinkedList()
9797

9898
list.addAtTail(1)
99+
list.addAtTail(1)
100+
list.addAtTail(2)
99101
list.addAtTail(2)
100102
list.addAtTail(3)
103+
list.addAtTail(3)
101104
list.addAtTail(4)
105+
list.addAtTail(4)
106+
list.addAtTail(5)
102107
list.addAtTail(5)
103108

104-
expect(list.toString()).toBe('1,2,3,4,5')
109+
expect(list.toString()).toBe('1,1,2,2,3,3,4,4,5,5')
105110
list.deleteValue(1)
106-
expect(list.toString()).toBe('2,3,4,5')
111+
expect(list.toString()).toBe('2,2,3,3,4,4,5,5')
107112
list.deleteValue(3)
108-
expect(list.toString()).toBe('2,4,5')
113+
expect(list.toString()).toBe('2,2,4,4,5,5')
109114
list.deleteValue(5)
110-
expect(list.toString()).toBe('2,4')
115+
expect(list.toString()).toBe('2,2,4,4')
111116
})
112117
})

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

Lines changed: 34 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,8 @@
1-
export class LinkedListNode<T> {
2-
value: T | null
3-
next: LinkedListNode<T> | null
4-
5-
constructor(value: T | null = null) {
6-
this.value = value
7-
this.next = null
8-
}
9-
10-
toString() {
11-
return `${this.value}`
12-
}
13-
}
1+
import { LinkedListNode } from './LinkedListNode'
142

3+
/**
4+
* Linked List implementation in TypeScript.
5+
*/
156
export class LinkedList<T> {
167
head: LinkedListNode<T>
178
size: number
@@ -32,11 +23,10 @@ export class LinkedList<T> {
3223
}
3324

3425
let currentNode = this.head
35-
for (let i = 0; i <= index; i++) {
26+
while (index--) {
3627
currentNode = currentNode.next as LinkedListNode<T>
3728
}
38-
39-
return currentNode
29+
return currentNode.next
4030
}
4131

4232
/**
@@ -61,33 +51,37 @@ export class LinkedList<T> {
6151
* @param value
6252
*/
6353
addAtIndex(index: number, value: T): void {
64-
if (index >= 0 && index <= this.size) {
65-
let prev: LinkedListNode<T> = this.head
66-
if (index > 0) {
67-
prev = this.get(index - 1) as LinkedListNode<T>
68-
}
54+
if (index < 0 || index > this.size) {
55+
return
56+
}
6957

70-
const newNode = new LinkedListNode(value)
71-
newNode.next = prev.next
72-
prev.next = newNode
73-
this.size++
58+
let prev: LinkedListNode<T> = this.head
59+
if (index > 0) {
60+
prev = this.get(index - 1) as LinkedListNode<T>
7461
}
62+
63+
const newNode = new LinkedListNode(value)
64+
newNode.next = prev.next
65+
prev.next = newNode
66+
this.size++
7567
}
7668

7769
/**
7870
* Delete the node at the specified index.
7971
* @param index
8072
*/
8173
deleteAtIndex(index: number) {
82-
if (index >= 0 && index < this.size) {
83-
let prev = this.head
84-
if (index > 0) {
85-
prev = this.get(index - 1) as LinkedListNode<T>
86-
}
74+
if (index < 0 || index >= this.size) {
75+
return
76+
}
8777

88-
prev.next = prev.next!.next
89-
this.size--
78+
let prev = this.head
79+
if (index > 0) {
80+
prev = this.get(index - 1) as LinkedListNode<T>
9081
}
82+
83+
prev.next = prev.next!.next
84+
this.size--
9185
}
9286

9387
/**
@@ -96,34 +90,25 @@ export class LinkedList<T> {
9690
* @returns the node containing the specified value, or null if the value is not found.
9791
*/
9892
find(value: T): LinkedListNode<T> | null {
99-
let node = this.head.next
100-
101-
while (node !== null && node.value !== value) {
93+
let node = this.head
94+
while (node.next !== null && node.value !== value) {
10295
node = node.next
10396
}
104-
10597
return node
10698
}
10799

108100
/**
109-
* Delete the first occurrence of the specified value in this list.
101+
* Delete all occurrences of the specified value in this list.
110102
* @param value
111103
*/
112104
deleteValue(value: T) {
113-
let prevNode: LinkedListNode<T> | null = null
114-
let currentNode: LinkedListNode<T> | null = this.head
115-
116-
while (currentNode !== null && currentNode.value !== value) {
117-
prevNode = currentNode
118-
currentNode = currentNode.next
119-
}
120-
121-
if (currentNode) {
122-
if (prevNode) {
123-
prevNode.next = currentNode.next
105+
let prevNode = this.head
106+
while (prevNode.next) {
107+
if (prevNode.next.value === value) {
108+
prevNode.next = prevNode.next.next
124109
}
125110
else {
126-
this.head.next = currentNode.next
111+
prevNode = prevNode.next as LinkedListNode<T>
127112
}
128113
}
129114
}

‎src/1-data-structures/1-linked-list/LinkedListNode.ts

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
/**
2+
* LinkedListNode class
3+
* @param T value
4+
* @param LinkedListNode<T> next
5+
* @constructor
6+
*/
7+
export class LinkedListNode<T> {
8+
value: T | null
9+
next: LinkedListNode<T> | null
10+
11+
constructor(value: T | null = null, next: LinkedListNode<T> | null = null) {
12+
this.value = value
13+
this.next = next
14+
}
15+
16+
toString() {
17+
return `${this.value}`
18+
}
19+
}

0 commit comments

Comments
 (0)