Python: Implementing Linked List

1. Introduction

A linked list is a foundational data structure where elements, known as nodes, are connected linearly. Each node contains its data and a reference (or link) to the next node in the sequence. The primary advantage of linked lists over traditional arrays is that the former allows for efficient insertions and deletions because they don't need to shift elements around.

2. Program Overview

In this post, we'll create a basic singly linked list. We will implement the following operations:

1. append: Adds a new node at the end of the list.

2. display: Shows all the elements of the linked list.

3. is_empty: Checks if the linked list is empty.

4. length: Returns the number of elements in the linked list.

3. Code Program

class Node:
    def __init__(self, data):
        """Initialize the node with data and no reference to the next node."""
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        """Initialize the linked list with a head set to None."""
        self.head = None

    def append(self, data):
        """Add a new node with the given data at the end of the list."""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def display(self):
        """Print all the elements of the linked list."""
        curr_node = self.head
        while curr_node:
            print(curr_node.data, end=" -> ")
            curr_node = curr_node.next
        print("None")

    def is_empty(self):
        """Check if the linked list is empty."""
        return not self.head

    def length(self):
        """Return the number of elements in the linked list."""
        count = 0
        curr_node = self.head
        while curr_node:
            count += 1
            curr_node = curr_node.next
        return count

# Demonstration
llist = LinkedList()
print("is_empty:", llist.is_empty())  # True
llist.append(5)
llist.append(10)
llist.append(15)
llist.display()  # 5 -> 10 -> 15 -> None
print("length of the linked list:",llist.length())  # 3

Output:

is_empty: True
5 -> 10 -> 15 -> None
length of the linked list: 3

4. Step By Step Explanation

1. The Node class represents an individual node of the linked list. It contains data and a reference to the next node (initialized as None).

2. The LinkedList class defines the operations we can perform on the linked list. Its head attribute points to the first node of the linked list.

3. The append method allows us to add a node at the end of the list.

4. The display method lets us visualize the list, printing each element followed by an arrow, culminating in None.

5. The is_empty method returns a boolean indicating whether the list is empty or not.

6. The length method gives the number of nodes in the list.