Describe the structure of a singly linked list. How does each node point to the next node in the list? What are the advantages and disadvantages of singly linked lists compared to other data structures?
Hello everyone welcome to new concept of the week….
Single linked list: A singly linked list is a linear data structure so here we will be having nodes, and which is linking with each other. So, in the structure of a single linked list every node will have two fields, one is data, and the other is the link to the next node that means address of the next node. The end of the structure is called as tail of linked list which will be set to null by default.
Structure of Single Linked list
- When we compare with other languages like ” C” and “java”, we have that dynamic memory allocation, and we have a concept of pointers, so every node has two pointers, one is data, and another one is a pointer variable.
- Whereas this implementation in python we do not have the concept of pointers so we must go with the object-oriented programming which means we must create a class for data and next (which is link address to next node).
Below is the example for single linked list structure:
Node Structure: A node in a linked list typically consists of two components Data and Next.
Data: It holds the actual value or data associated with the node.
Next Pointer: It stores the memory address (reference) of the next node in the sequence.
Head and Tail: The linked list is accessed through the head node, which points to the first node in the list. The last node in the list points to NULL or nullptr, indicating the end of the list. This node is known as the tail node.
Operations on Linked Lists
- Insertion: Adding a new node to a linked list involves adjusting the pointers of the existing nodes to maintain the proper sequence. Insertion can be performed at the beginning, end, or any position within the list. Below is the code for single linked and insertion operations.
Syntax of Insertion Operation at the beginning and end:
# Program to create nodes and insert operation at front, end, and desired location
# creating a class for data
class node:
def __init__(self,data):
self.data=data
self.next=None
# creating a class for link(address)
class SingleLinkedList:
def __init__(self):
self.head=None
# Insertion at the begining using linked list
def insert_begining(self,data):
nb=node(data)
nb.next=self.head
self.head=nb
# Insertion at the end using linked list
def insert_end(self,data):
ne=node(data)
temp=self.head
while temp.next:
temp=temp.next
temp.next=ne
# Insertion at the desired position using linked list
def insert_position(self,pos,data):
np=node(data)
temp=self.head
for i in range(pos-1):
temp=temp.next
np.data=data
np.next=temp.next
temp.next=np
# creating to display the node during output
def display(self):
if self.head is None:
print("Linked List is Empty")
else:
temp=self.head
while temp:
print(temp.data,"-->",end=" ")
temp=temp.next
L= SingleLinkedList()
n=node(10)
L.head=n
n1=node(20)
n.next=n1
n2=node(30)
n1.next=n2
n3=node(40)
n2.next=n3
n4=node(50)
n3.next=n4
# inserting new values at the begining
L.insert_begining(5)
# inserting new values at the end
L.insert_end(60)
L.insert_end(70)
# inserting new values at the desired position
L.insert_position(4,25)
L.display() Output:5 --> 10 --> 20 --> 30 --> 25 --> 40 --> 50 --> 60 --> 70 -->Deletion: Removing a node from a linked list requires adjusting the pointers of the surrounding nodes to bridge the gap left by the deleted node. Deletion can be performed at the beginning, end, or any position within the list. Below is the sample code for deletion of nodes.
Get Priya Karnasula’s stories in your inbox
Join Medium for free to get updates from this writer.
Syntax of Deletion Operation:
# creating a class for data
class node:
def __init__(self,data):
self.data=data
self.next=None
# creating a class for link(address)
class SingleLinkedList:
def __init__(self):
self.head=None
# creating to display the node during output
def display(self):
if self.head is None:
print("Linked List is Empty")
else:
temp=self.head
while temp:
print(temp.data,"-->",end=" ")
temp=temp.next
# Deletion at the begining
def delete_begining(self):
temp=self.head
self.head=temp.next
temp.next=None
# Deletion at the end
def delete_end(self):
prev=self.head
temp=self.head.next
while temp.next is not None:
temp=temp.next
prev=prev.next
prev.next=None
# Deetion at desired location
def delete_position(self,pos):
prev=self.head
temp=self.head.next
for i in range(1,pos-1):
temp=temp.next
prev=prev.next
prev.next=temp.next
L= SingleLinkedList()
n=node(10)
L.head=n
n1=node(20)
n.next=n1
n2=node(30)
n1.next=n2
n3=node(40)
n2.next=n3
n4=node(50)
n3.next=n4
# Deletion at the begining
L.delete_begining()
# Deletion at the end
L.delete_end()
# Deletion at the desired position
L.delete_position(3)
L.display()Output: 20 --> 30 -->Searching: Searching for a specific value in a linked list involves traversing the list from the head node until the value is found or the end of the list is reached.
Advantages of singly linked list compare to other data structures:
- No wastage of memory as we are using dynamic memory allocation.
- No need to use contiguous memory locations as we are providing the address of the link to connect the next node.
- Insertion and deletion becomes more simple.
- Linear data structures like stacks and queues can be implemented easily.
- can store any type of data in node. (ex: int, string, float)
Disadvantages of singly linked list compare to other data structures:
- It is not possible to access random elements as we must go in order.
- Only direct traversal is possible because link contains address of next node not the previous one.
- As index values are not accessed binary search algorithm is not possible.
- Reversing linked list is complex.
- Extra pointer is required to store the address of the next node.
— — — — — — — — — — — — — — — — Thank You — — — — — — — — — — — —
