Singly Linked List
A singly linked list is a linear data structure in which the elements are not stored in contiguous memory locations and each element is connected only to its next element using a pointer.
The elements in a linked list are linked using pointers to the next node as shown in the below image:
Singly Linked List
Operations on Singly Linked List:
- Insertion at the beginning of the Linked List: To insert a node at the beginning of the Linked List, we change the next pointer of the new node to the current head and make the new node as the current head. Time Complexity: O(1)
- Insertion at the end or after a given node: To insert a node after a given node, we need to update the next pointer of the new node to the next pointer of the given node and update the next pointer of the given node to the new node. Time Complexity: O(N) as in the worst case we may traverse through all the nodes of the linked list.
- Searching an element: We can search a node by traversing through the linked list and comparing the nodes one by one. Time Complexity: O(N)
- Find length of the Linked List: We can find the length of the linked list by traversing through the linked list and maintaining the count of nodes. Time Complexity: O(N)
- Reverse a Linked List: We can reverse a linked list using three pointers curr, prev, and next to keep track of nodes to update reverse links. Time Complexity: O(N)
- Deletion at the beginning of the Linked List: To delete a node from the beginning of the Linked List, we can change the head to the next of the current head and delete the previous head. Time Complexity: O(1)
- Deletion at the end or after a given node: To delete a node after a given node, we need to update the next pointer of the given node to point to the node which is present after the node to be deleted. Time Complexity: O(N) as in the worst case we may traverse through all the nodes of the linked list.
Linked List Notes for GATE Exam [2024]
The “Linked List Notes for GATE Exam” is a comprehensive resource designed to aid students in preparing for the Graduate Aptitude Test in Engineering (GATE). Focused specifically on the topic of linked lists, a fundamental data structure in computer science, these notes offer a detailed and structured approach to mastering this subject within the context of the GATE examination.
Table of Content
- What is Linked List?
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Applications of Linked List
- Advantages of Linked Lists
- Disadvantages of Linked Lists
- Previous Year GATE Questions on Linked List: