A warm hello to all the readers!
In the last post, we talked about the origin of linked list data structure. There are variations in linked list as well. In this post, we will understand the first variation or type which is called Singly Linked List.
The singly linked list is actually the same as the basic concept of linked list data structure. The elements are stored in non continuous memory locations. Each element contains two values. One is the actual value of the element. Second is the pointer or memory address of the next element.
And a sample singly linked list is represented as:
| 50 | x5004 |
| 28 | x5008 |
| 30 | null |
Node1 is pointing to Node2 and Node2 is pointing to Node3. Node3 is the last node and does not point to any memory address. Therefore, pointer is null.
The singly linked list means that the list can be traversed in a single direction only. We can go from Node1 to Node2 and then Node3. We cannot travel back from Node3 to Node2 and so on.
What Are Singly Linked List Operations?
Let us now talk about different operations that can be performed on singly linked list.
- The item can be accessed
- A new item can be inserted in the beginning, end or anywhere in between the list
- Any item can be deleted
- Any item can be searched by traversing the list
What Is The Time Complexity Of Singly Linked List?
Now we know the different operations that can be performed on the singly linked list. We shall now see what is the time complexity of each operation.
- Accessing element – This takes O(n) time because each element has to be traversed to see memory address of next element
- Inserting element – This takes O(n) time since in worst case if inserting element in middle of the list, then this requires traversing the list.
- Deleting element – This again takes O(n) time since in worst case if inserting element in middle of the list, then this requires traversing the list.
- Searching element – This also takes O(n) time since it requires (n) unknown number of iterations over the elements of the list in order to search a particular value
