So I can remember being in class one day at Flatiron and one of the lessons during TIPS (a time spent to algorithms and data structures) was linked list. My mind was blown completely and I can confidently say I did not grasp or retain any information! LOL but no worries — let’s give it another try!
A linked list is a data structure that consists of a grouping of nodes in a sequence. If you are wondering what a node is, let’s break that down as well. A node represents the information contained in a single data structure. Nodes can be divided into two parts: A data part that stores the element and a next part (often called a pointer, because it is pointing to the next node in the series) that has a link or some address to the next node which forms a chain-like structure.
Every linked list has two references: the first and the last node. Within this list there is a HEAD, which you can imagine is the start. It is the name given to the first node. As well as the last node which does not have a name but can be identified because it points to Null. Below is a graph demonstrating this.
Why are Linked Lists useful?
Linked lists can be used anywhere and under any circumstance! Here are a few examples of where they get the most credit:
- Stacks & Queues: these two data structure follow the rules of LIFO (last in first out) and FIFO (first in first out) so both are focused mainly on the ends and not so much what the data is in the middle.
- You want an array but will insert more data than looking over/reading: Linked lists are great for storing data, especially if you know you will be inserting data more than actually extracting a single item out!
What are the differences between Linked Lists and Arrays?
First, arrays are a collection of elements where a Linked List is an ordered collection of elements. Both are used to store linear data of a similar type but the way the way they use memory is quite different. An array consumes contiguous memory locations allocated at compile time (when the array is declared). In strict languages this size of memory must be specified beforehand. But in dynamic languages (JavaScript) arrays can grow and shrink to meet the needs of the programmer. Linked lists memory is assigned as and when the data is added to it (at runtime). Although, accessing a specific node is much harder, this method of storing memory can be much faster when creating and removing nodes.
Secondly, Arrays also support random access meaning elements can be accessed using their index (arr[3] or arr[0]). Linked Lists support Sequential Access, meaning to access any node, we have to sequentially traverse the complete linked list, up to the element we want.
Lastly, as we’ve seen before each element in an array is independent and can be accessed using its index value. With a linked list, each node or elements points to the next (or previous or both).
I hope you enjoyed this quick overview of all the fun that involves Linked List!
