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. …
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
- is_empty(): Checks if the list is empty.
- append(data): Adds a new node with the given data to the end of the list.
- prepend(data): Adds a new node with the given data to the beginning of the list.
- delete(data): Removes the first occurrence of a node with the given data.
- search(data): Searches for a node with the given data and returns True if found.
- 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
- Reverse a Linked List: Can you implement a method to reverse the linked list in-place?
- Detect a Cycle: How would you detect if a linked list has a cycle?
- Find the Middle Node: Can you find the middle node of the linked list in one pass?
Exercise
- 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
. - Write a method
length(self)
that returns the number of nodes in the linked list. - 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!