Linked Lists in Python

In this Python tutorial, we will discuss about Linked Lists in Python. Also, we will see these below topics as:

• What are linked lists in python?
• Create a linked list in python
• Linked list program in python
• Traversing a linked list in python
• Inserting at the beginning of the linked list in python
• Inserting at the end of the linked list in python
• Deletion in a linked list in python

What are linked lists in python?

• A linked list in Python is a linear data structure, in which the element is not stored at contiguous memory locations.
• Each data element is connected to another data element in form of a pointer.
• Linked lists consist of the node where each node has a data field and a link to the next node.
• The first node is called the head, and it is the starting point of iteration through a list.
• The last node has its next reference pointing to none which means it is the end of the list.
• Python does not have linked lists in its standard library.

You may like Python copy file (Examples)

Create a linked list in python

Now, we can see how to create a linked list in python.

Let’s create a single node, firstly we will make a Node class that holds some data and a pointer next, which will be used to point to the next node in the linked list.

Example:

class Node:
  def__init__(self, data, next=None):
    self.data = data
    self.next = next
s = Node(5)
print(s.data)

After writing the above code (create a linked list in python), when you will print “s.data” then the output will appear as “5”. Here, I have created a single node “s = Node(5)” and after print, it will return the data of the node.

You can refer to the below screenshot for create a linked list in python.

Linked list program in python

• First, create a class Node with instance variables data and next.
• Now, I will create a class Linkedlist with instance variables head and last_node.
• The variable head points to the first element in the linked list while last_node points to the last.
• Also, define methods append and display inside the class linkedlist to append data and to display a linked list
• Create an instance for a linked list, append data to it, and display it.

Example:

class Node:
    def__init__(self, data):
       self.data = data
       self.next = None
