Linked List
Description:
The Linked List is a data structure that is composed by Nodes that are linked to each other by a reference to the next Node in the list. This allows us to have an dynamic list of elements that we can scale as much as we want. The elements are not contiguous in memory -- like in an array.
Pros & Cons:
Using this data structure has some benefits, such as:
Insertion: because the elements are not contiguous in memory, it's easy to insert elements in every position of the array. You don't have to move every element after insertion, you just need to change the reference to the next element.
Delete: because the elements are not contiguous in memory, it's easy to delete elements as well. You don't have to move every element after deleting an element, you just need to change the reference to the next element.
Little memory Waste: there are two possible places were memory could be wasted. The first one is the Head of the list, but only if the list is empty. The second place is the last element Next reference.
It also has some cons, for example:
Access and Search: this is because we need to iterate over all the elements of the list and in the worst case scenario, this is going to be end up being O(n).
Memory: because each element needs to have a reference to the next one, the amount of memeory used for each node is more than a simple array for example.
1. Main class and node implmentation
Let's implment the base classes for the Linked List:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
export type LinkedListNode<T> = {
content: T,
next: LinkedListNode<T> | null,
};
export class LinkedList<T> {
// Define the head.
head: LinkedListNode<T> | null;
constructor(head: LinkedListNode<T> | null = null) {
this.head = head;
}
}
2. First and Last
Now we are going to define some helper functions to get the first element (the head) and the last element of the Linked List:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
first(): LinkedListNode<T> | null {
return this.head;
};
last(): LinkedListNode<T> | null {
if(this.head)
return this.getLast(this.head);
return null;
};
// Define aux function
private getLast = (node: LinkedListNode<T>): LinkedListNode<T> => {
if (node.next) {
return this.getLast(node.next);
} else {
return node;
}
};
3. Append and Prepend
When we have a Linked List we can add elements in the beggining of the list, also known as Prepend or at the end of the list, Append:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Add the element at the begining of the linked list.
prepend(element: LinkedListNode<T>) {
element.next = this.head;
this.head = element;
};
// Add the element at the end of the linked list.
append(element: LinkedListNode<T>) {
if(this.head) {
const lastElement = this.getLast(this.head);
lastElement.next = element;
}
else
this.head = element;
};
4. Insertion
We can also insert an element at any position using the insert function:
0
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
// Insert an element in a position of the list.
insert(elementToInsert: LinkedListNode<T>, position: number) {
let counter:number = 0;
let currentNode: LinkedListNode<T> | null = this.head;
if(currentNode) {
// Gets to the previus position that I want to insert.
while (counter < position-1) {
counter++;
// if there is a next element, I move to that one.
if(currentNode.next)
currentNode = currentNode.next;
else
break;
}
// If i got the the actual position.
if(counter === position-1) {
elementToInsert.next = currentNode.next;
currentNode.next = elementToInsert;
}
}
};
5. Delete
To delete an element of the list the idea :
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Delete an element from the list.
delete(contentToDelete: any) {
let currentNode: LinkedListNode<T> | null = this.head;
if (this.head && this.head.content === contentToDelete) {
this.head = this.head?.next;
return;
}
while(currentNode) {
if(currentNode.next && currentNode.next.content === contentToDelete) {
currentNode.next = currentNode.next.next;
break;
};
currentNode = currentNode.next;
}
};
Testing it
So, we are going to test in console to see if it is working. We are going to run the following:
0
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
// Creates a new stack
console.log('** Creates a new linked list.');
const newLinkedList = linkedList();
// Prepend new elements
console.log('** Prepend elements to the linked list.');
newLinkedList.prepend({content: "A", next: null});
newLinkedList.prepend({content: "B", next: null});
newLinkedList.prepend({content: "D", next: null});
console.log('** Linked List elements: ', newLinkedList.toArray().map(item => item.content).join(','));
// Append new element
console.log('** Append element to the linked list.');
newLinkedList.append({content: "0", next: null});
console.log('** Linked List elements: ', newLinkedList.toArray().map(item => item.content).join(','));
// Insert an element on position 3
console.log('** Insert element to the linked list in position 3.');
newLinkedList.insert({content: "C", next: null}, 3);
console.log('** Linked List elements: ', newLinkedList.toArray().map(item => item.content).join(','));
// Delete an element
console.log('** Delete an element from the linked list.');
newLinkedList.delete("0");
console.log('** Linked List elements: ', newLinkedList.toArray().map(item => item.content).join(','));
console.log('** Delete an element from the linked list.');
newLinkedList.delete("C");
console.log('** Linked List elements: ', newLinkedList.toArray().map(item => item.content).join(','));
Console output
You should see something like the following in the console:
0
1
2
3
4
5
6
7
8
9
10
11
** Creates a new linked list.
** Prepend elements to the linked list.
** Linked List elements: A,B,D
** Append element to the linked list.
** Linked List elements: 0,A,B,D
** Insert element to the linked list in position 3.
** Linked List elements: 0,A,B,C,D
** Delete an element from the linked list.
** Linked List elements: A,B,C,D
** Delete an element from the linked list.
** Linked List elements: A,B,D
Complete Code
0
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
export type LinkedListNode<T> = {
content: T,
next: LinkedListNode<T> | null,
};
export class LinkedList<T> {
// Define the head.
head: LinkedListNode<T> | null;
constructor(head: LinkedListNode<T> | null = null) {
this.head = head;
}
// Define aux function
getLast = (node: LinkedListNode<T>): LinkedListNode<T> => {
if (node.next) {
return this.getLast(node.next);
} else {
return node;
}
};
first(): LinkedListNode<T> | null {
return this.head;
};
last(): LinkedListNode<T> | null {
if(this.head)
return this.getLast(this.head);
return null;
};
// Add the element at the begining of the linked list.
prepend(element: LinkedListNode<T>) {
element.next = this.head;
this.head = element;
};
// Add the element at the end of the linked list.
append(element: LinkedListNode<T>) {
if(this.head) {
const lastElement = this.getLast(this.head);
lastElement.next = element;
}
else
this.head = element;
};
// Insert an element in a position of the list.
insert(elementToInsert: LinkedListNode<T>, position: number) {
let counter:number = 0;
let currentNode: LinkedListNode<T> | null = this.head;
if(currentNode) {
// Gets to the previus position that I want to insert.
while (counter < position-1) {
counter++;
// if there is a next element, I move to that one.
if(currentNode.next)
currentNode = currentNode.next;
else
break;
}
// If i got the the actual position.
if(counter === position-1) {
elementToInsert.next = currentNode.next;
currentNode.next = elementToInsert;
}
}
};
// Delete an element from the list.
delete(contentToDelete: any) {
let currentNode: LinkedListNode<T> | null = this.head;
if (this.head && this.head.content === contentToDelete) {
this.head = this.head?.next;
return;
}
while(currentNode) {
if(currentNode.next && currentNode.next.content === contentToDelete) {
currentNode.next = currentNode.next.next;
break;
};
currentNode = currentNode.next;
}
};
// Returns if the content exist in the linked list.
contains(content: T): boolean {
let currentNode: LinkedListNode<T> | null = this.head;
while (currentNode) {
if(currentNode.content === content)
return true;
currentNode = currentNode.next;
}
return false;
}
// Eliminates everything but the head.
clear() {
if(this.head)
this.head.next = null;
}
// Returns the list as an array.
toArray(): LinkedListNode<T>[] {
let array: LinkedListNode<T>[] = [];
let currentNode: LinkedListNode<T> | null = this.head;
if(currentNode) {
do {
array = [...array, currentNode];
currentNode = currentNode?.next;
} while (currentNode)
}
return array;
}
}