Skip to content

Linked Lists

linked lists#

I have never been good at linked lists and even more broader - pointer logic. In this post I want to show a practical example of a linked list implementation in python and how to use it.

The main advantage of a linked list is that it does not need to be stored in a continuous block in memory and can live in a random place. The disadvantage is we can’t just access a node - the list has to be traversed.

The Python Implementation#

This Singly linked list implementation was taken from hackerrank:

class SinglyLinkedListNode:
    def __init__(self, node_data): = node_data = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_node(self, node_data):
        node = SinglyLinkedListNode(node_data)

        if not self.head:
            self.head = node
   = node

        self.tail = node

To use it:

my_linked_list = SinglyLinkedList()

Moving it Around#

Instead of passing the linked list around. Sometimes it is preferable to just send a single node (really? when is that preferable and why? - recursion?)

That is all the current function needs to know as the node has the reference to the next and the function can iterate from the current node till the tail of the linked list.

Printing a linked list#

To print a linked list you can use a while loop or recursion.

The recursion example:

def print_linked_list(head):
    Print a singly linked list

what happens is you print the current nodes data attribute then if the current node has a next node - run the function to print the linked list with that node.

The while example:

def print_linked_list_while(head):
    Print a single linked list in a while loop
        head =

The timing were inconclusive:

  • while loop: 10000 times - 0.702690217, 50000 times - 8.423126091
  • recursion: 10000 times - 0.388262048, 50000 times - 7.361549832

Inserting a node at the Tail#

My successful attempt (but probably not optimal):

def insertNodeAtTail(head, data):
    initial_node = head
    node = SinglyLinkedListNode(data)
    if head is None:
        return node
    # Get the the end
    while ( is not None):
        head =
    # Set the next node as the new tail node = node
    return initial_node

Inserting a node at the head#

def insertNodeAtHead(llist, data):
    node = SinglyLinkedListNode(data) = llist
    return node

Inserting a node within a linkedlist#

Whenever dealing with positions not at the start or the end - a temporary node is needed to do changes and switches

def insertNodeAtPosition(llist, data, position):
    head = llist
    new_node = SinglyLinkedListNode(data)
    if llist is None:
        return new_node
        # index position form 0
        position = position - 1
        while (position > 0 and is not None):
            llist =
            position -= 1
        temp = = new_node = temp
    return head

Deleting a Node#

When deleting a node a reference will always be needed to the prior node as the prior nodes next attribute will (the case of the first and last node are handled with if statements)

def deleteNode(llist, position):
    if position == 0:
    head = llist
    prior_node = llist

    position -= 1
    while (position > 0):
        prior_node =
        position -= 1

    current_node =
    if is not None:
        next_node =
        next_node = None = next_node
    return head

Since the linked list can only be processed in a single direction - we could read the entire list until == None then print it and set the prior nodes next to None

I went with using a list:

def reversePrint(llist):
    items = []
    while (llist):
    for item in items[::-1]:

Reverse a Linked List#

Reversing a linked list - at the core is changing the next to point to the prior node - instead of the next one - for all nodes along the chain. We can process it one way - swapping the next references all the way until the end returning the head. Whenever making changes in teh middle - we require a temporary node and have references to 3 nodes at a time

def reverse(llist):
    prior_node = None
    current_node = llist
    next_node =

        temp = = prior_node
        prior_node = current_node
        current_node = temp

    # at this point the prior_node is the head of the list
    return prior_node

Comparing 2 Linked Lists#

def compare_lists(llist1, llist2):
    while( ==
        llist1 =
        llist2 =
        if not llist1 and not llist2:
            return 1
        elif not llist1 or not llist2:
            return 0
    return 0

Delete Even numbers in a linked list#

def delete_even_nodes(head):
    Remove nodes that are even
    odd_head = head
    while ( % 2 == 0):
        head =

    odd_head = head
    current_node =
    prior_node = odd_head
    while (current_node):
        if % 2 == 0:
            # skip it
   = next_node
            # otherwise ensure current node is maintained
            prior_node = current_node
        current_node = next_node

    return odd_head