When to actually use linked lists

  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.

This is because the memory for each array is allocated on compile, while linked lists get allocated on runtime. This is advantageous to link lists because they can be resized dynamically at runtime, while changing the size of an array involves creating a new array of longer length and using more memory, or you have to know the upper limit of the needed length beforehand, wasting memory space. This is less of an issue in JavaScript, Python, and Ruby where arrays can be dynamically resized using operations like .push() and .pop()

The memory allocation however is more efficient with arrays than link lists because the data at each index is stored directly in the allocation for each index, whereas link lists have to store a value, as well as a pointer to the next (or previous and next in a doubly linked list) node.

Arrays can also reference a particular element using an index, so to get the 5th element:

    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.

Linked lists (especially doubly linked lists) have a better space time complexity for adding and removing nodes at ends because inserting (or removing) the target element consists of simply changing the pointer(s) of the surrounding elements. To insert in the middle the complexity is still linear ( O(n) ) in a singly linked list because you must traverse to the index and update the pointer. The advantage here over an array comes from it's space complexity where you must traverse to an index, insert the value, and then find something to do with the remaining elements to re-position them. This is done a few different ways but requires more memory regardless.

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.

A linked list can be used as a stack by repeatedly adding and removing elements from the 'head' of the list.

  // 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());
  }

A doubly linked list can be used as a queue by adding to the 'head' of a linked list and removing from the 'tail'.

Linked lists can also be the buckets on hash tables to prevent intersection. (If something is already at that hash location, add it to the end of the list).

Other real world applications can include the back button on a browser, an undo button in photoshop, or the cycle of applications running on an operating system.

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.

References:

https://www.geeksforgeeks.org/linked-list-vs-array/

https://www.quora.com/In-which-languages-are-arrays-automatically-resizable-and-in-which-are-they-a-fixed-length