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
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
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:
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
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 LinkedList:
# ... (previous code)
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
"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 can dynamically adjust their size, allowing for efficient memory allocation as elements are added or removed. This flexibility makes them suitable for situations where the size of the data structure may change frequently.
- Efficient Insertion and Deletion: Inserting or deleting an element at the beginning of a Singly Linked List is a constant-time operation (O(1)), making it efficient for scenarios that require frequent data updates. Other operations, such as insertion and deletion in the middle, are also relatively efficient when the position of the element is known.
- Low Memory Overhead: Singly Linked Lists have lower memory overhead compared to some other data structures like arrays or doubly linked lists. Each element only needs to store a reference to the next element, which saves memory.
- Dynamic Memory Allocation: Singly Linked Lists allocate memory for each element individually, reducing the risk of memory wastage. This feature is particularly valuable in environments with limited memory 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.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
What is a singly linked list?
A singly linked list is a linear data structure composed of nodes, where each node contains data and a reference to the next node.
Question 2.
How do I insert an element at the beginning of a singly linked list?
To insert an element at the beginning, create a new node, make its next reference point to the current head, and update the head to the new node.
Question 3.
How do I insert an element at a specific position in a singly linked list?
To insert an element at a specific position, create a new node, traverse the list to the desired position, and update the references accordingly.
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
