Linked List is also similar to an array is a linear data structure but dissimilar in the manner of it doesn’t use contiguous memory location, it uses pointer by which elements are linked together. In Linked List, we can perform insertion and deletion task easily than an array. Linked list uses the dynamic size that means we can enhance or shrink the size of linked list at runtime.
Nodes: Nodes are similar to Pointers which store data and address of next element, and in linked List, all the nodes are connected by the link to each other.
Each node contains two parts (1) value or data and (2) Pointer to next node
Node creation in Linked List with Python:
#create a Class Node #initialize the object #assign value #initialize to next node as None class Node: def __init__(self,val): self.val=val self.next=None #create object of class Node one=Node(1) two=Node(2) three=Node(3) #points to next node one.next=three three.next=two #assign the value to variables start=one while start: print(start.val,end=" ") start=start.next Output 1 3 2
Head: First node is called Head.
Null: In the empty linked list the head node is called Null or the pointer of the last node represents null nodes.
Linked List creation using Python
#create a class of Linked List #initialize the class object and initialize head to None class LinkedList: def __init__(self): self.head=None
Types of Linked List
Linked List has three types:
- Single Linked List: A single linked list stores the data and pointer only in node but not store any pointer or reference to the previous node. A=>B=>C=>Null
- Double Linked List: A Doubly linked list contain extra pointer called the previous pointer. Null<=| |A| |=>| |B| |=>| |C| |=>Null
- Circular Linked List: In a Circular linked list all the elements are connected to each other in a circular way In this list there will be not Null value. A circular linked list is of two types as single circular and double circular linked list.
In this article, we will discuss Single Linked List.
Operations in Single Linked List
Traversing of the linked list means we have to print all the data points into the linked list from the starting node to last.
Python implementation of the Linked list traversing:
# travering function def traverseList(self): printvar=self.head while(printvar): print(printvar.val,end=" ") printvar=printvar.next
In the Linked list, there are three ways to insert a new node:
- At the beginning of the linked list
- Insert a node after an existing node
- At the last of the node
At the beginning of the linked list
In this scenario, we add a new node in the place of head node or if the head doesn’t exist we add a new node to the head node. For example 4=>5=>6 is a linked list and we want to add a new node 3 at the beginning of the linked list then we substitute head node by new node.
Algorithms for an inserting new node at the beginning of Node
- Create an object of Node assign a value into the node for example new_val
- Make head to next to the newly created node i.e new_val.next=head value
- Assign head to newly created node i.e head value=new_val
Programming implementation with python
def insertbefor(self,new_val): new_node=Node(new_val) new_node.next=self.head self.head=new_node
Insert a node after an existing node
In this scenario, we add a new node to an existing node. For example, 4=>5=>6 is a linked list and we want to add a new node 3 after 4 then the resulting linked list will be 4=>3=>5=>6.
Algorithm for inserting a new after an existing node.
- Firstly we will check that if the previous node present in the linked list or not
- Create a new object of Node or create the new node
- assign the previous node next to new node next
- make new node next to the previous node
Programming implementation with Python
def insertnext(self,prev,new_val): if prev is None: print("Previous node should be in Linkedlist") return new_node=Node(new_val) new_node.next=prev.next prev.next=new_node
At the last of the node
In this scenario we add a new node at the last of the node, For example, if we have 3=>4=>5=> and we want to add 6 from the last side then the new Linked list will be 3=>4=>5=>6.
Algorithm for implementing this scenario:
- Create a new node object
- check if head node is null or not if yes then make it new_node
- traverse till the last node
- change the last node to new node.
def insertlast(self,new_val): new_node=Node(new_val) if self.head is None: self.head=new_node return lastnode=self.head while lastnode.next: lastnode=lastnode.next lastnode.next=new_node
Deletion in Linked List
Deletion in linked list performed on the basis of the key. The first occurrence of key deleted if the key matches more than one element.
Algorithms for Deletion in Linked List
- Get the reference to key
- Store the head node
- If the head node matches the key then proceed for delete
- Search for the key to being deleted
- If the key node doesn’t present then return as it is linked list
- If key==node then unlink it from the linked list
Programming Implementation In Python
def deleteNode(self,key): tmp=self.head if tmp is not None: if tmp.val==key: self.head=tmp.next tmp=None return while tmp is not None: if tmp.val==key: break prev=tmp tmp=tmp.next if(t mp==None): return prev.next=tmp.next tmp=None
This is all basic information about how to implement linked list in python. I also recommend you to go through the whole process to solve the problem of data structure and implements linked list. It will enhance your skill in programming and problem-solving.
If you liked this article be sure to like this article and you have any questions related to this answer I will do my best to answer.