Data Structures — Linked List & Doubly Linked List
AKA My Introduction to Nodes
This post is the second part of a multi-part series on Data Structures. To check out the previous post, click here.
As I had mentioned in an earlier post, Data Structures are a way of organizing data in an efficient manner. While each Data Structures may differ in complexity and function, they each provide a unique construct on how we access information. In this post, we will be reviewing the specifics of a Linked List and a Doubly-Linked List in order to understand their functionality and use cases, as well as how to implement them.
Linked List
A Linked List is a linear data structure made up of multiple node elements that are linked together using pointers. This allows the elements to be stored in different locations, allowing for a more optimal storage of information. Linked Lists can be dynamic in size, and have more optimal insertion and deletion than arrays. Each Link, or Node, has a value it stores, and a link to the next link called Next. In addition, each Linked List has a head and tail property to indicate the beginning and end of the Linked List.
Due to their rather simple nature, Linked Lists are an extremely popular data structure. However, due to their structure they do not allow for random access of information, so any search of the Linked List has the potential to be a linear time complexity. In addition, extra memory space is required for each pointer within the Linked List. Typically, a Linked List will have an addToTail method (constant time), a removeHead method (constant time), and a contains method (linear at worst). Now that we have a visual understanding of what a Linked List will look like, let’s start pseudocoding
// Create our Linked List class
// Linked List will have a head
// Linked List will have a tail// AddToTail method
// instantiate a value based on a node
// sets the head if it is null
// sets the next value if a tail exists
// sets the tail value// RemoveHead method
// checks the value of the head
// if the head has a value, store the value in a temp variable
// set the head value equal to the next value
// return the temp variable// Contains method
// compares the current val to the target value
// if there is no match, check the next value through recursion
// return whether a match has been found// Create our Node class
// Node will have a value
// Node will have a next
Since we know that each Linked List will be comprised of individual Nodes, we must create a Node class with the relevant properties first. This Node class will have a value, and a next property to correspond to the properties of each node. Once we have done this, we will be able to utilize the Node class to perform our specific Linked List operations and create our Linked List. We know that the Linked List will need a head and tail reference in order to create its one-directional structure. Now that we have our pseudocode clearly laid out, we’re ready to start coding.
class LinkedList extends Node {
constructor() {
super();
this.head = null;
this.tail = null;
}
}LinkedList.prototype.addToTail = (value) => {
const link = new Node(value);
// check if our head exists, if not, we will set the value
if (list.head === null) {
list.head = link;
}
// check to see if we already have a tail, if so, set the new next value
if (list.tail) {
list.tail.next = link;
}
// set the new tail value
list.tail = link;
}LinkedList.prototype.removeHead = () => {
// check if our head exists, if not, we will return null
if (list.head === null) {
return null;
}
// Set our temp variable to the existing head
const temp = list.head;
// set the new head value
list.head = list.head.next;
return temp;
}LinkedList.prototype.contains = (target) => {
// create a recursive function to iterate over each node
const search = (node) => {
if (node) {
if (node.value === target) {
return true;
} else {
return search(node.next);
}
} else {
return false;
}
};
// initiates recursive call at the start of the Linked List
return search(list.head);
}// Create our Node class
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
Since a Linked List is a compilation of Nodes, it is clear that the purposes of its methods are to create the connections from one Node to another, and set the head and tail properties to create the one-directional data flow. As such, we know that information only travels from the head to the tail in a Linked List. However, it is possible to modify a Linked List to account for its previous Node and allow for two-directional data transfers. These Linked Lists are called Doubly Linked Lists.
Doubly Linked List
As was mentioned earlier, a Doubly Linked List is a Linked List that has capacity to remember its previous node, thereby allowing information to travel from the head to the tail and vice versa. This is achieved by adding a previous value to each node that records the previous Node. Since there are more links to consider when adding and removing Nodes, these operations are potentially not as efficient as in a regular Linked List.
Now that we have a general idea of how a Doubly Linked List looks, we’ll add some pseudocode to our previous Linked List
// Create our Doubly Linked List class
// Linked List will have a head
// Linked List will have a tail// AddToTail method
// instantiate a value based on a node
// sets the head if it is null
// sets the next value if a tail exists
// sets the previous value based on previous tail value
// sets the tail value// RemoveHead method
// checks the value of the head
// if the head has a value, store the value in a temp variable
// set the head value equal to the next value
// set the new head.previous to null
// return the temp variable// Contains method
// compares the current val to the target value
// if there is no match, check the next value through recursion
// return whether a match has been found// Create our Node class
// Node will have a value
// Node will have a next
// Node will have a previous
Since we already have the basic construct of a Linked List, it is easy to see how we can potentially extend its functionality to make it a Doubly Linked List. In order to achieve this, we will need to add a previous key to our nodes in order to consider for each of the previous connections. As such, we must also modify the new previous values whenever a Node is added to the tail, a head is removed, or we delete a node. This will allow us to maintain the defining characteristics of a Doubly Linked List (two-way data relationships) while still keeping with the Linked List base.
class DoublyLinkedList extends Node {
constructor() {
super();
this.head = null;
this.tail = null;
}
}DoublyLinkedList.prototype.addToTail = (value) => {
const link = new Node(value);
if (list.head === null) {
this.head = link;
this.link.previous = null;
}
if (list.tail) {
this.tail.next = link;
link.previous = this.tail;
}
this.tail = link;
}DoublyLinkedList.prototype.removeHead = () => {
if (list.head === null) {
return null;
}
const temp = list.head;
list.head = list.head.next;
list.head.previous = null;
return temp;
}DoublyLinkedList.prototype.contains = (target) => {
const search = (node) => {
if (node) {
if (node.value === target) {
return true;
} else {
return search(node.next);
}
} else {
return false;
}
};
return search(list.head);
}// Create our Node class
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.previous = null;
}
}
There you have it, a Doubly Linked List. If you’re new to Data Structures, this may be difficult to grasp at first, but don’t worry — it gets easier with more practice.
Recap
- Linked Lists are comprised of nodes that have a value and next property
- Information within a Linked List is one-directional, so no Node knows about the previous Node.
- These Links are joined by referencing one another, allowing for constant time additions.
- Doubly Linked Lists allow users to reference previous information.
- These previous references must be modified when implementing the removeHead and addToTail methods.
This is Part II of a multi-part series on Data Structures. If you’re interested in continuing on with the series on Data Structures, check out this next post to see how to create and traverse Tree Structures.