What is a Singly Linked List?
Singly Linked List is a type of Data Structure that contains a head, tail, and length property. It helps us to arrange the data in a list and access the data by traversing through all the nodes one by one within the list by accessing the next node.
Traversing a Singly Linked List.
A singly Linked list contains the head, tail, and length of the list.
The above diagram displays the structure of the Singly Linked List. All the boxes are nodes and they point towards the next node, so, if we want to access the node which has a value of 6 then we need to traverse through the head node which has a value of 4 then we will access the next node which has a value of 5 and then we will be able to access the next node which has the value of 6.
Difference between a List and an Array?
Now the next question arrives why do we need a List when we already have arrays?
Well, the answer to that is pretty simple, lists do not have indexes but arrays have, so, if we need to add or remove from a list we can perform the task without caring about the indexing and how much time complexity it will create. Inserting and Deletion in an array is quite expensive as compared to a list.
Secondly, the nodes within the list are connected with the next pointer but in arrays, there is no such connection, if we need to access an element inside an array we need to know the index of that particular element otherwise we need to loop over through the whole array, similarly, in a list, we need to loop over through the whole list.
The last difference is that we can randomly access elements inside an array with the help of an index but in a list, random access to elements is not possible we always have to traverse through the list to access an element.
Big O of Singly Linked Lists.
Everybody who is learning Data Structures probably has knowledge of Big O Notation. So, what is the Big O notation of a Singly Linked List?
The answer to that is, that it depends on the task you perform, for example.
Insertion: Inserting inside a list has O(1) time complexity.
Removal: Removing an element from a Singly Linked List has a time complexity of O(1) or O(n). It depends on the node location, if we want to remove the head or the tail of the list then the complexity is O(1) else if we want to remove the node whose location is in the middle of the list then it will take O(N) time complexity.
Searching: Searching a node within the list also has a time complexity of O(N).
Access: Accessing is similar to Searching so the time complexity is also the same for both of them which is O(N).
Blogs for further understanding
Creating a Singly Linked List in JavaScript: https://medium.com/@Satyam_Garhewal/creating-a-singly-linked-list-in-javascript-e5224a161146
If you liked 👍 my blog then you can buy me a coffee ☕️ @ https://www.buymeacoffee.com/satyamgarhewal
Small support will also be appreciated.
