Singly Linked Lists - Implementation and Basic Operations #

Welcome to Day 8 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deeper into singly linked lists, implementing a more comprehensive version and exploring various operations.

Singly Linked List Structure #

A singly linked list consists of nodes where each node contains data and a pointer to the next node. The last node points to None, indicating the end of the list.

1class Node:
2    def __init__(self, data):
3        self.data = data
4        self.next = None

Implementing a Singly Linked List #

Let’s implement a singly linked list with several basic operations:

 1class SinglyLinkedList:
 2    def __init__(self):
 3        self.head = None
 4
 5    def is_empty(self):
 6        return self.head is None
 7
 8    def append(self, data):
 9        new_node = Node(data)
10        if self.is_empty():
11            self.head = new_node
12        else:
13            current = self.head
14            while current.next:
15                current = current.next
16            current.next = new_node
17
18    def prepend(self, data):
19        new_node = Node(data)
20        new_node.next = self.head
21        self.head = new_node
22
23    def delete(self, data):
24        if self.is_empty():
25            return
26
27        if self.head.data == data:
28            self.head = self.head.next
29            return
30
31        current = self.head
32        while current.next and current.next.data != data:
33            current = current.next
34
35        if current.next:
36            current.next = current.next.next
37
38    def search(self, data):
39        current = self.head
40        while current:
41            if current.data == data:
42                return True
43            current = current.next
44        return False
45
46    def display(self):
47        elements = []
48        current = self.head
49        while current:
50            elements.append(str(current.data))
51            current = current.next
52        print(" -> ".join(elements))

Basic Operations Explained #

1. is_empty(): Checks if the list is empty.
2. append(data): Adds a new node with the given data to the end of the list.
3. prepend(data): Adds a new node with the given data to the beginning of the list.
4. delete(data): Removes the first occurrence of a node with the given data.
5. search(data): Searches for a node with the given data and returns True if found.
6. display(): Prints all elements in the list.

Time Complexity Analysis #

• Append: O(n) - We need to traverse to the end of the list.
• Prepend: O(1) - We simply add to the head.
• Delete: O(n) - In the worst case, we need to traverse the entire list.
• Search: O(n) - We may need to traverse the entire list to find an element.

Example Usage #

Let’s see how to use our SinglyLinkedList class:

 1# Create a new linked list
 2my_list = SinglyLinkedList()
 3
 4# Append elements
 5my_list.append(1)
 6my_list.append(2)
 7my_list.append(3)
 8my_list.display()  # Output: 1 -> 2 -> 3
 9
10# Prepend an element
11my_list.prepend(0)
12my_list.display()  # Output: 0 -> 1 -> 2 -> 3
13
14# Search for elements
15print(my_list.search(2))  # Output: True
16print(my_list.search(4))  # Output: False
17
18# Delete an element
19my_list.delete(2)
20my_list.display()  # Output: 0 -> 1 -> 3

Common Interview Questions #

1. Reverse a Linked List: Can you implement a method to reverse the linked list in-place?
2. Detect a Cycle: How would you detect if a linked list has a cycle?
3. Find the Middle Node: Can you find the middle node of the linked list in one pass?

Exercise #

1. Implement a method insert_after(self, target_data, new_data) that inserts a new node with new_data after the first occurrence of a node with target_data.
2. Write a method length(self) that returns the number of nodes in the linked list.
3. Implement a method remove_duplicates(self) that removes all duplicate nodes from the linked list.

Summary #

Today, we’ve implemented a more comprehensive singly linked list and explored its basic operations. Understanding these operations and their time complexities is crucial for using linked lists effectively in various algorithms.

Tomorrow, we’ll dive into doubly linked lists and compare them with singly linked lists. We’ll also explore some more advanced linked list problems. Stay tuned!