Generic selectors
Exact matches only
Search in title
Search in content
wb_sunny

Linked Lists in Python

Linked List

Linked lists in Python are one of the most interesting abstract data types that have continued to stay in popularity since the C/C++ days. In this article, we’ll learn how to implement a Linked list in Python from scratch.

What is a Linked List?

A linked list is a linear data structure where each element is a separate object. The elements of a linked list, unlike an array, are not stored together in the memory.

Each element of the linked list points to the element after it. Here points mean that each element stores the address of the next element.

While traversing a linked list we use these pointers to jump from one node to the next.

For each linked list, there are a two elements that need to be considered:

  • The nodes – We handle them by creating a node class
  • The connection between nodes – We will handle this with the variables and lists in Python.

How to Create a Linked List in Python?

Let’s go over the steps to create a linked list in Python.

Create the Node Class

To create our own linked list we need to define a node class. Before we define a node class, we need to think about what fields should the class have.

A linked list node is supposed to store two things. These are :

  1. Data
  2. Address of the next node

Let’s define a node class with these two fields.

class Node(object):

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

Create the Linked-List class

Let’s make another class that will initialize an empty node for creating a linked list.

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

There are a few important functions that will be held within this class. Let’s go over the purpose and the definition for each of these classes.

1. Function to print the list

Let’s write a function to print our linked list. To print the linked list we need to traverse through the entire list and keep printing the data from each node.

def printList(self): 
        temp = self.head 
        while (temp): 
            print (temp.data, " -> ", end = '') 
            temp = temp.next_node
        print("")

2. Get size of the list

Let’s write a function that returns the size of the linked list. To calculate the size, we need to traverse through the entire list and keep a counter while doing so.

def size(self):
     current = self.head
     count = 0
     while current:
        count += 1
        current = current.next_node
     return count

This function will return the size of the linked list.

3. Insert a new node at the head

Let’s write a function to insert a new node at the head.

def insert_at_head(self, data):
      new_node = Node(data)
      new_node.next_node = self.head
      self.head = new_node

This will create a new node with the data and add it before the head. It then points the head of the linked list to this new node.

4. Get Next node

The function to get next node is given below :

 def get_next_node (self,node):
      return node.next_node.data

Create a New Linked List

Let’s write the main function and create a linked list using the class we created above.

llist = LinkedList() 

This line of code initializes the llist object with an empty node.

1. Adding nodes

Let’s add some data to this node.

llist.head = Node(1)

Create a few other nodes for the linked list.

 s = Node(2)
 t = Node(3) 

2. Create links between the nodes

Creating links between the individual nodes is the most important part of creating a linked list.

You can create the links using :

llist.head.next_node = s
s.next_node = t

3. Print the nodes of the list

To verify whether the list was created successfully or not we can use the print function.

llist.printList()

Output:

1  -> 2  -> 3 

4. Output the size of the list

To output the size of the list, call the size function we wrote above.

 print(llist.size())

Output :

3

5. Insert a new node

Let’s try inserting some data at the head of the linked list using the function above.

llist.insert_at_head(5)

We can print the list to verify.

llist.printList()

Output :

5  -> 1  -> 2  -> 3

6. Get next node

To get the next node:

print(llist.get_next_node(s))

Output:

3

Complete Implementation of Linked Lists in Python

The complete implementation is given below :

class Node(object):

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node


class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    def size(self):
     current = self.head
     count = 0
     while current:
        count += 1
        current = current.next_node
     return count
      
    def printList(self): 
        temp = self.head 
        while (temp): 
            print (temp.data, " -> ", end = '') 
            temp = temp.next_node
        print("")

    def insert_at_head(self, data):
      new_node = Node(data)
      new_node.next_node = self.head
      self.head = new_node

    def get_next_node (self,node):
      return node.next_node.data


if __name__=='__main__': 
  
    
    llist = LinkedList() 
  
    llist.head = Node(1) 
    s = Node(2) 
    t = Node(3) 
    llist.head.next_node = s;
    s.next_node = t
    llist.printList()
    print(s.data)
    print(llist.size())
    print(llist.get_next_node(s))
    llist.insert_at_head(5)
    llist.printList()

Conclusion

This tutorial covered the implementation of linked lists in Python. We created our own linked list from scratch and wrote some additional functions to print the list, get the size of the list and make insertions at the head.