Data Structures for Coding Interviews in Python/

...

/

Singly Linked List Insertion

Singly Linked List Insertion

Let's look at the Pythonic implementation for the insertion of a node in a linked list.

We'll cover the following...

Types of Insertion #

The three types of insertion strategies used in singly linked-lists are:

  1. Insertion at the head
  2. Insertion at the tail
  3. Insertion at the kth index

Insertion at Head #

This type of insertion means that we want to insert a new element as the first element of the list.

As a result, the newly added node will become the head, which in turn will point to the previous first node.

For a better understanding of the Insertion At Head method, check out the illustration below:

Implementation

The implementation of this operation is simple and straightforward. It is all about correctly manipulating the next_element of the node being inserted.

Take a look at the implementation for insert_at_head below:

Python 3.5
from Node import Node
class LinkedList:
    def __init__(self):
        self.head_node = None
    # Insertion at Head
    def insert_at_head(self, data):
        # Create a new node containing your specified value
        temp_node = Node(data)
        # The new node points to the same node as the head
        temp_node.next_element = self.head_node
        self.head_node = temp_node  # Make the head point to the new node
        return self.head_node  # return the new list
    def is_empty(self):
        if self.head_node is None:
            return True
        else:
            return False
# Supplementary print function
    def print_list(self):
        if(self.is_empty()):
            print("List is Empty")
            return False
        temp = self.head_node
        while temp.next_element is not None:
            print(temp.data, end=" -> ")
            temp = temp.next_element
        print(temp.data, "-> None")
        return True
list = LinkedList()
list.print_list()
print("Inserting values in list")
for i in range(1, 10):
    list.insert_at_head(i)
list.print_list()

Explanation

To start things off, let’s explain the function called print_list(self) ...