class Linkedlist:
    def__init__(self):
       self.head = None
       self.last_node = None
    def append(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next
    def display(self):
        curr = self.head
        while curr is not None:
            print(curr.data, end = ' ')
            curr = curr.next
my_llist = Linkedlist()
a = int(input('How many elements you will like to add? '))
for i in range(a):
    data = int(input('Enter data item: '))
    my_llist.append(data)
print('The linked list: ', end = ' ')
my_llist.display()

After writing the above code (linked list program in python), when you will display the list then the output will appear. Here, the user is asked for the number of elements to add, and using a loop the data will be appended to the linked list. The linked list value will be displayed in the output.

You can refer to below Output:

Read: Python NumPy read CSV

Traversing a linked list in python

Traversing means going through every single node, singly linked list traverse in forward direction starting with the head of the linked list and ending at the node which has next value as None.

Example:

class Node:
    def__init__(self, data=None):
       self.data = data
       self.next = None
class Linkedlist:
    def__init__(self):
       self.headvalue = None
    def listprint(self):
        printvalue = self.headvalue
        while printvalue is not None:
            print (printvalue.data)
            printvalue = printvalue.next
list = Linkedlist()
list.headvalue = Node("first")
x2 = Node("second")
x3 = Node("third")
list.headvalue.next = x2
x2.next = x3
list.listprint()

After writing the above code (traversing a linked list in python), when you will print then the output will appear as “first second third”. Here, we simply print the value of the current data item and also the next data item by assigning the pointers of the next node.

You can refer to the below screenshot for traversing a linked list in python.

Read Python NumPy empty array

Inserting at the beginning of the linked list in Python

Now, we will see how to Insert at the beginning of the linked list.

To insert at the beginning of the linked list, we will add a new node before the head of the given linked list. The newly added node will become the new head of the linked list.

Example:

class Node:
    def__init__(self, data=None):
       self.data = data
       self.next = None
class Linkedlist:
    def__init__(self):
       self.headvalue = None
    def listprint(self):
        printvalue = self.headvalue
        while printvalue is not None:
            print (printvalue.data)
            printvalue = printvalue.next
     def Atbegining(self,newdata):
         NewNode = Node(newdata)
         NewNode.next = self.headvalue
         self.headvalue = NewNode
my_list = Linkedlist()
my_list.headvalue = Node("jan")
x2 = Node("feb")
x3 = Node("march")
my_list.headvalue.next = x2
x2.next = x3
my_list.Atbegining("dec")
my_list.listprint()

After writing the above code (inserting at the beginning of the linked list in python), when you will print then the output will appear as “dec jan feb march”. Now, we will call the function that will add at the start of the list and the new node is inserted at the beginning

You can refer to the below screenshot for inserting at the beginning of the linked list.

You can refer to below Output:

Inserting at the end of the linked list in python

The node is being added to the end of the linked list, this involves pointing the next pointer of the last node to the new data node of the linked list. Now, the current last node will become the second last data and the new node become the last node of the linked list.

Example:

class Node:
    def__init__(self, data=None):
       self.data = data
       self.next = None
class Linkedlist:
    def__init__(self):
       self.headvalue = None
    def AtEnd(self,newdata):
         NewNode = Node(newdata)
         if self.headvalue is None:
             self.headvalue = NewNode
             return
         last = self.headvalue
         while(last.next):
             last = last.next
         last.next=NewNode
     def listprint(self):
         printvalue = self.headvalue
         while printvalue is not None:
             print (printvalue.data)
             printvalue = printvalue.next
my_list = Linkedlist()
my_list.headvalue = Node("jan")
x2 = Node("feb")
x3 = Node("march")
my_list.headvalue.next = x2
x2.next = x3
my_list.AtEnd("april")
my_list.listprint()

After writing the above code (inserting at the end of the linked list in python), when you will print then the output will appear as ” jan feb march april”. Now, we will call the function that will add the new node at the end of the list.

You can refer to the below screenshot for inserting at the end of the linked list in python.

You can refer to below Output:

Read: Python NumPy log + Examples

Deletion in a linked list in python

Let’s see how we can delete a node in linked list.

To delete a node in a linked list, we will find the previous node of the node to be deleted. We will change the next of the previous node and a function is called to remove a node.

Example:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
class Linkedlist:
    def __init__(self):
        self.head = None
    def Atbegining(self, data_n):
        NewNode = Node(data_n)
        NewNode.next = self.head
        self.head = NewNode
    def RemoveNode(self, Removekey):
        Headvalue = self.head
        if (Headvalue is not None):
            if (Headvalue.data == Removekey):
                self.head = Headvalue.next
                Headvalue = None
                return
        while (Headvalue is not None):
            if Headvalue.data == Removekey:
                break
            previous = Headvalue
            Headvalue = Headvalue.next
        if (Headvalue == None):
            return
        previous.next = Headvalue.next
        Headvalue = None
    def list_print(self):
        printvalue = self.head
        while (printvalue):
            print(printvalue.data),
            printvalue = printvalue.next
my_list = Linkedlist()
my_list.Atbegining("jan")
my_list.Atbegining("feb")
my_list.Atbegining("march")
my_list.RemoveNode("jan")
my_list.list_print()

After writing the above code (inserting at the end of the linked list in python), when you will print then the output will appear as ” march feb”. Now, we will call the function that will remove the specified node from the list.

You can refer to the below Output:

You may like the following Python tutorials:

• How to display calendar in Python
• How to make a calculator in Python
• Regular Expressions in Python
• Python print 2 decimal places
• Python Recursion
• Increment and Decrement operators in Python
• Constructor in Python
• Python Anonymous Function (Lambda Function)
• Union of sets Python + Examples

In this Python tutorial, we have learned about the Linked Lists in Python. Also, we covered these below topics:

• What are linked lists in python?
• Create a linked list in python
• Linked list program in python
• Traversing a linked list in python
• How to Insert at the beginning of the linked list in python
• How to Insert at the end of the linked list in python
• Deletion in a linked list in python