Open In App

Python Linked List

Last Updated : 09 Jul, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

In this article, we will learn about the implementation of a linked list in Python. To implement the linked list in Python, we will use classes in Python. Now, we know that a linked list consists of nodes and nodes have two elements i.e. data and a reference to another node. Let’s implement the node first. 

What is Linked List in Python

A linked list is a type of linear data structure similar to arrays. It is a collection of nodes that are linked with each other. A node contains two things first is data and second is a link that connects it with another node. Below is an example of a linked list with four nodes and each node contains character data and a link to another node. Our first node is where head points and we can access all the elements of the linked list using the head.

Python Linked List

Linked List

Creating a linked list in Python

In this LinkedList class, we will use the Node class to create a linked list. In this class, we have an __init__ method that initializes the linked list with an empty head. Next, we have created an insertAtBegin() method to insert a node at the beginning of the linked list, an insertAtIndex() method to insert a node at the given index of the linked list, and insertAtEnd() method inserts a node at the end of the linked list. After that, we have the remove_node() method which takes the data as an argument to delete that node. In the remove_node() method we traverse the linked list if a node is present equal to data then we delete that node from the linked list. Then we have the sizeOfLL() method to get the current size of the linked list and the last method of the LinkedList class is printLL() which traverses the linked list and prints the data of each node.

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.

Python 
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Insertion in Linked List

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.

