An Interest In:
Web News this Week
- April 1, 2024
- March 31, 2024
- March 30, 2024
- March 29, 2024
- March 28, 2024
- March 27, 2024
- March 26, 2024
Some of Our Sources
- Techcrunch
- The Logo Smith
- Creative Curio
- Inspiredology
- Web Designer Depot
- Crazy Leaf Design
- Line 25
- Web Resource Source
- Codrops
- The Verge
Help Webnuz
Referal links:
Singly Linked Lists Implementation in JavaScript and Python
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 = Noneclass 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 selflist = 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 selfShift
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 tempUnshift
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 selfGet
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 currentset
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 FalseInsert
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 selfRemove
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 selfReverse
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 selfFinal 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 = Noneclass 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 selflist = SLL()list.push(20)list.push(21)list.push(22)list.push(23)print("|||||||||||||")list.traverse_listprint("***************")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.
Original Link: https://dev.to/edwardcashmere/singly-linked-lists-implementation-in-javascript-and-python-1ao5
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To