Linked List implementation in Python

Intro

A linked list is a data structure which represents a sequence of nodes. In a singly linked list, each node points to the next node. In a doubly linked list, each node points to both the next and previous node.

To find nth element in the linked list, you have to iterate through n nodes which results in linear time complexity O(n). This is less efficient than array which has constant time complexity O(1) to access an element.

However, the advantage to use linked list is for insert and delete operation since it can be achieved in the constant time without shifting nodes around.

The following are the key methods to be implemented:

• insert(): add an item to the linked list
• remove(): remove a specified item from the linked list
• insertAt(index): insert an item at a given index
• deleteAt(index): delete an item at a given index
• find(): search an item in the linked list
• is_empty(): return if the linked list is empty or not
• count(): return the number of items in the linked list

Construct a node class

Before we implement a singly linked list, we need to construct a node class. The linked list would contain one or more nodes. Each node has a value and a pointer linked to the next node.

class Node:
    def __init__(self):
        self.val = None
        self.next = None

    def set_val(self, val):
        self.val = val

    def get_val(self):
        return self.val

    def set_next(self, next):
        self.next = next

    def get_next(self):
        return self.next

Build a singly Linked List

The first function in the linked list class is the constructor, which will be called whenever a linked list is initialized.

It can include three attributes:

• head: the first node in the linked list
• tail: the last node in the linked list
• count: the number of nodes in the linked list

Then we can build the other required functions according to the node pointer manipulations.

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    def count_nodes(self):
        return self.count

    # insert at the tail of list
    def insert(self, val):
        new_node = Node()
        new_node.set_val(val)

        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

        self.count += 1

    # insert at the given index
    def insertAt(self, val, index):
        new_node = Node()
        new_node.set_val(val)

        current_idx = 0
        current_node = self.head
        previous_node = current_node

        while current_idx < index and current_node.next != None:
            previous_node = current_node
            current_node = current_node.next
            current_idx += 1

        if current_idx == index:
            # found the index
            new_node.next = current_node
            previous_node.next = new_node

            # increase counter
            self.count += 1
        else:
            print("the specified index {} is invalid".format(index))

    # delete the specified node
    def deleteAt(self, index):
        current_idx = 0
        current_node = self.head
        previous_node = current_node

        while True:
            if current_idx < index:
                if current_node.next != None:
                    # move on to the next node
                    previous_node = current_node
                    current_node = current_node.next
                    current_idx += 1
                else:
                    print("invalid index {}".format(index))
                    break
            else:
                # found the index, delete it
                if current_node.next == None:
                    # this is tail
                    previous_node.next = None
                    self.tail = previous_node
                else:
                    # this is not tail
                    previous_node.next = current_node.next

                # decrease the counter
                self.count -= 1

                break

    def find(self, index):
        current_node = self.head
        current_idx = 0

        while current_node.next != None:
            if current_idx == index:
                return current_node.get_val()
            else:
                current_node = current_node.next

        print("invalid index {}".format(index))

    def print_list(self):
        current_node = self.head
        current_idx = 0

        while current_node.next != None:
            print(current_node.get_val())
            current_node = current_node.next

        # print the last node
        print(current_node.get_val())
        print("count: {}".format(self.count_nodes()))
        print()

Test the Linked List class

ll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(5)
ll.print_list()

ll.insertAt(4, 2)
ll.print_list()

ll.insertAt(3, 3)
ll.print_list()

ll.deleteAt(3)
ll.print_list()

Output:

1
2
5
count: 3

1
2
4
5
count: 4

1
2
4
3
5
count: 5

1
2
4
5
count: 4