Python 
def insertAtBegin(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        return
    else:
        new_node.next = self.head
        self.head = new_node

Insert a Node at a Specific Position in a Linked List

This method inserts the node at the given index in the linked list. In this method, we create a new_node with given data , a current_node that equals to the head, and a counter ‘position’ initializes with 0. Now, if the index is equal to zero it means the node is to be inserted at begin so we called insertAtBegin() method else we run a while loop until the current_node is not equal to None or (position+1) is not equal to the index we have to at the one position back to insert at a given position to make the linking of nodes and in each iteration, we increment the position by 1 and make the current_node next of it. When the loop breaks and if current_node is not equal to None we insert new_node at after to the current_node. If current_node is equal to None it means that the index is not present in the list and we print “Index not present”.

Python 
# Method to add a node at any index
# Indexing starts from 0.
def insertAtIndex(self, data, index):
    if (index == 0):
        self.insertAtBegin(data)

    position = 0
    current_node = self.head
    while (current_node != None and position+1 != index):
        position = position+1
        current_node = current_node.next

    if current_node != None:
        new_node = Node(data)
        new_node.next = current_node.next
        current_node.next = new_node
    else:
        print("Index not present")

Insertion in Linked List at End

This method inserts the node at the end 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 make a current_node equal to the head traverse to the last node of the linked list and when we get None after the current_node the while loop breaks and insert the new_node in the next of current_node which is the last node of linked list.

Python 
def inserAtEnd(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        return

    current_node = self.head
    while(current_node.next):
        current_node = current_node.next

    current_node.next = new_node

Update the Node of a Linked List

This code defines a method called updateNode in a linked list class. It is used to update the value of a node at a given position in the linked list.

Python 
# Update node of a linked list
# at given position
def updateNode(self, val, index):
    current_node = self.head
    position = 0
    if position == index:
        current_node.data = val
    else:
        while(current_node != None and position != index):
            position = position+1
            current_node = current_node.next

        if current_node != None:
            current_node.data = val
        else:
            print("Index not present")

Delete Node in a Linked List

Remove First Node from Linked List

This method removes the first node of the linked list simply by making the second node head of the linked list.

Python 
def remove_first_node(self):
    if(self.head == None):
        return
    
    self.head = self.head.next

Remove Last Node from Linked List

In this method, we will delete the last node. First, we traverse to the second last node using the while loop, and then we make the next of that node None and last node will be removed.

Python 
def remove_last_node(self):

    if self.head is None:
        return

    curr_node = self.head
    while (curr_node.next != None and curr_node.next.next != None):
        curr_node = curr_node.next

    curr_node.next = None

Delete a Linked List Node at a given Position

In this method, we will remove the node at the given index, this method is similar to the insert_at_inded() method. In this method, if the head is None we simply return else we initialize a current_node with self.head and position with 0. If the position is equal to the index we called the remove_first_node() method else we traverse to the one node before that we want to remove using the while loop. After that when we out of the while loop we check that current_node is equal to None if not then we make the next of current_node equal to the next of node that we want to remove else we print the message “Index not present” because current_node is equal to None.

Python 
# Method to remove at given index
def remove_at_index(self, index):
        if self.head == None:
            return

        current_node = self.head
        position = 0
        if position == index:
            self.remove_first_node()
        else:
            while(current_node != None and position+1 != index):
                position = position+1
                current_node = current_node.next

            if current_node != None:
                current_node.next = current_node.next.next
            else:
                print("Index not present")

Delete a Linked List Node of a given Data

This method removes the node with the given data from the linked list. In this method, firstly we made a current_node equal to the head and run a while loop to traverse the linked list. This while loop breaks when current_node becomes None or the data next to the current node is equal to the data given in the argument. Now, After coming out of the loop if the current_node is equal to None it means that the node is not present in the data and we just return, and if the data next to the current_node is equal to the data given then we remove that node by making next of that removed_node to the next of current_node. And this is implemented using the if else condition.

Python 
def remove_node(self, data):
    current_node = self.head

    # Check if the head node contains the specified data
    if current_node.data == data:
        self.remove_first_node()
        return

    while current_node is not None and current_node.next.data != data:
        current_node = current_node.next

    if current_node is None:
        return
    else:
        current_node.next = current_node.next.next

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 iterate through the linked list using a while loop until the current_node become None and print the data of current_node in each iteration and make the current_node next to it.

Python 
def printLL(self):
    current_node = self.head
    while(current_node):
        print(current_node.data)
        current_node = current_node.next

Get Length of a Linked List in Python

This method returns the size of the linked list. In this method, we have initialized a counter ‘size’ with 0, and then if the head is not equal to None we traverse the linked list using a while loop and increment the size with 1 in each iteration and return the size when current_node becomes None else we return 0.

Python 
def sizeOfLL(self):
    size = 0
    if(self.head):
        current_node = self.head
        while(current_node):
            size = size+1
            current_node = current_node.next
        return size
    else:
        return 0

Example of the Linked list in Python

In this example, After defining the Node and LinkedList class we have created a linked list named “llist” using the linked list class and then insert four nodes with character data ‘a’, ‘b’, ‘c’, ‘d’ and ‘g’ in the linked list then we print the linked list using printLL() method linked list class after that we have removed some nodes using remove methods and then print the linked list again and we can see in the output that node is deleted successfully. After that, we also print the size of the linked list.

Python 
# Create a Node class to create a node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Create a LinkedList class
class LinkedList:
    def __init__(self):
        self.head = None

    # Method to add a node at begin of LL
    def insertAtBegin(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        else:
            new_node.next = self.head
            self.head = new_node

    # Method to add a node at any index
    # Indexing starts from 0.
    def insertAtIndex(self, data, index):
        if (index == 0):
            self.insertAtBegin(data)
            
        position = 0
        current_node = self.head
        while (current_node != None and position+1 != index):
            position = position+1
            current_node = current_node.next

        if current_node != None:
            new_node = Node(data)
            new_node.next = current_node.next
            current_node.next = new_node
        else:
            print("Index not present")

    # Method to add a node at the end of LL
    def insertAtEnd(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while(current_node.next):
            current_node = current_node.next

        current_node.next = new_node

    # Update node of a linked list
        # at given position
    def updateNode(self, val, index):
        current_node = self.head
        position = 0
        if position == index:
            current_node.data = val
        else:
            while(current_node != None and position != index):
                position = position+1
                current_node = current_node.next

            if current_node != None:
                current_node.data = val
            else:
                print("Index not present")

    # Method to remove first node of linked list

    def remove_first_node(self):
        if(self.head == None):
            return

        self.head = self.head.next

    # Method to remove last node of linked list
    def remove_last_node(self):

        if self.head is None:
            return

        current_node = self.head
        while(current_node != None and current_node.next.next != None):
            current_node = current_node.next

        current_node.next = None

    # Method to remove at given index
    def remove_at_index(self, index):
        if self.head == None:
            return

        current_node = self.head
        position = 0
        if position == index:
            self.remove_first_node()
        else:
            while(current_node != None and position+1 != index):
                position = position+1
                current_node = current_node.next

            if current_node != None:
                current_node.next = current_node.next.next
            else:
                print("Index not present")

    # Method to remove a node from linked list
    def remove_node(self, data):
        current_node = self.head

        if current_node.data == data:
            self.remove_first_node()
            return

        while(current_node != None and current_node.next.data != data):
            current_node = current_node.next

        if current_node == None:
            return
        else:
            current_node.next = current_node.next.next

    # Print the size of linked list
    def sizeOfLL(self):
        size = 0
        if(self.head):
            current_node = self.head
            while(current_node):
                size = size+1
                current_node = current_node.next
            return size
        else:
            return 0

    # print method for the linked list
    def printLL(self):
        current_node = self.head
        while(current_node):
            print(current_node.data)
            current_node = current_node.next


# create a new linked list
llist = LinkedList()

# add nodes to the linked list
llist.insertAtEnd('a')
llist.insertAtEnd('b')
llist.insertAtBegin('c')
llist.insertAtEnd('d')
llist.insertAtIndex('g', 2)

# print the linked list
print("Node Data")
llist.printLL()

# remove a nodes from the linked list
print("\nRemove First Node")
llist.remove_first_node()
print("Remove Last Node")
llist.remove_last_node()
print("Remove Node at Index 1")
llist.remove_at_index(1)

# print the linked list again
print("\nLinked list after removing a node:")
llist.printLL()

print("\nUpdate node Value")
llist.updateNode('z', 0)
llist.printLL()

print("\nSize of linked list :", end=" ")
print(llist.sizeOfLL())

Output
Node Data
c
a
g
b
d

Remove First Node
Remove Last Node
Remove Node at Index 1

Linked list after removing a node:
a
b

Update node Value
z
b

Size of linked list : 2

Python Linked List – FAQs

What is a linked list in Python?

A linked list is a linear data structure where elements are stored in nodes. Each node contains data and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations.

Does Python have a linked list library?

Python does not have a built-in linked list library in its standard library. However, linked lists can be implemented using classes and references in Python.

How to create a linked list?

You can create a linked list in Python by defining a Node class and a LinkedList class. Here’s a basic example of how to implement a linked list:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # Reference to the next node
# LinkedList class manages the nodes and operations of the linked list
class LinkedList:
    def __init__(self):
        self.head = None  # Initialize an empty linked list
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")
# Example usage:
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.print_list()

Is tuple a linked list in Python?

No, a tuple is not a linked list in Python. Tuples are immutable sequences of elements stored in contiguous memory, whereas linked lists are mutable and elements are stored in separate nodes with references.

What are the types of linked list?

The main types of linked lists include:

  • Singly Linked List: Each node points to the next node in the sequence.
  • Doubly Linked List: Each node points to both the next and previous nodes.
  • Circular Linked List: Last node points back to the first node, forming a circle.
  • Sorted Linked List: Elements are stored in a sorted order based on a specific criterion.


author
sagar99
Improve
Next Article
Singly Linked List in Python

Similar Reads

Python3 Program to Rotate the sub-list of a linked list from position M to N to the right by K places
Given a linked list and two positions 'm' and 'n'. The task is to rotate the sublist from position m to n, to the right by k places. Examples: Input: list = 1->2->3->4->5->6, m = 2, n = 5, k = 2 Output: 1->4->5->2->3->6 Rotate the sublist 2 3 4 5 towards right 2 times then the modified list are: 1 4 5 2 3 6 Input: list
4 min read
Python | Convert list of string to list of list
Many times, we come over the dumped data that is found in the string format and we require it to be represented in the actual list format in which it was actually found. This kind of problem of converting a list represented in string format back to la ist to perform tasks is quite common in web development. Let's discuss certain ways in which this
7 min read
Python program to find middle of a linked list using one traversal
Given a singly linked list, find the middle of the linked list. Given a singly linked list, find the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the output should be 3. Method 1: Traverse the whole linked list and count the no. of nodes. Now traverse the list again till count/2 and return the n
5 min read
Python | Queue using Doubly Linked List
A Queue is a collection of objects that are inserted and removed using First in First out Principle(FIFO). Insertion is done at the back(Rear) of the Queue and elements are accessed and deleted from first(Front) location in the queue. Queue Operations:1. enqueue() : Adds element to the back of Queue. 2. dequeue() : Removes and returns the first ele
3 min read
Python | Stack using Doubly Linked List
A stack is a collection of objects that are inserted and removed using Last in First out Principle(LIFO). User can insert elements into the stack, and can only access or remove the recently inserted object on top of the stack. The main advantage of using LinkedList over array for implementing stack is the dynamic allocation of data whereas in the a
4 min read
Python Library for Linked List
Linked list is a simple data structure in programming, which obviously is used to store data and retrieve it accordingly. To make it easier to imagine, it is more like a dynamic array in which data elements are linked via pointers (i.e. the present record points to its next record and the next one points to the record that comes after it, this goes
5 min read
Pretty print Linked List in Python
Creating custom data types can be tricky, especially when you want to use it like any other data type. Linked List can be thought of as an example of a custom data type. In other languages, if you want to print the linked list, you would define a separate print function, something like pprint but it looks kind of odd, right? Like it would be great
3 min read
Linked list using dstructure library in Python
Dstructure is a Python library for creating data structures like linked list, stack, queue, hashmap, tree, etc. A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image: pip install dstructure Let's see how to cr
4 min read
Implementation of XOR Linked List in Python
Prerequisite: XOR Linked List An ordinary Doubly Linked List requires space for two address fields to store the addresses of previous and next nodes. A memory-efficient version of Doubly Linked List can be created using only one space for the address field with every node. This memory efficient Doubly Linked List is called XOR Linked List or Memory
6 min read
Random Singly Linked List Generator using Python
In this article, we will learn how to generate a singly linked list using random numbers. Prerequisite: Insertion in Linked List A Singly Linked List is a linear data structure. A linked list is a collection of nodes and in a singly linked list every node contains two things: Data Reference to the next node In this article, we will learn to generat
5 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox