Data structures from scratch- Bot-up series #10[Linked Lists II]
We will look into the pros and cons of the linked list
Pros:
1)No need for continuous slots
2)We can use any random location
3)Any number of values can be linked through pointers
4)No need to mention the length of the list in advance(Dynamicity)
5)Insertion and deletion of elements in the middle is easy
Cons:
1)Each value takes one additional space for pointers(More space)
2)Accessing a particular value takes time because values are not indexed
3)Indexing gives us prediction(i.e where the next value is located) but linked lists are located randomly
4)This essentially means we will have to go through all the values till the particular value is found
5)For example, if the value is located on the 9th link, then we will have to go through 8 values to attain it
6)Time taken to search is proportional to no of values in the linked list at worst case(i.e if the desired element is located last)
In a nutshell,
Array gives us faster accessibility because of indexing — positioning and indexing are synchronous in array.
The linked list gives faster insertion and deletion because of pointers and dynamicity
This now time to understand the difference between Accessibility and Search(lookup)
By accessibility, I mean Random Access
This means If I know the position of an element, I can easily calculate the index in the array and access the corresponding value
This random access is available only in an array and not in a linked list
But searching for a value is different from accessing it because we do not know the position of the value
So for both arrays and linked lists, values must be sequentially checked until a match is found
On searching aspect, both arrays and linked list are on the same page
So we will have to build a data structure that has a faster lookup than arrays and linked list
This faster lookup is important in many real-world applications like Database, Web services, social networking etc
In the next post, we will build such a structure
