The importance of learning different types of data structures can lead to a deeper understanding of how we not only represent data, but also how we organize and interact with it. One data structure that all developers should be familiar with is Linked Lists.
Linked Lists are common types of data structures that is used to represent a sequential group of elements. In other words, they are a just list of items. The key difference between a linked list and an array, would be the “location” or “address” of the list in memory. What in the world do you mean by “location” and “address”?! We’re talking about where our list is stored in our computer’s memory. Arrays are stored in fixed blocks of memory while linked lists elements are stored in any available block of memory and are connected via pointers. Take this list of numbers for example: 2, 4, 6, 8.
Array elements are all grouped together making it easier to index through the list to find a number at a specified location.
Linked List elements have a pointer that points to the next element in the list, meaning that each block holds 2 pieces of information 1) the value of the item and 2) the location of the next item in the chain.
Before we go into the advantages and disadvantages of linked lists compared to regular array lists, we’ll first need to see how a linked list works.
There are 2 common types of linked lists:
- Singly-Linked List
- Doubly-Linked List
Singly-Linked Lists
Singly-Linked Lists are made up of a collection of nodes where each node contains a value and a pointer. When a node element is created, the value is set and the pointer initially points to nothing or nullin JavaScript.
class Node {
constructor(value) {
this.value = value,
this.next = null
}
}class LinkedList {
constructor(head, tail) {
this.head = null,
this.tail = null
}
}
When interacting with a Linked List, we have the ability to append, prepend, insert into, find/search, and remove elements. For the purpose of this article, we will focus only on appending elements to the end, prepending elements to the start, and finding a certain element of a linked list.
class LinkedList {
constructor(head, tail) {
this.head = null,
this.tail = null
} find(value) {
let currentHead = this.head;
while (currentHead) {
if (currentHead.value === value) {
return currentHead;
}
currentHead = currentHead.next;
}
return null;
} append(value) {
if (!this.tail) {
this.head = this.tail = new Node(value);
} else {
const oldTail = this.tail;
const newNode = new Node(value);
this.tail = newNode;
oldTail.next = newNode;
}
} prepend(value) {
if (!this.head) {
this.head = this.tail = new Node(value);
} else {
const oldHead = this.head;
this.head = new Node(value);
this.head.next = oldHead;
}
}
}const linked1 = new LinkedList; // => Initialize a new linked list
linked1.append(123);
// => Creates the first node and sets head and tail to this node
These nodes then create a single direction link that chain each node together. In order to traverse through the list, there is a head pointer that is initialized to point at the first node in the chain when it is created. Lets create a few more nodes to see how it changes our diagram.
linked1.prepend(0); // => new node at the start of the list
linked1.append(456); // => new node at the end of the list
These commands prepend a node with a value of 0 and sets that node to be the head of the list, while the tail is set to the appended node with a value of 456. The last task that we cover is the ability to find a specified value.
linked1.find(123); // => Node {value: 123, next: [Node...]}
linked1.find(789); // => nullAs we begin to find the respective values in the list, we set a currentHead variable that points to the start of the linked list and begins to check if that current node’s value matches the value that we are searching for. If we don’t find the value, we then move the currentHead pointer to the next node and rinse and repeat until we either find the value or get to the end of the list.
Doubly-Linked List
Doubly-Linked Lists are essentially the same as the Singly-Linked Lists with 1 key difference. The doubly-linked list have a two-way relationship that allows the traversal both forward and backwards, whereas the single direction linked list flows downwards only. Try to convert the singly-linked list above to a doubly-linked list. The final product should look something like this.
Advantages & Disadvantages
All right, enough about how linked lists works. Let’s talk about why we would want to use a linked list over an array list. To do this comparison, we want to look at what the differences are.
As with most decisions in programming, the best answer is “it depends”. There are arguments for and against linked lists, but it really depends on your special scenario. If its a small list of items, it may be better to go with an array. If you’re worried about costly memory reallocation, maybe a linked list would be the better option. In any case, learning about how and why linked lists are important will help in other data structures such as trees, stacks, and hash tables.
Great Sources of information that helped inspire this article