You are reading the article Singly Linked List In Data Structures updated in September 2023 on the website Lifecanntwaitvn.com. We hope that the information we have shared is helpful to you. If you find the content interesting and meaningful, please share it with your friends and continue to follow and support us for the latest updates. Suggested October 2023 Singly Linked List In Data Structures
What is a Singly Linked List?Singly Linked List is a linear and unidirectional data structure, where data is saved on the nodes, and each node is connected via a link to its next node. Each node contains a data field and a link to the next node. Singly Linked Lists can be traversed in only one direction, whereas Doubly Linked List can be traversed in both directions.
Here’s a node structure of a Singly Linked List:
Structure of a Node in a Linked List
Why use linked list over array?There’re several cases when it’s better to use the Linked List rather than the Array. Here’re some scenarios:
Unknown number of elements: When you don’t know how many elements you need to store during the program runtime, you can use the Linked List. Memory is allocated dynamically as you add elements to the linked lists.
Random access: In a scenario, where you don’t need to use the random access from the elements, you can use the Linked List.
Insertion in the middle: Insertion in the middle of an array is a complex task. Because you need to push other elements to the right. However, a linked List allows you to add an element to any position you want.
Operations of Singly Linked List
Singly Linked List is good for dynamically allocating memory. It provides all the basic operations of the linked list, i.e., insertion, deletion, searching, updating, merging two linked lists, traversing, etc.
Here we’ll discuss the following operation of the linked list:
Inserting at head
Inserting at tail
Inserting after a node
Inserting before a node
Delete the head node
Delete the tail node
Search and Delete a node
Traversing the Linked List
Here’s an example of a linked list with four nodes.
Example of a Singly Linked List
Insertion at the head of a Singly Linked ListThis is a simple operation. Generally, it’s known as pushing a singly linked list. You need to create a new node and place this at the head of the linked list.
To perform this operation, we need to follow two important conditions. They’re
If the list is empty, then the newly created node will be the head node, and the next node of the head will be ”NULL”.
If the list is not empty, the new node will be the head node, and the next will point to the previous head node.
Here’s the pseudo-code for inserting a node at the head of a linked list:
function insertAtHead( head, value ): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNodeInserting at the head
Insertion at the end of a Singly Linked ListInserting a node at the end of a linked list has some similarities with inserting in the head. All you need to do is, traverse to the end node or the tail node. Then point the “next” node of the end node to the newly created node. If the head node is null, the new node will be the head node.
Here’re the steps:
Step 1) Traverse until the “next” node of the current node becomes null.
Step 2) Create a new node with the specified value.
Step 3) Assign the new node as the next node of the tail node.
The pseudo-code for inserting a node at the tail of a singly list:
function insertAtEnd( head, value ): newNode = Node(value) if head is NULL: head = newNode return head while chúng tôi is not NULL: then head = head.next head.next = newNode newNode.next = NULLInserting at the tail
Insertion after a node in a Singly Linked ListInserting after a node has two parts: Search for the node and attach after the searched node. We need to traverse all the nodes. For each node, we need to match with the search element. If there’s a match, then we will add the new node after the searched node.
Here’re the steps:
Step 1) Traverse the next node until the value of the current node equals the search item.
Step 2) New node’s next pointer will be the current node’s next pointer.
Step 3) Current node’s next node will be the new node.
Here’s the pseudo-code for inserting a node after a node:
function insertAfter( head, value, searchItem ): newNode = Node(value) while head.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNodeInserting a node after a node in Singly Linked List
Insertion before a node in a Singly Linked ListThis function is much similar to the insertion after a node. We must create a new node and traverse the linked list until the current node matches the search node. After that, we will add the new node as the previous node of the current node.
Here’re the steps:
Step 1) Traverse until the next node’s value equals the search item.
Step 2) Create a new node and assign the node’s “next” with the next to the next node of the current node.
Step 3) Assign the new node as the next node of the current node.
Here’s the pseudo-code:
function insertBefore( head, value, searchItem ): newNode = Node(value) while head.next.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNodeInserting a node before a node in Singly Linked List
Delete the head of the singly linked listIn every function of the linked list, the head pointer is provided as the parameter. You need to delete the head node and make the next node of the head node as the new head of the linked list. We also need to free the memory of the deleted node. Otherwise, the memory will be marked as occupied when another program tries to access it.
Here’re the steps for deleting the head of the singly linked list:
Step 1) Assign the next node of the head node as the new head.
Step 2) Free the allocated memory by the previous head node.
Step 3) Return the new head node.
The pseudo-code for deleting the head node:
function deleteHead( head ): temp = head head = head.next free( temp ) return headDeleting the head of a linked list
Delete the tail of the singly linked listDeleting the tail node is more familiar with deleting the head node. The difference is that we need to traverse to the end of the linked list and delete it. In the singly linked list, the node with the next node as “NULL” is the tail node.
Here’re the steps for deleting the tail node of the linked list:
Step 1) Traverse before the tail node. Save the current node.
Step 2) Free the memory of the next node of the current node.
Step 3) Set the next node of the current node as NULL.
Here’s the pseudo-code for deleting the tail node:
function deleteTail( head ): while chúng tôi is not NULL: head = head.next free( chúng tôi ) head.next = NULLDeleting the tail of Singly Linked List
Search and delete a node from a singly linked listThis function has two tasks, search and delete. We need to search until the end of the singly linked lists. If we find any similar node, we will delete that one. After that, we need to merge or link the left and right nodes of the deleted node. Here’re the steps for doing this:
Step 1) Traverse until the end of the linked list. Check if the current node is equal to the search node or not.
Step 2) If any node matches, store the node pointer to the current node.
Step 3) The “next” of the previous node will be the next node of the current node.
Step 4) Delete and free the memory of the current node.
Pseudo-code for search and delete a node from a singly linked list:
function searchAndDelete( head, searchItem ): while chúng tôi is not NULL and head.next.value is not equals searchItem : head = head.next head.next = head.next.next delete(head.next)Search and delete a node from Singly Linked List
Traverse a singly linked listSingly linked list only has the functionality for traversing head to tail. There are no pointer points to the previous node; that’s why we can’t traverse the Singly Linked List in reverse order. We will traverse each node and print the current node’s value until we get null.
Here’re the steps:
Step 1) Traverse each node until we get null as the next node.
Step 2) Print the value of the current node.
Pseudo-code for traversing a singly linked list:
function traverse( head ): while chúng tôi is not NULL: print the value of the head head = head.next Example of Singly Linked List in C++using namespace std; struct Node{ int data; struct Node *next; }; void insertAtHead(Node* &head, int value){ Node* newNode = new Node(); if(head!=NULL){ } head = newNode; } void insertEnd(Node* &head, int value){ if(head==NULL){ insertAtHead(head,value); } Node* newNode = new Node(); Node *temp = head; } } void searchAndDelete(Node **headPtr, int searchItem){ Node *temp = new Node(); temp = *headPtr; free(temp); }else{ Node *currentNode = *headPtr; free(temp); }else{ } } } cout<<“Deleted Nodet”<<searchItem<<endl; return; } void insertAfter(Node * &headPtr, int searchItem, int value){ Node* newNode = new Node(); Node *head = headPtr; } cout<<“Inserted “<<value<<” after nodet”<<searchItem<<endl; } void insertBefore(Node * &headPtr, int searchItem, int value){ Node* newNode = new Node(); Node *head = headPtr; } cout<<“Inserted “<<value<<” before nodet”<<searchItem<<endl; } void traverse(Node *headPointer){ Node* tempNode = new Node(); tempNode = headPointer; cout<<“Traversal from head:t”; while(tempNode !=NULL){ } cout<<endl; } int main(){ Node *head = NULL; insertAtHead(head,5); insertAtHead(head,6); insertAtHead(head,7); insertEnd(head,9); traverse(head); searchAndDelete(&head,6); traverse(head); insertAfter(head,7,10); insertBefore(head,9,11); traverse(head); }
Output:
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Traversal from head: 7 → 6 → 5 → 9 Deleted Node 6 Traversal from head: 7 → 5 → 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversal from head: 7 → 10 → 5 → 11 → 9 Example of Singly Linked List in Python Program class Node: def __init__(self,data = None, next = None): chúng tôi = data chúng tôi = next class SinglyLinkedList: def __init__(self): chúng tôi = None def insertAtHead(self, value): newNode = Node(data=value) if chúng tôi is not None: chúng tôi = self.head chúng tôi = newNode print(f'Added {newNode.data} at the front.') return def insertAtEnd(self,value): if chúng tôi is None: self.insertAtHead(value) newNode = Node(value) temp = self.head while chúng tôi is not None: temp = temp.next chúng tôi = newNode print(f'Added {newNode.data} at the end.') def searchAndDelete(self,searchItem): temp = Node() if chúng tôi is searchItem: temp = self.head chúng tôi = self.head.next else: currentNode = self.head while chúng tôi is not None: if chúng tôi is searchItem: temp = currentNode.next chúng tôi = currentNode.next.next else: currentNode = currentNode.next print(f'Deleted nodet{searchItem}') return def insertAfter(self,searchItem,value): newNode = Node(data=value) temp = self.head while chúng tôi is not None and chúng tôi is not searchItem: temp = temp.next chúng tôi = temp.next chúng tôi = newNode print(f'Inserted {value} after nodet{searchItem}') return def insertbefore(self,searchItem,value): newNode = Node(data=value) temp = self.head while chúng tôi is not None and chúng tôi is not searchItem: temp = temp.next chúng tôi = temp.next chúng tôi = newNode print(f'Inserted {value} before nodet{searchItem}') return def traverse(self): temp = self.head print("Traversing from head:t",end="") while temp: print("{}t".format(temp.data),end="") temp = temp.next print() SinglyLinkedList = SinglyLinkedList() SinglyLinkedList.insertAtHead(5) SinglyLinkedList.insertAtHead(6) SinglyLinkedList.insertAtHead(7) SinglyLinkedList.insertAtEnd(9) SinglyLinkedList.traverse() SinglyLinkedList.searchAndDelete(6) SinglyLinkedList.traverse() SinglyLinkedList.insertAfter(7,10) SinglyLinkedList.insertbefore(9, 11) SinglyLinkedList.traverse()Output:
Added 5 at the front. Added 6 at the front. Added 7 at the front. Added 9 at the end. Traversing from head: 7 6 5 9 Deleted node 6 Traversing from head: 7 5 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversing from head: 7 10 5 11 9 Complexity of Singly Linked ListThere are two kinds of complexity: time complexity and space complexity. The worst and average case time complexity is the same for the Singly Linked List.
The time complexity for the best case:
Insertion in the head can be done in O(1). As we don’t need to traverse inside of the linked list.
Search and delete operation can be done in O(1) if the search element is present in the head node.
The time complexity for the average case:
Insertion inside a linked list will take O(n) if “n” elements are present in the Singly Linked List.
Search and delete can take O(n) too, as the search element can be present in the tail node. In that case, you should traverse the whole list.
Space Complexity of Singly Linked List
Singly Linked List dynamically allocates memory. If we want to store n elements, it will allocate n memory unit. So, the space complexity is O(n).
You're reading Singly Linked List In Data Structures
Update the detailed information about Singly Linked List In Data Structures on the Lifecanntwaitvn.com website. We hope the article's content will meet your needs, and we will regularly update the information to provide you with the fastest and most accurate information. Have a great day!