Insertion in Singly Linked List in Python
Insertion in Singly Linked List in Python
In the world of data structures and algorithms, linked lists are a fundamental concept. They provide a dynamic way of storing and organizing data, offering flexibility that arrays often lack. One common operation with linked lists is insertion, a process where we add a new element at a specific position within the list.
In this page, we will discuss about insertion in singly linked list in python, exploring various scenarios and techniques to master this essential skill.
Understanding Singly Linked Lists
A singly linked list is a linear data structure composed of nodes. Each node contains data and a reference (or link) to the next node in the sequence. The first node is known as the head, and the last node typically points to null, indicating the end of the list.
How to Perform Insertion in a Singly Linked List
- Understanding the Objective : When inserting an element at the end of a singly linked list, our primary goal is to add a new node containing the desired data to the last position, while ensuring that the previous node’s reference now points to this new node.
- Traversing the List : To accomplish this, we must first traverse the entire linked list. Starting from the head node, we follow the links until we reach the last node.
- Creating a New Node :
class Node:
def __init__(self, data):
self.data = data
self.next = None
new_node = Node(new_data)
Implementing Singly Linked Lists in Python:
Implementing Singly Linked Lists in Python allows for dynamic memory usage and efficient insertion or deletion at the beginning of the list. It’s a foundational data structure where each element points to the next, enabling sequential data storage and traversal.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
Output:
10 -> 20 -> 30 ->
Explanation:
- The Node class defines a single element with data and a pointer to the next node.
- The SinglyLinkedList class maintains the list. It starts empty (head = None).
- insert_at_end(data) creates a new node and inserts it at the end of the list. If the list is empty, the new node becomes the head. Otherwise, the method traverses to the end of the list and appends the node.
- The traversal loop prints all elements from head to the end of the list.
Time and Space Complexity:
| Time | Space |
|---|---|
O(n) — for insert_at_end() traversal | O(1) — constant extra space per operation |
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Common Operations on Singly Linked Lists
- Insertion at Beginning
- Insertion at Ending
Insertion at Beginning in Singly Linked List in Python
To insert a new node at the beginning of the list, you can use the following code:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
new_node = Node(data) # Create a new node
new_node.next = self.head # Point new node to current head
self.head = new_node # Update head to the new node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage
sll = SinglyLinkedList()
sll.insert_at_beginning(30)
sll.insert_at_beginning(20)
sll.insert_at_beginning(10)
sll.display()
Output:
10 -> 20 -> 30 -> None
Explanation:
- A new node is created with the given data using the Node class.
- The next pointer of this new node is set to the current head of the list.
- The head of the linked list is then updated to point to this new node.
- This process ensures that the new node is placed at the beginning of the list.
- Insertion at the beginning is done in constant time O(1), regardless of list size.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insertion at Beginning | O(1) | O(1) |
| Display Linked List | O(n) | O(1) |
Insertion at End in Singly Linked List in Python
To insert a new node at the end of the list, you can follow this approach:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node # If list is empty, make new node the head
else:
current = self.head
while current.next: # Traverse to the last node
current = current.next
current.next = new_node # Point last node to the new node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage
sll = SinglyLinkedList()
sll.insert_at_end(10)
sll.insert_at_end(20)
sll.insert_at_end(30)
sll.display()
Output:
10 -> 20 -> 30 -> None
Explanation:
- If the list is empty (head is None), the new node becomes the head.
- If not, we traverse the list using a loop until we find the last node.
- The next of the last node is updated to point to the new node.
- Insertion at the end takes O(n) time as it requires traversal to the last node.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insertion at End | O(n) | O(1) |
| Display Linked List | O(n) | O(1) |
"Singly Linked List vs. Arrays: Data Storage Comparison"
| Feature | Singly Linked List | Arrays |
|---|---|---|
| Data Structure | Consists of nodes where each node has a data element and a reference to the next node. | Contiguous memory block holding elements of the same data type. |
| Memory Allocation | Dynamic allocation of memory for each node as needed. | Static allocation of memory for a fixed size determined at initialization. |
| Size Flexibility | Can grow or shrink dynamically as nodes are added or removed. | Fixed size; requires resizing or creating a new array to change size. |
| Insertion/Deletion | Efficient for insertions/deletions at the beginning or middle with O(1) time complexity. | Inefficient for insertions/deletions in the middle, typically O(n) due to shifting elements. |
| Random Access | Inefficient for random access, typically O(n) as you must traverse from the head. | Efficient for random access with O(1) time complexity using an index. |
| Memory Overhead | Requires extra memory for storing references/pointers to the next node. | Minimal memory overhead, primarily for data storage. |
| Search Time Complexity | O(n) for searching as you must traverse the list linearly. | O(n) for unsorted arrays, O(log n) for sorted arrays, or O(1) with hash tables. |
| Use Cases | Suitable for scenarios with dynamic size requirements and frequent insertions/removals. | Suitable when size is known in advance and frequent random access is required. |
Advantages of Using Singly Linked Lists in Python
Dynamic Size:
Singly Linked Lists adjust their size at runtime, making them ideal when the number of elements frequently changes.Efficient Insertion and Deletion:
Adding or removing elements at the beginning is done in constant time O(1). Middle operations are also efficient if the position is known.Low Memory Overhead:
Each node stores only one reference (to the next node), consuming less memory than arrays or doubly linked lists.Dynamic Memory Allocation:
Nodes are allocated individually, reducing memory waste especially useful in systems with limited resources.
Conclusion
In this page, we’ve explored the intricacies of insertion in singly linked lists in Python. Understanding for working with this essential data structure, whether it’s for programming projects, interviews, or furthering your Python skills.
FAQs
There are three common ways: insertion at the beginning, at the end, and at a specific position (middle). Each method requires handling pointers differently to maintain the list’s structure.
To insert at the beginning, create a new node and point its next to the current head. Then, update the head to this new node—this operation takes constant time, O(1).
Insertion at the end takes O(n) time, as you must traverse the entire list to reach the last node unless you maintain a tail pointer.
To insert at a specific position, first traverse to the node before the target position. Then, link the new node’s next to the next node and adjust the previous node’s next pointer to the new node.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
