what is linked list
Linear collection of data elements (aka Node), In which linear order is not given by their physical placement in memory. Instead each element points to the next element. It is a data structure consisting of a group of nodes that together represent a sequence.
what are the advantages
- Efficient Deletion of Known Nodes / O(1)
- Efficient Insertion / O(1)
- Dynamic Size
- Linked lists do not require contiguous memory allocation like Array
what are the disadvantages
- Sequential Access / O(n)
- Memory Overhead, as each node in a linked list requires additional memory for the pointer/reference to the next node.
when to use
- Implementing a Queue or Stack / O(1)
- Undo Mechanisms
- Frequent Insertions/Deletions in Middle/ O(1)
Example
structure of a single node :
class LinkedListNode {
constructor(value, next = null){
this.value = value;
this.next = next
}
}
Figure 1: This is an example of a node.
structure of linked list :
class LinkedList {
constructor () {
this.head = null;
this.tail = null;
}
}
Figure 2: This is an example of a nodelist.
Figure 3: This is an example of visual representation of Node List.
Basic Operation
Append
PseudoCode
Append(value)
pre : value is the value to add in the list
post : value has beed added at the tail of the list
newNode ⟵ node(value)
if(head = Ø) :
head ← newNode
tail ← newNode
else
tail.next ← newNode
tail ← newNode
end Append
Figure 4: This is an example of a nodelist append pseudocode.
Javascript Implementaion
append (value) {
let lastNode = new LinkedListNode(value)
if(!this.head){
this.head = lastNode;
this.tail = lastNode;
return this;
}else{
//here this.tail is the previous last node
this.tail.next = lastNode; //add the current lastNode reference to the previous last node next property
this.tail = lastNode; // change the reference of the tail to the current lastNode.
return this;
}
}
Figure 5: This is an example of a nodelist append method implementation.
Visual Example
Figure 6: This is an example of visual representation of Node List Appending.
Prepend
PseudoCode
Prepend(value)
pre : value is the value to add in the list.
post : value added as the head of the list
newNode ← node(value)
newNode.next ← head
head ← newNode
if(tail = Ø)
tail ← newNode
end Prepend
Figure 7: This is an example of a nodelist prepend pseudocode.
prepend(value){
//create a node whose next property point to the previous head
const newHead = node(value, this.head)
this.head = newHead
if(!this.tail){
this.tail = newHead
}
}
Figure 8: This is an example of a nodelist prepend method implementation.
Figure 9: This is an example of visual representation of Node List Prepending.
Top comments (0)