Linked List in Python with Example

We will be implementing a linked list in Python with Example and will go through various operations on the linked list. 

Suppose I have an array of student names and it this is a memory layout of those student’s names. 

names=[‘Tushar’,’Deepak’,’Tejas’,’Pushkar’] 

There are like the fire elements in this array if you want to insert an element  ‘Swati ‘ at location number 1 then it will insert ‘Swati’ at location number 1 and it will swap all the elements. So it will copy Deepak from location number 2, Tejas from location number 2 to 3, and so on. 

Index 0 Index 1 Index 2 Index 3   

Tushar

Deepak

Tejas

Pushkar

 

Index 0 Index 1 Index 2 Index 3 Index 4 

Tushar

Swati

Deepak

Tejas

Pushkar

 

Insert

Using an array or list is possible by using an insert function like that 

names.insert(1,’Swati’) 

Now let us discuss this data structure with individual values stored with two different areas of memory. That structure is called a linked list. 

0x1100 0x1104 0x1108 0x1112 0x1114 

Tushar

Deepak

Tejas

Pushkar

Sarika

A linked list is a sequence of data elements, which are connected together via links.  Each data element contains a connection to another data element in the form of a pointer. 

A Linked list is made up of nodes, where a node is made up of two parts: 

1. Data Part: Holds the data 
2. Address Part: Holds the address of the next node.

 

As you can see, every node has some data stored in it, and it also stores the location of the next node. It is not necessary that all the nodes get saved in contiguous memory locations, next to each other, that is why we need to store the location of the next node in the previous node to be able to access it like its a chain or list. 

Head is a pointer that always points to the first node of the list, if Head points to nothing, it means the linked list is empty. 

Our first node is where head points and we can access all the elements of the linked list using the head. 

Creating a Node Class 

We have created a Node class in which we have defined a __init__ function to initialize the node with the data passed as an argument and a reference with None because if we have only one node then there is nothing in its reference.

 

Insertion at Beginning in Linked List 

This method inserts the node at the beginning of the linked list. In this method, we create a new_node with the given data and check if the head is an empty node or not if the head is empty then we make the new_node as head and return else we insert the head at the next new_node and make the head equal to new_node.

 

Called a function insertAtBegin() using the object of the LinkedList class: 

 

Linked List Traversal in Python 

This method traverses the linked list and prints the data of each node. In this method, we made a current_node equal to the head and iterated through the linked list using a while loop until the current_node became None printed the data of current_node in each iteration, and made the current_node next to it.

 

Called a function printLL() using object of LinkedList class: 

 

The output of the program: 

 

Insert a Node at a Specific Position in a Linked List:

 

Called a function insertAtIndex()using the object of the LinkedList class:

 

The output of the program: 

 

Insertion in Linked List at End:

 

Called a function insertAtEnd()using an object of the LinkedList class:

 

The output of the program: 

 

Update the Node of a Linked List:

 

Called a function updateNode()using object of LinkedList class:

 

The output of the program: 

 

Get the Length of a Linked List in Python: 

 

Called a function sizeOfLL()using object of LinkedList class:

 

Output of the program: 

 

Just like insertion an element into a list, we can remove an element from first, last, and particular index positions. 

Advantages of a Linked List 

1. Insertion and Deletion are very easy, in the case of Linked List, because all we have to do is update the next pointer.
2. We can easily implement Stack and Queue data structures using Linked List. 

Disadvantages of a Linked List: 

Random access is not possible, to access any node we must traverse the  Linked List. That is why it is said, that if you want to carry out insertion and updation on a set of data use Linked List, but if you want to traverse and search for data, the array is better.

Do visit our channel: Click Here

 

Author:-
Deepali Shinkar
Call the Trainer and Book your free demo Class For Python

Call now!!! | SevenMentor Pvt Ltd.

© Copyright 2021 | SevenMentor Pvt Ltd.