Python doesn’t have inbuilt linked lists, you will have to create one. A linked list (as the name says it’s like a chain) is a sequence of elements and each element points to the next element (the first element has a value and points to the second, the second element has a value points to the third, and so on.. and the last element points to None). This is a simple singly linked list. Remember you cannot access elements of the linked list by value or you cannot extract elements at position X directly (in all these cases you will have to traverse the linked list.. from left to right). Right now we are just talking about a singly linked list.
Why do we need Linked List?
linked lists take less space! Elements of the array are stored continuously and once you declare an array your program will assign some additional space for it. reorganization of the array is a heavy operation as allocation has to be continuous. With Linked list allocation doesn’t need to be continuous.
The most common types of linked lists are Singly linked list, doubly linked list, circular linked list. The operations we will learn in this tutorial are creating a linked list, adding elements, removing element(s), searching elements, etc. To create a linked list you need to be familiar with python Objects and Classes.
you can see the head of the singly linked list points to the first element and the last element points to None.
- Each element of the linked list is commonly called Node (It has two things: data and pointer to next node or None)
- A node is an object
- Head is a pointer to the first element of the linked list.
Creating a Linked list in python
let’s create a Node class:
class Node: def __init__(self,data,nextnode=None): self.data=data nextnode=None node1=Node(5) node2=Node(10) node3=Node(11) node1.nextnode=node2 # link node1 object to node 2 node2.nextnode=node3 # link node2 object to node 3 print (node1.nextnode.data)
So what are we doing in the above code?
We have created a Node class with init method, whenever we call Node we create an object of type Node (which are individual nodes of linked list) we pass a value to when creating the object as its a required field. “nextnode” has a default value of “None” so it’s not a required field and by default, all Individual Nodes point to None They are not linked!
node1.nextnode=node2 ### this is saying node1 object to point to node2 object and that’s how we link the linked list.
How to delete an item in a linked list?
For the above-linked list if we want to delete an item and if you are given the Node to delete how will you proceed? Like if we want to delete Node C? The goal is to link B directly to D (then Node C will not be part of the linked list). If you are just given the Node object one easier option will be to copy the content of the next node to the current Node and point the current node to the Next.Next.. see below.
#delete node from the linked list node.val=node.next.val node.next=node.next.next
How to add an item in a linked list?
### create a linked list first class Node: def __init__(self,data,nextnode=None): self.data=data nextnode=None node1=Node(5) node2=Node(10) node3=Node(11) node1.nextnode=node2 # link node1 object to node 2 node2.nextnode=node3 # link node2 object to node 3, node3 points to None. #### insert in the beginning of linked list node0=Node(4) ### create a node node0.nextnode=node1 #### insert in between i.e. after node2 and before node3 ### in real scenarios you might have to find node based on it's value node25=Node(105) ##### create a node node2.nextnode=node25 ##### point node2 to node25 node25.nextnode=node3 ##### point node25 to node3 #### insert at end of the linked list #### Here we will first find the last node