How to understand the Linked Lists Data structure? Explanations of HackerRank exercises. Theoretical part
I started to learn a python programming language and the best way to learn some new language is a practice of course. I try to learn algorithms and data structures step by step on HackerRank. The goal of this post is a strong understanding of Linked List data structure and explanations of common Linked list exercises because the theory is nothing without practice.
Linked List is a linear data structure, in which the elements are not stored at contiguous memory locations. All elements in the Linked List are linked using the reference on each other within a variable.
There is doesn't matter which programming language to use because many of them can have the realization of Linked List. I will use the python realization.
So the simple Linked List should look like below:
Classic realization of Linked List Node should have the next variable. The next variable will have reference to the next item of Linked List.
Main Conclusions About Linked List
Linked List is a simple chain of structures
Each element of Linked List is a Node
The node only has a reference to the next Node (or and to the previous) and so on. (We are only discussing simple Linked List)
Differences between Linked List and most used data structure - Array
The array is an index bases data structure where each element associated with an index. Linked List Nodes only have references to the previous or next nodes and there is no way to find the 2nd or 4th node of the linked list without searching it throw all Linked List.
Size of the array specified during declaration. Size of Linked list no need to specify. It will grow and shrinks during execution.
The array has consecutively order of elements. Linked List has a random order of elements (nodes)
Array's item is easy to access with his index. Linked List needs to be traverse from the head to the search element. Conclusion: Array is better than Linked List because with the index you can instantly access any element of the array.
Insertion and deletion of elements are better in the Linked List. Because it doesn't matter the physical order in memory of all nodes. The array has a weakness here. Sometimes array needs to be shifted in memory for insertion or deletion. Conclusion: Array is worse than Linked List in insertion and deletion operations.
When you need to search elements in Array you can use not only linear search. If the array is ordered you can also use binary search which has a huge time of the search. You can't use binary search in Linked list and it is a huge disadvantage of Linked List if you need to search elements through the List. Conclusion: Ordered array can use binary and linear search. Linked List can use only linear.
For understanding Linked List it is a good idea to do a few exercises with them. It will give us a more clear vision of this data structure. Check my explanations about Linked List exercises from the HackerRank bellow.