What is a Linked List?
A linked list according to codementor is a data structure that can store an indefinite amount of items. These items are connected using pointers in a sequential manner. The elements of a linked list are called the nodes. A node has two fields i.e. data and next. The data field contains the data being stored in that specific node. It cannot just be a single variable. There may be many variables presenting the data section of a node. The next field contains the address of the next node. So this is the place where the link between nodes is established. I will use the abbrev SLL to refer to a linked list.
My definition is simple, it is a data structure that consists of nodes with a value property for storing data and the next property pointing to the next node. In this way, a node only knows about its next node and not about the rest of the nodes in the chain.
Operations we to be Implemented
- push //add node a the end
- pop // remove node at the end
- shift // remove node at the beginning
- unshift // add a node at the beginning
- get // get node at a specific index or according to criteria
- set // change node value attribute
- insert //
- remove
- reverse // reverse the direction of the list
NB: Below I have done a deep dive into each function or method implementation. All the functions or methods are inside the class: Skip to the end to see the full code implementation then comeback and follow-through
Let's begin, ps: I will be doing the implementations in both Javascript and Python.
Push
In the push function, you will always be adding a node at the end of the list. The steps to follow are outlined below.
Step 1 - Create a newNode with given value and newNode → next as NULL.
Step 2 - Check whether list is Empty (head == NULL).
Step 3 - If it is Empty then, set head = newNode.
Step 4 - If it is Not Empty then point the tails next attribute to the newNode
Step 5 - then reset the tail to point to the newNode and increment the size
code implementation in JavaScript:
class Node{
constructor(val){
this.val= val
this.next=null
}
}
class SLL{
constructor(){
this.head= null
this.tail= null
this.size= 0
}
push(val){
let newNode= new Node(val);
if(!this.head){
this.head=newNode
this.tail= newNode
this.size++
return this
}
this.tail.next = newNode
this.tail = newNode
this.size++
return this
}
}
let list =new SLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
In python:
class Node:
def __init__(self, val):
self.val = val
self.next = None
class SLL:
def __init__(self):
self.head=None
self.tail= None
self.size=0
def traverse_list(self):
if(self.head is None):
print("No elements in this list")
return
else:
n = self.head
while n is not None:
print(n.val)
n = n.next
def push(self,val):
newNode = Node(val)
if(self.head == None):
self.head = newNode
self.tail = newNode
self.size+=1
return self
self.tail.next= newNode
self.tail = newNode
self.size+=1
return self
list = SLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
list.traverse_list()
Pop
In the pop function, this involves always removing from the end. The steps to follow are as below
step 1 - Handle the edge case if the list is empty return None or undefined
step 2 - Create a current and newTail variable, set the current variable to the head node then set the newTail to the current variable
step 3 - traverse the list while current.next exists and setting newTail equal to the current node after each iteration.
The loop will break at the n-1 node if we assume the size of the nodes is n
step 4 - Set the tail attribute equal to the new tail. the tail .next equal to null and decrement the size of the list by 1.
step 5 - check if the size is zero, if so set the head and tail equal to None or null then return the removed node or list
Code implementation in Javascript :
pop(){
if(!this.head) return undefined;
let current= this.head;
let newTail=current;
while(current.next){
newTail = current;
current= current.next;
}
this.tail= newTail;
this.tail.next= null;
this.size--;
if(this.size ===0){
this.head = null;
this.tail = null;
}
return this
}
In python:
def pop(self):
if self.head ==None:return
current = self.head
new_tail = None
while current.next is not None:
new_tail = current
current = current.next
self.tail = new_tail
self.tail.next = None
self.size-=1
if self.size == 0:
self.head = None
self.tail = None
return self
Shift
This involves removing the first node in the list.
The steps to follow are below:
step 1: Check if the head exists otherwise return early
step 2: Initiate a variable called temp set it equal to the head property
step 3: set the head property to be the current heads next property
step 4: decrement the size by 1
step 5: Edge case check if the size is down to zero if it is set the tail to null and return the list
Code implementation in Javascript :
shift(){
if(!this.head) return undefined
let temp = this.head
this.head = this.head.next
this.size --
if(this.size ===0){
this.tail =null
}
return temp
}
In python:
def shift(self):
if self.head == None: return
temp = self.head
self.head = self.head.next
self.size-=1
if(self.size == 0):
self.tail = None
return temp
Unshift
From the name unshift you can guess it is the opposite of shift and it involves adding a node a the beginning. Follow the steps below:
step 1: Create a variable newNode and instantiate the Node class will the val passed in.
step 2: If there is no head property set the head property and tail property equal to the newNode
step 3: if there is a head property set the newNodes's next property to the head property and then set the head property to the newNode
step 4: Increment the size by 1 and return the list
Code implementation in Javascript :
unshift(val){
let newNode = new Node(val);
if(!this.head){
this.head= newNode;
this.tail = newNode;
}else{
newNode.next = this.head
this.head = newNode
}
this.size++
return this
}
In python:
def unshift(self,val):
newNode = Node(val)
if self.head == None:
self.head = newNode
self.tail = newNode
else:
newNode.next = self.head
self.head = newNode
self.size+=1
return self
Get
Get method is just is a search criterion for a node it can use an index or value of the node but in this case, I will just use the index. Follow the steps outline below:
step 1: If the index is less than 0 or greater than or equal to the size property return early
step 2 Create variable count set to zero , create variable current set it equal to the head property
step 3: count is not equal to index set current=current.next and increment count by 1
step 4: when the loop breaks return current
Code implementation in Javascript :
get(index){
if(index<0 || index >= this.size)return undefined;
let count=0;
let current= this.head;
while(count !== index){
current= current.next;
count++
}
return current;
}
In python:
def get(self,index):
if index <0 or index >=self.size:return
current= self.head
count = 0
while count != index:
current = current.next
count+=1
return current
set
This method will use the Get method to find the node we want and set its value attribute to something else. Follow the steps outlined below:
step 1 : Create a node variable set it to the function
getwith index passed in as a parameter
step 2 : If the node variable is set to a Non-null or Non- None value set the val property of the node to the new val then return true otherwise return false
Code implementation in Javascript :
set(index, val){
let node = this.get(index);
if(node){
node.val = val;
return true;
}
return false;
}
In python:
def set(self,index,val):
node = self.get(index)
if node :
node.val = val
return True
return False
Insert
This method will insert a node at a specific point, it will also use the Get method as a helper method to determine where to insert the node. Follow the steps below:
Step 1: If the index parameter is less than zero or greater than the size property return early
step 2: if the index parameter is equal to zero, the return theunshiftmethod with the val parameter passed in
step 3: if the index is equal to the size property return thepushmethod with the val parameter passed in
step 4: Create a variable newNode and instantiate the Node class will the val passed in.
step 5: Get the node at theindex -1position
step 6: Create a temp variable and set it equal to the current node's next property
step 7: set the current node's next property to the newNode and newNodes's next property to temp.
step 8: Increment the size property by 1 and return the list
Code implementation in Javascript :
insert(index, val){
if(index<0 || index > this.size ) return undefined
if(index === 0){
this.unshift(val);
}else if(index === this.size){
this.push(val);
}else{
let newNode = new Node(val);
let node = this.get(index-1);
let temp = node.next;
node.next = newNode;
newNode.next = temp;
}
this.size++;
return this;
}
In python:
def insert(self,index, val):
if index<0 or index> self.size: return
if index == 0: return self.unshift(val)
if index == self.size: return self.push(val)
newNode = Node(val)
prevNode = self.get(index-1)
temp = prevNode.next
prevNode.next = newNode
newNode.next = temp
self.size+=1
return self
Remove
This method removes an element from the list.The steps to follow are outlined below:
Step 1: If the index parameter is less than zero or greater than or equal to the size property return early
step 2: if the index parameter is equal to zero, the return theshiftshift method.
step 3: if the index is equal to the size property minus
1 return thepopmethod.
step 4: Create a variable prevNode and set it to the results ofgetmethod withindex-1.
step 5: Get the node at theindex -1position
step 6: Create a temp variable and set it equal to the prevNode's next property
step 7: set the prevNode's next property to the temp's variable next property
step 8: decrement the size property by 1 and return the list
Code implementation in Javascript :
remove(index){
if(index<0 || index >= this.size ) return undefined
if(index === 0) return this.shift()
if(index === this.size-1) return this.pop()
let prevNode = this.get(index-1)
let temp = prevNode.next
prevNode.next = temp.next
this.size--
return this
}
In python:
def remove(self,index):
if index<0 or index>= self.size: return
if index == 0:
return self.shift()
if index == self.size-1:
return self.pop()
prevNode = self.get(index-1)
temp = prevNode.next
prevNode.next = temp.next
self.size-=1
return self
Reverse
This method will reverse the direction of the list. The start will be the end and the end the new start. Basically, we will be starting from the end going backwards to the start.The steps to follow are outlined below
step 1 : Create a node variable and set it equal to head property
step 2: Set the head property to the tail property and the tail property to the node variable
step 3: Create a Next and prev variable and set them both to null or None.
step 4: Start a loop for when it is within the size property's range take 1 step from zero.
step 5: In each step set the Next variable to the current node's next property, set the current node's next property to the prev variable, set the prev variable to the current node and finally set the node variable to the Next variable.
step 6: Return the list
NB If you check the final solution there is an extra method called print, the method puts the values in an array in order and returns the array, I included it for testing the reverse method only, otherwise, it is not needed. If you print the list for the first time, it should return the list in the order entered, reverse the list and print again. the array returned should be in reverse to show the operation was successfull.
Code implementation in Javascript :
reverse(){
let node = this.head;
this.head= this.tail; // 20 -> 21 -> 22 -> 23
this.tail = node; // reversed 21 -> 20 -> null
let Next,
prev=null;
for(let i =0;i< this.size;i++){
Next= node.next
node.next=prev
prev = node
node = Next
}
return this
}
In python:
def reverse(self):
node = self.head
self.head = self.tail
self.tail = node
prev = Next =None
for i in range(self.size):
Next = node.next
node.next = prev
prev = node
node = Next
i+=1
return self
Final Code solution for JavaScript :
class Node{
constructor(val){
this.val= val
this.next=null
}
}
class SLL{
constructor(){
this.head= null
this.tail= null
this.size= 0
}
push(val){
let newNode= new Node(val);
if(!this.head){
this.head=newNode
this.tail= newNode
this.size++
return this
}
this.tail.next = newNode
this.tail = newNode
this.size++
return this
}
pop(){
if(!this.head) return undefined;
let current= this.head;
let newTail=current;
while(current.next){
newTail = current;
current= current.next;
}
this.tail= newTail;
this.tail.next= null;
this.size--;
if(this.size ===0){
this.head = null;
this.tail = null;
}
return this;
}
//shift
shift(){
if(!this.head) return undefined
let temp = this.head;
this.head = this.head.next;
this.size --;
if(this.size ===0){
this.tail =null;
}
return temp
}
//unshift
unshift(val){
let newNode = new Node(val);
if(!this.head){
this.head= newNode;
this.tail = newNode;
}else{
newNode.next = this.head;
this.head = newNode;
}
this.size++;
return this;
}
//get
get(index){
if(index<0 || index >= this.size)return undefined;
let count=0;
let current= this.head;
while(count !== index){
current= current.next;
count++
}
return current;
}
//set
set(index, val){
let node = this.get(index);
if(node){
node.val = val;
return true;
}
return false;
}
//insert
insert(index, val){
if(index<0 || index > this.size ) return undefined
if(index === 0){
this.unshift(val);
}else if(index === this.size){
this.push(val);
}else{
let newNode = new Node(val);
let node = this.get(index-1);
let temp = node.next;
node.next = newNode;
newNode.next = temp;
}
this.size++;
return this;
}
//remove
remove(index){
if(index<0 || index >= this.size ) return undefined
if(index === 0) return this.shift()
if(index === this.size-1) return this.pop()
let prevNode = this.get(index-1)
let temp = prevNode.next
prevNode.next = temp.next
this.size--
return this
}
//reverse
reverse(){
let node = this.head;
this.head= this.tail; // 20 -> 21 -> 22 -> 23
this.tail = node; // reversed 21 -> 20 -> null
let Next,
prev=null;
for(let i =0;i< this.size;i++){
Next= node.next
node.next=prev
prev = node
node = Next
}
return this
}
//print
print(){
let current= this.head
let arr = []
while(current){
arr.push(current.val)
current = current.next
}
return arr
}
}
let list =new SLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
for Python:
class Node:
def __init__(self, val):
self.val = val
self.next = None
class SLL:
def __init__(self):
self.head=None
self.tail= None
self.size=0
def traverse_list(self):
if(self.head is None):
print("No elements in this list")
return
else:
n = self.head
while n is not None:
print(n.val)
n = n.next
def push(self,val):
newNode = Node(val)
if(self.head == None):
self.head = newNode
self.tail = newNode
else:
self.tail.next= newNode
self.tail = newNode
self.size+=1
return self
def pop(self):
if self.head ==None:return
current = self.head
new_tail = None
while current.next is not None:
new_tail = current
current = current.next
self.tail = new_tail
self.tail.next = None
self.size-=1
if self.size == 0:
self.head = None
self.tail = None
return self
def shift(self):
if self.head == None: return
temp = self.head
self.head = self.head.next
self.size-=1
if(self.size == 0):
self.tail = None
return temp
def unshift(self,val):
newNode = Node(val)
if self.head == None:
self.head = newNode
self.tail = newNode
else:
newNode.next = self.head
self.head = newNode
self.size+=1
return self
def get(self,index):
if index <0 or index >=self.size:return
current= self.head
count = 0
while count != index:
current = current.next
count+=1
return current
def set(self,index,val):
node = self.get(index)
if node :
node.val = val
return True
return False
def insert(self,index, val):
if index<0 or index> self.size: return
if index == 0: return self.unshift(val)
if index == self.size: return self.push(val)
newNode = Node(val)
prevNode = self.get(index-1)
temp = prevNode.next
prevNode.next = newNode
newNode.next = temp
self.size+=1
return self
def remove(self,index):
if index<0 or index>= self.size: return
if index == 0:
return self.shift()
if index == self.size-1:
return self.pop()
prevNode = self.get(index-1)
temp = prevNode.next
prevNode.next = temp.next
self.size-=1
return self
def print(self):
arr=[]
current= self.head
while current:
arr.append(current.val)
current= current.next
return arr
def reverse(self):
node = self.head
self.head = self.tail
self.tail = node
prev = Next =None
for i in range(self.size):
Next = node.next
node.next = prev
prev = node
node = Next
i+=1
return self
list = SLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
print("|||||||||||||")
list.traverse_list
print("***************")
print(list.print())
print("===============")
list.reverse()
print("===============")
print(list.print())
Advantages Of Linked List:
- Dynamic data structure: A linked list is a dynamic arrangement so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list.
- No memory wastage: In the Linked list, efficient memory utilization can be achieved since the size of the linked list increase or decrease at run time so there is no memory wastage and there is no need to pre-allocate the memory.
- Implementation: Linear data structures like stack and queues are often easily implemented using a linked list. Insertion and Deletion Operations: Insertion and deletion operations are quite easier in the linked list. There is no need to shift elements after the insertion or deletion of an element only the address present in the next pointer needs to be updated.
Disadvantages Of Linked List:
- Memory usage: More memory is required in the linked list as compared to an array. Because in a linked list, a pointer is also required to store the address of the next element and it requires extra memory for itself.
- Traversal: In a Linked list traversal is more time-consuming as compared to an array. Direct access to an element is not possible in a linked list as in an array by index. For example, for accessing a mode at position n, one has to traverse all the nodes before it.
- Reverse Traversing: In a singly linked list reverse traversing is not possible, but in the case of a doubly-linked list, it can be possible as it contains a pointer to the previously connected nodes with each node. For performing this extra memory is required for the back pointer hence, there is a wastage of memory.
- Random Access: Random access is not possible in a linked list due to its dynamic memory allocation.
Conclusion
The implementation of a linked list is language agnostic, once you understand the logic behind it, you can implement it with any language of your choosing.Just follow the steps outlined above.
Top comments (0)