We've all learned in school or in our bootcamps about different complex data structures. Linked lists, hash maps, binary trees and search trees, stacks, queues, monotonic queues, etc... We've all also learned about how to write each one, how to traverse nodes, add nodes, and delete nodes. But what good is knowing all this stuff if we don't actually know when to use these data structures..
Linked Lists
As a brief recap, let's recall what linked lists are. Linked lists are a series of "nodes" containing a value as well as a pointer to the next node in the series. In a linked list you have access to the "head" of the list and all subsequent nodes are found by traversing through the list one by one. A doubly linked list has the same properties except a reference to the "tail" is kept as well and nodes also have a reference to the previous node, and the list can be traversed in reverse. Linked lists are usually compared to arrays as a similar data structure and although arrays are "primitive" data structures, they share similarities with linked lists.
Similarities
They both, for example, require traversal to access all elements in the structure and they both can be used to store linear data of similar types.
Differences
To really notice the differences you need to be programming in an older, compiled language such as C++, Java, or C# where arrays are of fixed length.
String[] array = new String[10]; //initializes new array of strings with length 10
String fifth = array[4]; //access the fifth element in the array (constant time)
and so on, while linked lists require access to the head, and then a loop to traverse the elements:
LinkedList<String> linkList = new LinkedList<String>();
//initializes a new linkList with type string. (no length specified)
linkList.search(4);
//then inside the linkList class:
public <T> search(int input){
head = current;
int counter = 1;
while(current.next != null){
if(counter == input){
return current.value
}
else{
counter++;
current = current.next;
}
Here we are looking for the 4th element of linkList, so we have to iterate through the first three values to get the fourth. Since space time complexity is worst case scenario, the lookup of a value in a linked list is O(n) because it is dependent on the length of the linked list as well as the index you are searching for. An array lookup on the other hand is a constant time-complexity ( O(1) ) because it is a direct lookup to the memory location of an element at a specific index.
Use Cases
So looking at the key differences between arrays and linked lists we can see the advantages and disadvantages of each and start to draw conclusions about when to use each. Linked lists utilize their key characteristic, to keep things quick and ordered, to really shine. Real-world applications most commonly include use in other complex data structures. Hash tables, graphs, stacks, queues, and dequeues all utilize linked lists internally.
// create stack linked list
StackUsingLinkedlist stack = new StackUsingLinkedlist();
// insert Stack value at head of linked list
stack.push(task1);
stack.push(task2);
stack.push(task3);
stack.push(task4);
while(!stack.isEmpty()){
//execute the task at the top of the stack (head of linked list)
execute(stack.pop());
}
Conclusion
There is a time and a place to use linked lists and most commonly it's when you want quickly add and remove elements from a container. Usually this occurs in stacks and queues with lower space time complexity over arrays or when you want to keep ordered data with more flexibility than arrays.
Stay tuned next week for part 2 of practical applications: When to actually use stacks.
Top comments (0)