Linked lists

Linked lists are a foundational data structure that all programmers should know about. For inexperienced developers, it can be hard to differentiate between arrays and linked lists since some programming languages and introductory textbooks and tutorials make them seem similar.

In this article, I will try my best to describe what differentiates a linked list from an array, and why you should care. Please note that a solid understanding of arrays and pointers is fundamental for understanding linked lists.

Like arrays, a linked list is a collection of related data. Unlike an array, a linked list does not contain its data in a contiguous space in memory. Instead, a linked list is a data structure consisting of a series of data nodes, where each node holds a piece of data and a pointer to the next node in the list.

In a singly linked list, each element stores the data and a pointer to the memory address of the next element in the list. In a doubly linked list, each node also has a pointer to the address of the previous element in the list. This causes the elements in a linked list to be scattered throughout memory. 

Since pointers to the next and previous nodes' locations in memory must also be stored on the node, a linked list requires more space in memory compared to an array.

The advantage of linked lists is that they do not require the developer to know the list's memory requirements in advance. Compared to arrays, it's also a lot more efficient to insert an element anywhere in the middle of a linked list, since you just have to swap out the pointers before and after the insert. The downside of a linked list is that it is much slower to look up a specific node in a linked list compared to an array.

Lookup speed is also a lot slower compared to an array.  To look up a specific index in a linked list, you have to traverse all the way from the start of the linked list to the index you are interested in. 

Deleting or inserting an element in the middle of a linked list is comparatively faster than doing the same operations on an array. Instead of having to move all the elements after the deleted element one step toward the start of an array after the deletion, you simply cut the deleted element out of the linked list and free the memory.

This makes removing the first element of the list, known as unshifting, significantly faster on a linked list compared to unshifting an array. This makes it ideal for queues, where the first element that gets added to a queue must be removed first (FIFO - First-in, First-out).

DSA (Data Structures and Algorithms) can only be learned by using them. I believe the most effective approach to learning DSA is first to understand the underlying theory and then solve challenges.

I encourage you first to solve these challenges by first using a brute force algorithm, then try to solve them with a time and space complexity of less than O(n²).

Here are the problems I solved when learning about linked lists using JavaScript:

• Creating a custom singly linked list class from scratch.
  • Append method
  • Prepend method
  • Print JSON to the terminal method.
  • Traverse to index method
  • Insert method
  • Remove method
• Create a doubly linked list class from scratch
   
• Singly linked list reversal
• Doubly linked list reversal