Introduction to Singly Linked List
Singly Linked List is a variant of Linked List which allows only forward traversal of linked lists. This is a simple form, yet it is effective for several problems such as Big Integer calculations.
A singly linked list is made up of nodes where each node has two parts:
- The first part contains the actual data of the node
- The second part contains a link that points to the next node of the list that is the address of the next node.
The beginning of the node marked by a special pointer named START. The pointer points to the fist node of the list but the link part of the last node has no next node to point to.
The main difference from an array is:
- Elements are not stored in contiguous memory locations.
- Size of Linked List need not be known in advance. It can increase at runtime depending on number of elements dynamically without any overhead.
In Singly Linked List, only the pointer to the first node is stored. The other nodes are accessed one by one.
To get the address of ith node, we need to traverse all nodes before it because the address of ith node is stored with i-1th node and so on.
Why is linked list insertion o1?
It is said that the complexity of the LinkedList remove and the add operation is of O[1] . and in case of ArrayList it is of O[n] . so the complexity should be of order O[n] where Worst performence will be at the tail node and best performence will be at the head node.
What is the time complexity for deleting a linked list?
The time complexity for removal is only O[1] for a doubly-linked list if you already have a reference to the node you want to remove. Removal for a singly-linked list is only O[1] if you already have references to the node you want to remove and the one before.
In which linked list does insert operation at end takes O 1 time?
According to the Wikipedia article on linked lists, inserting in the middle of a linked list is considered O[1].
Singly Linked List vs Doubly Linked List
Before looking at the differences between the singly linked list and doubly linked list, we first understand what is singly linked list and doubly linked list separately.
Insert N elements in a Linked List one after other at middle position
Given an array of N elements. The task is to insert the given elements at the middle position in the linked list one after another. Each insert operation should take O[1] time complexity.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: 1 -> 3 -> 5 -> 4 -> 2 -> NULL
1 -> NULL
1 -> 2 -> NULL
1 -> 3 -> 2 -> NULL
1 -> 3 -> 4 -> 2 -> NULL
1 -> 3 -> 5 -> 4 -> 2 -> NULL
Input: arr[] = {5, 4, 1, 2}
Output: 5 -> 1 -> 2 -> 4 -> NULL
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach: There are two cases:
- Number of elements present in the list are less than 2.
- Number of elements present in the list are more than 2.
- The number of elements already present are even say N then the new element is inserted in the middle position that is [N / 2] + 1.
- The number of elements already present are odd then the new element is inserted next to the current middle element that is [N / 2] + 2.
We take one additional pointer ‘middle’ which stores the address of current middle element and a counter which counts the total number of elements.
If the elements already present in the linked list are less than 2 then middle will always point to the first position and we insert the new node after the current middle.
If the elements already present in the linked list are more than 2 then we insert the new node next to the current middle and increment the counter.
If there are an odd number of elements after insertion then the middle points to the newly inserted node else there is no change in the middle pointer.
Below is the implementation of the above approach:
C++
|
// C++ implementation of the approach #include using namespace std; // Node structure struct Node { int value; struct Node* next; }; // Class to represent a node // of the linked list class LinkedList { private: struct Node *head, *mid; int count; public: LinkedList[]; void insertAtMiddle[int]; void show[]; }; LinkedList::LinkedList[] { head = NULL; mid = NULL; count = 0; } // Function to insert a node in // the middle of the linked list void LinkedList::insertAtMiddle[int n] { struct Node* temp = new struct Node[]; struct Node* temp1; temp->next = NULL; temp->value = n; // If the number of elements // already present are less than 2 if [count < 2] { if [head == NULL] { head = temp; } else { temp1 = head; temp1->next = temp; } count++; // mid points to first element mid = head; } // If the number of elements already present // are greater than 2 else { temp->next = mid->next; mid->next = temp; count++; // If number of elements after insertion // are odd if [count % 2 != 0] { // mid points to the newly // inserted node mid = mid->next; } } } // Function to print the nodes // of the linked list void LinkedList::show[] { struct Node* temp; temp = head; // Initializing temp to head // Iterating and printing till // The end of linked list // That is, till temp is null while [temp != NULL] { cout value next; } cout 3 -> 5 -> 4 -> 2 -> NULL Time Complexity : O[N] Article Tags : Data Structures Linked List Mathematical Practice Tags : Data Structures Linked List Mathematical Read Full Article Video liên quanChủ Đề |