Data Structures: Arrays and Linked Lists
Today, I am starting a series of blog posts outlining my studies of data structures and algorithms. I recently was selected for final interviews at Amazon Prime Video. I spend a two week period dedicated to learning data structures and algorithms. I decided it would be worth my time to solidify what I studied in preparation for the interviews by writing about it. The first topic I will go into are arrays and linked lists. Arrays and linked lists are both lists that have different characteristics and properties. I will also go into the implementation of linked lists in JavaScript.
Arrays
Arrays are a common implementation of a list and is usually a built in feature of most programming languages. Arrays are a collection of items with a specified order. The elements of an array are stored in a continuous block of memory. All elements of the array are of the same size in memory and we can assign each element an index denoting the elements location in memory. Lookup of an element is done in constant time, O(1), through the use of the associated index. Insertion and deletion of elements can be time consuming, O(N), on average as the elements in the array have to be relocated.
Linked Lists
Linked lists are different from arrays in several ways. Linked lists are a structure that has order, but does not have indices indicating location. Each element in a linked list stores a reference to the next element in the list. In a doubly linked list, elements store references to the previous element as well as the next element. In contrast, elements in arrays do not have a notion of the next element in the array. Elements in an array only know their location through an index. Insertion and deletion of elements in a linked list can be done in constant time, O(1), since the insertion or deletion only involves changing the references or pointers of neighboring elements. For an array, insertion or deletion involves iterating over multiple elements.
Implementing Linked Lists
We implement a linked list by defining a class for the linked list and for the nodes of the linked list. Linked lists are composed of nodes. Each node of a linked list has a value and a reference to the next node in the linked list (a reference to the previous node as well if the linked list is doubly linked). The linked list class defines the reference to the head node.
class LinkedList {
constructor() {
this.head = null;
}
}class ListNode {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
Appending and Prepending
We can write an append and a prepend method that operates on the linked list. The prepend method reassigns the head of the linked list. Thus, the prepend method runs in constant time, O(1), since it involves only reassigning the reference of the linked list. The prepend method is implemented as follows:
LinkedList.prototype.prepend = function(value) {
let newNode = new ListNode(value) if(!this.head) {
this.head = newNode
return this.head
} newNode.next = this.head;
this.head = newNode;
return this.head;
}
The above method creates a new node object. If the linked list does not have a head node, the new node is assigned as the head node. Otherwise, the new node points to the head node and the new node is assigned as the head node. Notice that the linked list is only defined by the head node. The characteristics of the linked list are then determined by the remaining nodes that make up the linked list.
The append method adds a value to the tail of the linked list. We create a pointer to the head that we iterate through the linked list to reach the tail. Once we reach the tail node, we assign the tail node’s pointer to the new node. The append method is implemented as follows and runs in linear time, O(N).
LinkedList.prototype.append = function(value) {
let newNode = new ListNode(value);
if(!this.head) {
this.head = newNode;
return this.head;
} let tail = this.head;
while (tail.next !== null) {
tail = tail.next;
}
tail.next = newNode; return this.head;
}
A doubly linked list is implemented as follows. For a doubly linked list, the tail node is referenced in addition to the head node.
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
}class DoublyLinkedNode {
constructor(value, next = null, prev = null) {
this.value = value;
this.next = next;
this.prev = prev;
}
}
How would we append a node to a doubly linked list? Let’s take a look. First, we need to check if the doubly linked list has a head node. If there is no head node, we assign the new node to be the head node as well as the tail node. If there is a head node, we assign the pointers for the tail node and the new node accordingly. Then, update the new node to be the new tail node.
DoublyLinkedList.prototype.append = function(value) {
let newNode = new DoublyLinkedNode(value); if(!this.head) {
this.head = newNode;
this.tail = this.head;
return this.head;
} this.tail.next = newNode;
this.tail.next.prev = this.tail;
this.tail = newNode;
}
For the prepend method, we similarly assign the pointers for the head node and the new node accordingly. Then, update the new node to be the new head node.
DoublyLinkedList.prototype.append = function(value) {
let newNode = new DoublyLinkedNode(value); if(!this.head) {
this.head = newNode;
this.tail = this.head;
return this.head;
} newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}}
Deleting Node from Head or Tail
Moving back to singly linked lists, we can write functions that delete the head node and the tail node. To delete the head node, we set the head node to be the next node. We can also return the value of the removed node. Since a linked list is defined by the head node, reassigning the head node reference removes the original head node from the linked list.
LinkedList.prototype.removeFirst = function() {
if(!this.head) {
return null;
} let node = this.head;
this.head = this.head.next;
return node.value;
}
To delete the tail node, we track two nodes the tail and the node previous to the tail. The pointers are started at the head and moved down the linked list. Once the tail pointer reaches the tail, the next reference for the node previous to the tail node is removed. This removes the tail node from the linked list since the linked list is constructed of these references between nodes. If the linked list is composed of one head node, we just remove the head node.
LinkedList.prototype.removeLast = function() {
if(!this.head) {
return null;
} if(!this.head.next) {
this.head = null;
return;
} let previous = this.head;
let tail = this.head.next; while(!this.head.next) {
previous = tail;
this.tail = this.tail.next;
}
previous.next = null;
return this.head;
}
Adding or Deleting Node from the Center of the Linked List
We can add or remove a node from a specified index. We can first define a function that gets this node at the specified index. Starting at the node, we can step through the linked list until the node at the specified index is located. We can also create a function that determines the size of the linked list.
LinkedList.prototype.getAt = function(index) {
let counter = 0;
let node = this.head;
while (node) {
if(counter === index) {
return node;
}
node = node.next;
counter++;
}
return null;
}LinkedList.prototype.size = function() {
let counter = 0;
let node = this.head;
while(node) {
node = node.next;
counter++;
}
return counter;
}
We can use the above helper functions to define an insert function given the value of the node and the index to be inserted at. If the index is 0, we prepend the value using the function defined above. Similarly if the index is greater than or equal to the size of the linked list, we append the value. If the list is empty, set the new node as the head node. Otherwise, we must set the surrounding node references accordingly. We save the node at the index before the insertion point. The pointer for the new node is set to the next node after the insertion point and the saved node’s pointer is set to the new inserted node.
LinkedList.prototype.insertAt(value, index) {
let newNode = new ListNode(value);
let previous = this.getAt(index - 1); if(!this.head) {
this.head = newNode;
return;
} if(index === 0) {
this.prepend(value);
return this.head;
} if(index <= this.size() - 1) {
newNode.next = previous.next;
previous.next = newNode;
} else {
this.append(value);
} return this.head;
}
The delete at index function is defined as follows. If the index is 0, we remove the head node of the linked list. Similarly, if the index is greater than or equal to the size of the linked list, we remove the tail node of the linked list. Otherwise, we must set the surrounding nodes accordingly. We save the node at the index before node to be removed. The pointer of this node is set to the node following the deleted node.
LinkedList.prototype.deleteAt(index) {
let previous = this.getAt(index - 1); if(!this.head) {
return;
} if(index === 0) {
this.head = this.head.next;
return;
} if(index <= this.size() - 1) {
previous.next = previous.next.next;
return this.head;
} else {
this.removeLast();
} return this.head;
}
We can create a function that prints out the linked list in the form of an array. The function uses the head pointer to loop through the list. The values of each node are then pushed into an array in order.
LinkedList.prototype.toArray = function() {
let output = [];
let node = this.head;
while (node) {
output.push(node.value);
node = node.next;
}
return output;
}Conclusion
In conclusion, a linked list is defined by its head node and constructed by nodes. Each node has a pointer to the next node. Linked lists are manipulated by redefining reference pointers between nodes. Insertion and deletion of elements involves the manipulation of pointers at constant time in contrast to an array where we need to reassign indices of each element resulting in linear time. Linked lists can be used to implement constructs such as stacks and queues and are the building blocks of larger data structures such as trees and graphs. I would like to acknowledge the data structures and algorithms course on Udacity which I referenced in writing this blog post.
