loading...
Cover image for Learn Data Structure and Algorithm in JavaScript | Part 13

Learn Data Structure and Algorithm in JavaScript | Part 13

edisonnpebojot profile image Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป) Updated on ใƒป30 min read


Prerequisite (โœ‹๐Ÿ˜)

If you're reading this article right now, please considered to read our Part 01: Big-O Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers to Part 12: Stacks and Queues

Part Table of Contents Description
01 Big-O Notation By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed).
02 JavaScript Unique Parts Big-O is important for analyzing and comparing the efficiencies of algorithms. The analysis of Big-O starts by looking at the code, and, applying the rules, applying the rules is because to simplify the Big-O notation linear or quadratic rule is not enough.
03 JavaScript Numbers This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation.
04 JavaScript Strings This part 4 will focus on strings, JavaScript String object, and the String objectโ€™s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption.
05 JavaScript Arrays As a JavaScript developer, you will use the array often; it is the most commonly used data structure. Arrays in JavaScript come with a lot of built-in methods. By the end of this part, you will understand arrays and choose the right method
06 JavaScript Object This part will focus on what JavaScript objects are, how they are declared, and how their properties can be changed. In addition, this part will cover how JavaScript classes are implemented using prototypal inheritance. Also this part will be short.
07 JavaScript Memory Management A variable takes up some memory. In C, the programmer allocate and deallocate memory manually. In contrast, modern JavaScript engines have garbage collectors that delete unused variables. However, there are pitfalls(unexpected) that developers can fall into(โ—) This part will show these unexpected and present techniques to help the garbage collector minimize the memory problems.
08 Recursion This part 8 introduces the concept of recursion and recursive algorithms(Remember they are different, we will discuss them later(๐Ÿ˜‰)). We will also discuss the definition of recursion and fundamental rules for recursive algorithms.
09 Sets This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (๐Ÿ’ก).
10 Searching and Sorting This part 10 focuses on searching and sorting for arrays. By the end of this part 10, you will understand how to use sorting and searching algorithms for arrays. Also, this article is a bit complicated for beginners, so as much as possible the visual aids is your friend (๐Ÿ‘€). (๐Ÿ˜ƒ)
11 Hash Tables A hash table is a fixed-sized data structure in which the size is defined at the start. This part 11 explains how hash tables work, and the method of generating a unique key. By the end of this part 11, you will understand various hashing techniques and know how to implement a hash table. (๐Ÿ˜ƒ)
12 Stacks and Queues This part 12 covers stacks and queues(pronounce as kyooz (๐Ÿ”ˆ)) not (kwewe) okay? hehehe (๐Ÿ˜…); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (๐Ÿ˜ƒ) Let's go! (๐Ÿ”ฅ๐Ÿ”ฅ๐Ÿ”ฅ)
13 Linked Lists A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (๐Ÿ˜ฎ) There are two types of linked lists: singly (โžก๏ธ) and doubly (โ†”๏ธ). Letโ€™s examine the singly linked list first.(๐Ÿ˜ƒ) Let's go! (๐Ÿ”ฅ๐Ÿ”ฅ๐Ÿ”ฅ)
14 Caching Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database keeps data cached to avoid re-reading the hard drive, and a web browser caches web images to avoid re-downloading. In this part 14, two caching techniques will discussed: LFU and LRU caching.
15 Trees A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (๐Ÿ˜ƒ)
16 Heaps A heap is an important data structure that returns the highest or lowest element in O(1) time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
17 Graphs In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (๐Ÿ‘)
18 Advance Strings Part 18 will cover more complex string algorithms than covered in the previous section. Now that you have heard of certain other data models or structures, they should be easier to comprehend. Specifically, Part 18 will focus on string searching algorithms. (๐Ÿ˜‰)

Part 13: Linked Lists (๐Ÿ˜ฑ ๐Ÿ”ฅ โžก๏ธ)

Alt Text

A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (๐Ÿ˜ฎ) There are two types of linked lists: singly (โžก๏ธ) and doubly (โ†”๏ธ). Letโ€™s examine the singly linked list first.(๐Ÿ˜ƒ) Let's go! (๐Ÿ”ฅ๐Ÿ”ฅ๐Ÿ”ฅ)

Singly Linked Lists (โžก๏ธโžก๏ธ)

Alt text

The Singly Linked List is data structure where each node has reference to the next node. Let's look to our sample below:
Alt Text

Figure 13-1. Singly linked list

A node in a singly linked list has the following properties: data and next. data is the value and next is a pointer to another. Let's look to our code below to start to write our Singly Linked Lists:

Example:

// Singly Linked List Node
function SinglyLinkedListNode(data) {
    this.data = data;
    this.next = null;
}

The following code below is the base for the singly linked list. That is, the code block that check whether the singly linked list is empty:

Example:

// Singly Linked List Node
function SinglyLinkedListNode(data) {
    this.data = data;
    this.next = null;
}


// Singly Linked List
function SinglyLinkedList() {
    this.head = null;
    this.size = 0;
}

// Base
SinglyLinkedList.prototype.isEmpty = function () {
    return this.size == 0;
}

Note (๐Ÿ“):The start of the linked list is the head. This property defaults to null before inserting any element.

Insertion (โžก๏ธโœ…โžก๏ธ)

The following code block below shows how to insert into a singly linked list. If the head is empty, the head is set to the new node (or must be added an element). Or if the head is not empty, the old heap (collection or quantity) is saved in temp, and the new head becomes the newly added node. Finally, the new headโ€™s next points to the temp (the old temp).

Note (๐Ÿ“): If you are confuse, you can look at the code and study them

Example:

// Singly Linked List Node
function SinglyLinkedListNode(data) {
    this.data = data;
    this.next = null;
}


// Singly Linked List
function SinglyLinkedList() {
    this.head = null;
    this.size = 0;
}

// Base: Empty
SinglyLinkedList.prototype.isEmpty = function () {
    return this.size == 0;
}

// Insert
SinglyLinkedList.prototype.insert = function (value) {
    if (this.head === null) {
        this.head = new SinglyLinkedListNode(value);
    } else {
        var temp = this.head;
        this.head = new SinglyLinkedListNode(value);
        this.head.next = temp;
    }
    this.size++;
}

// Log
SinglyLinkedList.prototype.log = function () {
    var head = this.head.data;
    var next1 = this.head.next.data;
    var next2 = this.head.next.next.data;
    var next3 = this.head.next.next.next;
    return {
        Tree: this.head,
        Result: head + " -> " + next1 + " -> " + next2 + " -> " + next3
    };
}

// Instance(example) of the SinglyLinkedList class
var sll = new SinglyLinkedList();

// Add
sll.insert(1); // 1 -> null
sll.insert(2); // 2 -> 1 -> null
sll.insert(3); // 3 -> 2 -> 1 -> null

// Result
sll.log(); // Prints "3 -> 2 -> 1 -> null"

Execution:

// Singly Linked List Node function SinglyLinkedListNode(data) { this.data = data; this.next = null; } // Singly Linked List function SinglyLinkedList() { this.head = null; this.size = 0; } // Base: Empty SinglyLinkedList.prototype.isEmpty = function () { return this.size == 0; } // Insert SinglyLinkedList.prototype.insert = function (value) { if (this.head === null) { this.head = new SinglyLinkedListNode(value); } else { var temp = this.head; this.head = new SinglyLinkedListNode(value); this.head.next = temp; } this.size++; } // Log SinglyLinkedList.prototype.log = function () { var head = this.head.data; var next1 = this.head.next.data; var next2 = this.head.next.next.data; var next3 = this.head.next.next.next; return { Tree: this.head, Result: head + " -> " + next1 + " -> " + next2 + " -> " + next3 }; } // Instance(example) of the SinglyLinkedList class var sll = new SinglyLinkedList(); // Add sll.insert(1); // 1 -> null sll.insert(2); // 2 -> 1 -> null sll.insert(3); // 3 -> 2 -> 1 -> null // Result sll.log(); // Prints "3 -> 2 -> 1 -> null"

Time Complexity: O(1)O(1)

Deletion By Value (โžก๏ธโžก๏ธโŒ)

The deletion of node in a singly linked list is by removing the reference(the link or the path) of that node. Let's look below how that it works as shown in Figure 13-2:

Alt Text

Figure 13-2. Interior node removal from a singly linked list

If the node is at the end of the linked list, then the second-to-last element can dereference the node by setting its next to null. Let's look at some example code below:

Example:

// Singly Linked List Node
function SinglyLinkedListNode(data) {
    this.data = data;
    this.next = null;
}


// Singly Linked List
function SinglyLinkedList() {
    this.head = null;
    this.size = 0;
}

// Base: Empty
SinglyLinkedList.prototype.isEmpty = function () {
    return this.size == 0;
}

// Insert
SinglyLinkedList.prototype.insert = function (value) {
    if (this.head === null) {
        this.head = new SinglyLinkedListNode(value);
    } else {
        var temp = this.head;
        this.head = new SinglyLinkedListNode(value);
        this.head.next = temp;
    }
    this.size++;
}

// Remove
SinglyLinkedList.prototype.remove = function (value) {
    var currentHead = this.head; // this.head is equal to 3 -> 2 -> 1 -> null
    // currentHead.data is equal to "3"
    if (currentHead.data == value) {
        // x = means deleted reference as an example
        // Remove the reference: 3 x 2 -> 1 -> null
        this.head = currentHead.next;
        // Reduce the size by "one"
        this.size--;
    } else {
        var prev = currentHead;  // prev is equal to 3 -> 2 -> 1 -> null
        // currentHead.next is equal to 2 -> 1 -> null
        while (currentHead.next) {
            // currentHead.data is equal to "3"            
            if (currentHead.data == value) {
                // prev.next is equal to 2 -> 1 -> null
                // currentHead.next is equal to 2 -> 1 -> null
                prev.next = currentHead.next;
                // prev is equal to 3 -> 2 -> 1 -> null
                prev = currentHead;
                // x = means deleted reference as an example
                // Remove the reference: 3 x 2 -> 1 -> null
                currentHead = currentHead.next;
                // currentHead is now equal to 2 -> 1 -> null
                break; // break out of the loop
            }

            // prev is now equal to 2 -> 1 -> null since currentHead is equal to 2 -> 1 -> null
            // if "currentHead.data == value" matched, but if not,
            // they ignore it and return to the original: "3 -> 2 -> 1 -> null"
            prev = currentHead;
            // "currentHead = currentHead.next" means move to the next
            // if the first value doesn't match linked list value
            // And then, the while loop starts again...
            currentHead = currentHead.next;
        }

        // If wasn't found in the head or middle, it must be on tail
        if (currentHead.data == value) {
            prev.next = null;
        }
        this.size--;
    }
}

// Log 1: Not Deleted Singly Linked List
SinglyLinkedList.prototype.log1 = function () {
    var head = this.head.data;
    var next1 = this.head.next.data;
    var next2 = this.head.next.next.data;
    var next3 = this.head.next.next.next;
    return {
        Tree: this.head,
        Result: head + " -> " + next1 + " -> " + next2 + " -> " + next3
    };
}

// Log 2: Deleted Singly Linked List
SinglyLinkedList.prototype.log2 = function () {
    var head = this.head.data;
    var next1 = this.head.next

    return {
        Tree: this.head,
        Result: head + " -> " + next1
    };;
}

// Instance(example) of the SinglyLinkedList class
var sll = new SinglyLinkedList();

// Add
sll.insert(1); // 1 -> null
sll.insert(2); // 2 -> 1 -> null
sll.insert(3); // 3 -> 2 -> 1 -> null


// Result
console.log(sll.log1()); // Prints " 3 -> 2 -> 1 -> null"

// Remove
sll.remove(3); // 2 -> 1 -> null
sll.remove(2); // 1 -> null

// Result
sll.log2(); // Prints "1 -> null"

Execution:

// Singly Linked List Node function SinglyLinkedListNode(data) { this.data = data; this.next = null; } // Singly Linked List function SinglyLinkedList() { this.head = null; this.size = 0; } // Base: Empty SinglyLinkedList.prototype.isEmpty = function () { return this.size == 0; } // Insert SinglyLinkedList.prototype.insert = function (value) { if (this.head === null) { this.head = new SinglyLinkedListNode(value); } else { var temp = this.head; this.head = new SinglyLinkedListNode(value); this.head.next = temp; } this.size++; } // Remove SinglyLinkedList.prototype.remove = function (value) { var currentHead = this.head; // this.head is equal to 3 -> 2 -> 1 -> null // currentHead.data is equal to "3" if (currentHead.data == value) { // x = means deleted reference as an example // Remove the reference: 3 x 2 -> 1 -> null this.head = currentHead.next; // Reduce the size by "one" this.size--; } else { var prev = currentHead; // prev is equal to 3 -> 2 -> 1 -> null // currentHead.next is equal to 2 -> 1 -> null while (currentHead.next) { // currentHead.data is equal to "3" if (currentHead.data == value) { // prev.next is equal to 2 -> 1 -> null // currentHead.next is equal to 2 -> 1 -> null prev.next = currentHead.next; // prev is equal to 3 -> 2 -> 1 -> null prev = currentHead; // x = means deleted reference as an example // Remove the reference: 3 x 2 -> 1 -> null currentHead = currentHead.next; // currentHead is now equal to 2 -> 1 -> null break; // break out of the loop } // prev is now equal to 2 -> 1 -> null since currentHead is equal to 2 -> 1 -> null // if "currentHead.data == value" matched, but if not, // they ignore it and return to the original: "3 -> 2 -> 1 -> null" prev = currentHead; // "currentHead = currentHead.next" means move to the next // if the first value doesn't match linked list value // And then, the while loop starts again... currentHead = currentHead.next; } // If wasn't found in the head or middle, it must be on tail if (currentHead.data == value) { prev.next = null; } this.size--; } } // Log 1: Not Deleted Singly Linked List SinglyLinkedList.prototype.log1 = function () { var head = this.head.data; var next1 = this.head.next.data; var next2 = this.head.next.next.data; var next3 = this.head.next.next.next; return { Tree: this.head, Result: head + " -> " + next1 + " -> " + next2 + " -> " + next3 }; } // Log 2: Deleted Singly Linked List SinglyLinkedList.prototype.log2 = function () { var head = this.head.data; var next1 = this.head.next return { Tree: this.head, Result: head + " -> " + next1 };; } // Instance(example) of the SinglyLinkedList class var sll = new SinglyLinkedList(); // Add sll.insert(1); // 1 -> null sll.insert(2); // 2 -> 1 -> null sll.insert(3); // 3 -> 2 -> 1 -> null // Result console.log(sll.log1()); // Prints " 3 -> 2 -> 1 -> null" // Remove sll.remove(3); // 2 -> 1 -> null sll.remove(2); // 1 -> null // Result sll.log2(); // Prints "1 -> null"

Time Complexity: O(n)O(n)

Note (๐Ÿ“): In the worst case, the entire linked list must be traversed.

Deletion at the Head (โŒโžก๏ธโžก๏ธ)

Deleting an element at the head of the linked list is possible in O(1)O(1) . No traversal is required. The implementation of this deletion is shown in the following code block below. This allows the linked list to implement a stack (remember the stack in Part 12). The last-added item can be removed in O(1)O(1) . Let's look at some example code below:

Example:

// Singly Linked List Node
function SinglyLinkedListNode(data) {
    this.data = data;
    this.next = null;
}


// Singly Linked List
function SinglyLinkedList() {
    this.head = null;
    this.size = 0;
}

// Base: Empty
SinglyLinkedList.prototype.isEmpty = function () {
    return this.size == 0;
}

// Insert
SinglyLinkedList.prototype.insert = function (value) {
    if (this.head === null) {
        this.head = new SinglyLinkedListNode(value);
    } else {
        var temp = this.head;
        this.head = new SinglyLinkedListNode(value);
        this.head.next = temp;
    }
    this.size++;
}

// Delete
SinglyLinkedList.prototype.deleteAtHead = function () {
    var toReturn = null;

    if (this.head !== null) {
        toReturn = this.head.data;
        this.data = this.head.next;
        this.size--;
    }
    return toReturn;
}

// Log 1: Not Deleted Singly Linked List
SinglyLinkedList.prototype.log1 = function () {
    var head = this.head.data;
    var next1 = this.head.next.data;
    var next2 = this.head.next.next.data;
    var next3 = this.head.next.next.next;
    return {
        Tree: this.head,
        Result: head + " -> " + next1 + " -> " + next2 + " -> " + next3
    };
}

// Log 2: Deleted Singly Linked List
SinglyLinkedList.prototype.log2 = function () {
    var next1 = this.head.next.data;
    var next2 = this.head.next.next.data;
    var next3 = this.head.next.next.next;

    return {
        Tree: this.head,
        Result: next1 + " -> " + next2 + " -> " + next3
    };;
}

// Instance(example) of the SinglyLinkedList class
var sll = new SinglyLinkedList();

// Add
sll.insert(1); // 1 -> null
sll.insert(2); // 2 -> 1 -> null
sll.insert(3); // 3 -> 2 -> 1 -> null


// Result
console.log(sll.log1()); // Prints " 3 -> 2 -> 1 -> null"

// Remove
sll.deleteAtHead(); // 2 -> 1 -> null

// Result
sll.log2(); // Prints "1 -> null"

Execution:

// Singly Linked List Node function SinglyLinkedListNode(data) { this.data = data; this.next = null; } // Singly Linked List function SinglyLinkedList() { this.head = null; this.size = 0; } // Base: Empty SinglyLinkedList.prototype.isEmpty = function () { return this.size == 0; } // Insert SinglyLinkedList.prototype.insert = function (value) { if (this.head === null) { this.head = new SinglyLinkedListNode(value); } else { var temp = this.head; this.head = new SinglyLinkedListNode(value); this.head.next = temp; } this.size++; } // Delete SinglyLinkedList.prototype.deleteAtHead = function () { var toReturn = null; if (this.head !== null) { toReturn = this.head.data; this.data = this.head.next; this.size--; } return toReturn; } // Log 1: Not Deleted Singly Linked List SinglyLinkedList.prototype.log1 = function () { var head = this.head.data; var next1 = this.head.next.data; var next2 = this.head.next.next.data; var next3 = this.head.next.next.next; return { Tree: this.head, Result: head + " -> " + next1 + " -> " + next2 + " -> " + next3 }; } // Log 2: Deleted Singly Linked List SinglyLinkedList.prototype.log2 = function () { var next1 = this.head.next.data; var next2 = this.head.next.next.data; var next3 = this.head.next.next.next; return { Tree: this.head, Result: next1 + " -> " + next2 + " -> " + next3 };; } // Instance(example) of the SinglyLinkedList class var sll = new SinglyLinkedList(); // Add sll.insert(1); // 1 -> null sll.insert(2); // 2 -> 1 -> null sll.insert(3); // 3 -> 2 -> 1 -> null // Result console.log(sll.log1()); // Prints " 3 -> 2 -> 1 -> null" // Remove sll.deleteAtHead(); // 2 -> 1 -> null // Result sll.log2(); // Prints "1 -> null"

Search (โžก๏ธโžก๏ธ๐Ÿ”Ž)

To find out whether a value exists in a singly linked list, simple iteration through all its next pointers is needed. Let's look at some example code below:

Example:

// Singly Linked List Node
function SinglyLinkedListNode(data) {
    this.data = data;
    this.next = null;
}

// Singly Linked List
function SinglyLinkedList() {
    this.head = null;
    this.size = 0;
}

// Base: Empty
SinglyLinkedList.prototype.isEmpty = function () {
    return this.size == 0;
}

// Insert
SinglyLinkedList.prototype.insert = function (value) {
    if (this.head === null) {
        this.head = new SinglyLinkedListNode(value);
    } else {
        var temp = this.head;
        this.head = new SinglyLinkedListNode(value);
        this.head.next = temp;
    }
    this.size++;
}

// Search
SinglyLinkedList.prototype.find = function (value) {
    var currentHead = this.head;

    while (currentHead.next) {
        if (currentHead.data == value) {
            return true;
        }
        currentHead = currentHead.next;
    }
    return false;
}

// Instance(example) of the SinglyLinkedList class
var sll = new SinglyLinkedList();

// Add
sll.insert(1); // 1 -> null
sll.insert(2); // 2 -> 1 -> null
sll.insert(3); // 3 -> 2 -> 1 -> null

// Search
sll.find(3); // Prints "true"

Execution:

// Singly Linked List Node function SinglyLinkedListNode(data) { this.data = data; this.next = null; } // Singly Linked List function SinglyLinkedList() { this.head = null; this.size = 0; } // Base: Empty SinglyLinkedList.prototype.isEmpty = function () { return this.size == 0; } // Insert SinglyLinkedList.prototype.insert = function (value) { if (this.head === null) { this.head = new SinglyLinkedListNode(value); } else { var temp = this.head; this.head = new SinglyLinkedListNode(value); this.head.next = temp; } this.size++; } // Search SinglyLinkedList.prototype.find = function (value) { var currentHead = this.head; while (currentHead.next) { if (currentHead.data == value) { return true; } currentHead = currentHead.next; } return false; } // Instance(example) of the SinglyLinkedList class var sll = new SinglyLinkedList(); // Add sll.insert(1); // 1 -> null sll.insert(2); // 2 -> 1 -> null sll.insert(3); // 3 -> 2 -> 1 -> null // Search sll.find(3); // Prints "true"

Time Complexity: O(n)O(n)

Note (๐Ÿ“): In the worst case, the entire linked list must be traversed.

Doubly Linked Lists (โ†”๏ธโ†”๏ธ)

Alt text

A doubly linked list can be thought of as a bidirectional(two-way) singly linked list. Each node in the doubly linked list has both a next pointer and a prev pointer. The following code block below implements the doubly linked list node:

Example:

// Doubly Linked List Node
function DoublyLinkedListNode(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
}

In addition, a doubly linked list has a head pointer as well as a tail pointer. The head refers to the beginning, and the tail refers to the end. This is implemented in the following code below along with a helper function to check whether the doubly linked list is empty:

Example:

// Doubly Linked List
function DoublyLinkedList() {
    this.head = null;
    this.tail = null;
    this.size = 0;
}

// Empty
DoublyLinkedList.prototype.isEmpty = function () {
    return this.size == 0;
}

Each node in a doubly linked list has next and prev properties. Figure 13-3 shows an example of a doubly linked list:

Alt Text

Figure 13-3. Doubly linked list example with five nodes

Insertion at the Head (โœ…โ†”๏ธโ†”๏ธ)

Inserting into the head of the doubly linked list is the same as the insertion for the singly linked list except that it has to update the prev pointer as well. The following code block below shows how to insert into the doubly linked list. If the head of the linked list is empty, the head and the tail are set to the new node.

This is because when there is only one element, that element is both the head and the tail. Otherwise, the temp variable is used to store the new node. The new nodeโ€™s next points to the current head, and then the current headโ€™s prev points to the new node. Finally, the head is updated to the new node. Let's look at it below:

Example:

// Doubly Linked List Node
function DoublyLinkedListNode(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
}

// Doubly Linked List
function DoublyLinkedList() {
    this.head = null;
    this.tail = null;
    this.size = 0;
}

//  Add
DoublyLinkedList.prototype.addAtFront = function (value) {
    // At first, the head is null
    if (this.head === null) {
        // So this is the first code block to be executed
        // "this.head = new DoublyLinkedListNode(value);" means
        //  Add "1" to data at current head
        this.head = new DoublyLinkedListNode(value);
        // "this.tail = this.head;" means
        // Add "1" to data at current tail
        this.tail = this.head;
        // This means both head and tail have the
        // same value of "1" at first.
        // After "1", it will go to "else statement"
        // Because "this.head" is now not null
    } else {
        // This is the code block to be executed next after "1"
        // if "this.head" is not null
        // "temp = new DoublyLinkedListNode(value);" means add new node to "this.data"
        // And that is "2". Because that's next
        var temp = new DoublyLinkedListNode(value);
        // "temp.next = this.head;" means add the current head
        // which is "1" and make
        // the last head we did earlier to become the tail
        // And now our head is "2" and the tail is "1"
        // But the "temp.next" said "make 1 as the head"
        // Because that's the last node we add in "temp.next"
        temp.next = this.head; // Working for "tail"
        // "this.head.prev = temp;" means just add the new head
        // "this.head.prev = temp;" means "add 3 after 2"
        // Because the earlier head was "2"
        // And now, our current head is "3"
        this.head.prev = temp; // Working for "head"
        // "this.head = temp;" means "add 2 after 1" and "add 3 after 2"
        // And now, our head is "3" and our tail is "1"
        // "this.head = temp;" makes the navigation
        // to next and prev pointer easier
        this.head = temp;
        // "add 3 after 2" and "add 2 after 1" equate to:
        // "3 <-> 2" as our head to middle and "2 <-> 1" as middle to tail
        // And now we have head and tail
    }
    this.size++;
}

// Log
DoublyLinkedList.prototype.log = function () {
    return {
        head: this.head.data,
        tail: this.tail.data
    };
    // You can try "this.head" and "this.tail" to see
    // the tree structure and study them
}

// Instance(example) of the Doubly Linked List class
var dll = new DoublyLinkedList();

// Add
dll.addAtFront(1);
dll.addAtFront(2);
dll.addAtFront(3);

// Result
dll.log() // Prints "{ head: 3, tail: 1 }"

Execution:

// Doubly Linked List Node function DoublyLinkedListNode(data) { this.data = data; this.next = null; this.prev = null; } // Doubly Linked List function DoublyLinkedList() { this.head = null; this.tail = null; this.size = 0; } // Add DoublyLinkedList.prototype.addAtFront = function (value) { // At first, the head is null if (this.head === null) { // So this is the first code block to be executed // "this.head = new DoublyLinkedListNode(value);" means // Add "1" to data at current head this.head = new DoublyLinkedListNode(value); // "this.tail = this.head;" means // Add "1" to data at current tail this.tail = this.head; // This means both head and tail have the // same value of "1" at first. // After "1", it will go to "else statement" // Because "this.head" is now not null } else { // This is the code block to be executed next after "1" // if "this.head" is not null // "temp = new DoublyLinkedListNode(value);" means add new node to "this.data" // And that is "2". Because that's next var temp = new DoublyLinkedListNode(value); // "temp.next = this.head;" means add the current head // which is "1" and make // the last head we did earlier to become the tail // And now our head is "2" and the tail is "1" // But the "temp.next" said "make 1 as the head" // Because that's the last node we add in "temp.next" temp.next = this.head; // Working for "tail" // "this.head.prev = temp;" means just add the new head // "this.head.prev = temp;" means "add 3 after 2" // Because the earlier head was "2" // And now, our current head is "3" this.head.prev = temp; // Working for "head" // "this.head = temp;" means "add 2 after 1" and "add 3 after 2" // And now, our head is "3" and our tail is "1" // "this.head = temp;" makes the navigation // to next and prev pointer easier this.head = temp; // "add 3 after 2" and "add 2 after 1" equate to: // "3 <-> 2" as our head to middle and "2 <-> 1" as middle to tail // And now we have head and tail } this.size++; } // Log DoublyLinkedList.prototype.log = function () { return { head: this.head.data, tail: this.tail.data }; // You can try "this.head" and "this.tail" to see // the tree structure and study them } // Instance(example) of the Doubly Linked List class var dll = new DoublyLinkedList(); // Add dll.addAtFront(1); dll.addAtFront(2); dll.addAtFront(3); // Result dll.log() // Prints "{ head: 3, tail: 1 }"

Time Complexity: O(1)O(1)

Insertion at the Tail (โ†”๏ธโ†”๏ธโœ…)

Similarly, a new node can be added to the tail of a doubly linked list, as implemented in the following code block:

Example:

// Doubly Linked List Node
function DoublyLinkedListNode(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
}

// Doubly Linked List
function DoublyLinkedList() {
    this.head = null;
    this.tail = null;
    this.size = 0;
}

//  Add
DoublyLinkedList.prototype.addAtTail = function (value) {
    // At first, the tail is null
    if (this.tail === null) {
        // So this is the first code block to be executed
        // "this.tail = new DoublyLinkedListNode(value);" means
        //  Add "1" to data at current tail
        this.tail = new DoublyLinkedListNode(value);
        // "this.head = this.tail;" means
        // Add "1" to data at current head
        this.head = this.tail;
        // This means both head and tail have the
        // same value of "1" at first.
        // After "1", it will go to "else statement"
        // Because "this.tail" is now not null
    } else {
        // This is the code block to be executed next after "1"
        // if "this.tail" is not null
        // "temp = new DoublyLinkedListNode(value);" means add new node to "this.data"
        // And that is "2". Because that's next
        var temp = new DoublyLinkedListNode(value);
        // "temp.prev = this.tail;" means add the current tail
        // which is "1" and make
        // the last tail we did earlier to become the head
        // And now our head is "2" and the tail is "1"
        // But the "temp.prev" said "make 2 as the tail"
        // Because that's the last node we add in "temp.prev"
        temp.prev = this.tail; // Working for "head"
        // "this.tail.next = temp;" means just add the new tail
        // "this.tail.next = temp;" means "add 3 after 2"
        // Because the earlier tail  was "2"
        // And now, our current tail is "3"
        this.tail.next = temp; // Working for "tail"
        // "this.tail = temp;" means "add 2 after 1" and "add 3 after 2"
        // And now, our tail is "3" and our head is "1"
        // "this.head = temp;" makes the navigation
        // to next and prev pointer easier
        this.tail = temp;
        // "add 2 after 1" and "add 3 after 2" equate to:
        // "1 <-> 2" as our head to middle and "2 <-> 3" as middle to tail
        // And now we have head and tail
        // In insertion to the head, we just reverse this code
        // a little bit. So there's just slight change in this code
    }
    this.size++;
}

// Log
DoublyLinkedList.prototype.log = function () {
    return {
        head: this.head.data,
        tail: this.tail.data
    };
    // You can try "this.head" and "this.tail" to see
    // the tree structure and study them
}

// Instance(example) of the Doubly Linked List class
var dll = new DoublyLinkedList();

// Add
dll.addAtTail(1);
dll.addAtTail(2);
dll.addAtTail(3);

// Result
dll.log() // Prints "{ head: 1, tail: 3 }"

Example:

// Doubly Linked List Node function DoublyLinkedListNode(data) { this.data = data; this.next = null; this.prev = null; } // Doubly Linked List function DoublyLinkedList() { this.head = null; this.tail = null; this.size = 0; } // Add DoublyLinkedList.prototype.addAtTail = function (value) { // At first, the tail is null if (this.tail === null) { // So this is the first code block to be executed // "this.tail = new DoublyLinkedListNode(value);" means // Add "1" to data at current tail this.tail = new DoublyLinkedListNode(value); // "this.head = this.tail;" means // Add "1" to data at current head this.head = this.tail; // This means both head and tail have the // same value of "1" at first. // After "1", it will go to "else statement" // Because "this.tail" is now not null } else { // This is the code block to be executed next after "1" // if "this.tail" is not null // "temp = new DoublyLinkedListNode(value);" means add new node to "this.data" // And that is "2". Because that's next var temp = new DoublyLinkedListNode(value); // "temp.prev = this.tail;" means add the current tail // which is "1" and make // the last tail we did earlier to become the head // And now our head is "2" and the tail is "1" // But the "temp.prev" said "make 2 as the tail" // Because that's the last node we add in "temp.prev" temp.prev = this.tail; // Working for "head" // "this.tail.next = temp;" means just add the new tail // "this.tail.next = temp;" means "add 3 after 2" // Because the earlier tail was "2" // And now, our current tail is "3" this.tail.next = temp; // Working for "tail" // "this.tail = temp;" means "add 2 after 1" and "add 3 after 2" // And now, our tail is "3" and our head is "1" // "this.head = temp;" makes the navigation // to next and prev pointer easier this.tail = temp; // "add 2 after 1" and "add 3 after 2" equate to: // "1 <-> 2" as our head to middle and "2 <-> 3" as middle to tail // And now we have head and tail // In insertion to the head, we just reverse this code // a little bit. So there's just slight change in this code } this.size++; } // Log DoublyLinkedList.prototype.log = function () { return { head: this.head.data, tail: this.tail.data }; // You can try "this.head" and "this.tail" to see // the tree structure and study them } // Instance(example) of the Doubly Linked List class var dll = new DoublyLinkedList(); // Add dll.addAtTail(1); dll.addAtTail(2); dll.addAtTail(3); // Result dll.log() // Prints "{ head: 1, tail: 3 }"

Time Complexity: O(1)O(1)

Deletion at the Head (โŒโ†”๏ธโ†”๏ธ)

Removing a node at the head from a doubly linked list can be done in O(1)O(1) time. If there is only one item, both the head and the tail are set to null. Otherwise, the head is set to the headโ€™s next pointer. Finally, the new headโ€™s prev is set to null to remove the reference of the old head. This is implemented in the following code block. This is great because it can be used like a dequeue function from the queue data structure. Let's look at some example code below:

Example:

// Doubly Linked List Node
function DoublyLinkedListNode(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
}

// Doubly Linked List
function DoublyLinkedList() {
    this.head = null;
    this.tail = null;
    this.size = 0;
}

//  Add
DoublyLinkedList.prototype.addAtFront = function (value) {
    if (this.head === null) {
        this.head = new DoublyLinkedListNode(value);
        this.tail = this.head;
    } else {
        var temp = new DoublyLinkedListNode(value);
        temp.next = this.head;
        this.head.prev = temp;
        this.head = temp;
    }
    this.size++;
}

// Delete
DoublyLinkedList.prototype.deleteAtHead = function () {
    var toReturn = null;

    if (this.head !== null) {
        toReturn = this.head.data;
        if (this.tail === this.head) {
            this.head = this.tail = null;
        } else {
            this.head = this.head.next;
            this.head.prev = null;
        }
    }
    this.size--;
    return toReturn;
}

// Log 1
DoublyLinkedList.prototype.log1 = function () {
    return {
        head: this.head.data,
        tail: this.tail.data
    };
}

// Log 2
DoublyLinkedList.prototype.log2 = function () {
    return {
        head: this.head.data,
        tail: this.tail.data
    };
}

// Instance(example) of the Doubly Linked List class
var dll = new DoublyLinkedList();

// Add
dll.addAtFront(1);
dll.addAtFront(2);
dll.addAtFront(3);

// Result
console.log(dll.log1()) // Prints "{ head: 3, tail: 1 }"

// Delete
dll.deleteAtHead();

// Result
console.log(dll.log2()) // Prints "{ head: 2, tail: 1 }"

Execution:

// Doubly Linked List Node function DoublyLinkedListNode(data) { this.data = data; this.next = null; this.prev = null; } // Doubly Linked List function DoublyLinkedList() { this.head = null; this.tail = null; this.size = 0; } // Add DoublyLinkedList.prototype.addAtFront = function (value) { if (this.head === null) { this.head = new DoublyLinkedListNode(value); this.tail = this.head; } else { var temp = new DoublyLinkedListNode(value); temp.next = this.head; this.head.prev = temp; this.head = temp; } this.size++; } // Delete DoublyLinkedList.prototype.deleteAtHead = function () { var toReturn = null; if (this.head !== null) { toReturn = this.head.data; if (this.tail === this.head) { this.head = this.tail = null; } else { this.head = this.head.next; this.head.prev = null; } } this.size--; return toReturn; } // Log 1 DoublyLinkedList.prototype.log1 = function () { return { head: this.head.data, tail: this.tail.data }; } // Log 2 DoublyLinkedList.prototype.log2 = function () { return { head: this.head.data, tail: this.tail.data }; } // Instance(example) of the Doubly Linked List class var dll = new DoublyLinkedList(); // Add dll.addAtFront(1); dll.addAtFront(2); dll.addAtFront(3); // Result console.log(dll.log1()) // Prints "{ head: 3, tail: 1 }" // Delete dll.deleteAtHead(); // Result console.log(dll.log2()) // Prints "{ head: 2, tail: 1 }"

Time Complexity: O(1)O(1)

Deletion at the Tail (โ†”๏ธโ†”๏ธโŒ)

The tail node can be removed in O(1)O(1) time. By having the ability to remove at , the doubly linked list can also be thought of as a bidirectional(two-way) queue data structure. A queue can dequeue the first-added item, but a doubly linked list can dequeue the tail the item at the tail or the item at the head in O(1)O(1) time. Let's look at some example code below:

Example:

// Doubly Linked List Node
function DoublyLinkedListNode(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
}

// Doubly Linked List
function DoublyLinkedList() {
    this.head = null;
    this.tail = null;
    this.size = 0;
}

//  Add
DoublyLinkedList.prototype.addAtTail = function (value) {
    if (this.tail === null) {
        this.tail = new DoublyLinkedListNode(value);
        this.head = this.tail;
    } else {
        var temp = new DoublyLinkedListNode(value);
        temp.prev = this.tail;
        this.tail.next = temp;
        this.tail = temp;
    }
    this.size++;
}

// Delete
DoublyLinkedList.prototype.deleteAtTail = function () {
    var toReturn = null;

    if (this.tail !== null) {
        toReturn = this.tail.data;

        if (this.tail == this.head) {
            this.head = this.tail = null;
        } else {
            this.tail = this.tail.prev;
            this.tail.next = null;
        }
        this.size--;
        return toReturn;
    }
}

// Log 1
DoublyLinkedList.prototype.log1 = function () {
    return {
        head: this.head.data,
        tail: this.tail.data
    };
}

// Log 2
DoublyLinkedList.prototype.log2 = function () {
    return {
        head: this.head.data,
        tail: this.tail.data
    };
}

// Instance(example) of the Doubly Linked List class
var dll = new DoublyLinkedList();

// Add
dll.addAtTail(1);
dll.addAtTail(2);
dll.addAtTail(3);

// Result
console.log(dll.log1()) // Prints "{ head: 1, tail: 3 }"

// Delete
dll.deleteAtTail();

//  Result
dll.log2() // Prints "{ head: 1, tail: 2 }"

Execution:

// Doubly Linked List Node function DoublyLinkedListNode(data) { this.data = data; this.next = null; this.prev = null; } // Doubly Linked List function DoublyLinkedList() { this.head = null; this.tail = null; this.size = 0; } // Add DoublyLinkedList.prototype.addAtTail = function (value) { if (this.tail === null) { this.tail = new DoublyLinkedListNode(value); this.head = this.tail; } else { var temp = new DoublyLinkedListNode(value); temp.prev = this.tail; this.tail.next = temp; this.tail = temp; } this.size++; } // Delete DoublyLinkedList.prototype.deleteAtTail = function () { var toReturn = null; if (this.tail !== null) { toReturn = this.tail.data; if (this.tail == this.head) { this.head = this.tail = null; } else { this.tail = this.tail.prev; this.tail.next = null; } this.size--; return toReturn; } } // Log 1 DoublyLinkedList.prototype.log1 = function () { return { head: this.head.data, tail: this.tail.data }; } // Log 2 DoublyLinkedList.prototype.log2 = function () { return { head: this.head.data, tail: this.tail.data }; } // Instance(example) of the Doubly Linked List class var dll = new DoublyLinkedList(); // Add dll.addAtTail(1); dll.addAtTail(2); dll.addAtTail(3); // Result console.log(dll.log1()) // Prints "{ head: 1, tail: 3 }" // Delete dll.deleteAtTail(); // Result dll.log2() // Prints "{ head: 1, tail: 2 }"

Time Complexity: O(1)O(1)

Search (โ†”๏ธ๐Ÿ”โ†”๏ธ)

To find out whether a value exists in a doubly linked list, you can start at the head and use the next pointer. The following code
block is the same implementation as the singly linked list search implementation, which starts at the head and looks for the item:

Example:

// Doubly Linked List Node
function DoublyLinkedListNode(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
}

// Doubly Linked List
function DoublyLinkedList() {
    this.head = null;
    this.tail = null;
    this.size = 0;
}

//  Add
DoublyLinkedList.prototype.addAtFront = function (value) {
    if (this.head === null) {
        this.head = new DoublyLinkedListNode(value);
        this.tail = this.head;
    } else {
        var temp = new DoublyLinkedListNode(value);
        temp.next = this.head;
        this.head.prev = temp;
        this.head = temp;
    }
    this.size++;
}

// Search
DoublyLinkedList.prototype.findStartingHead = function (value) {
    var currentHead = this.head;
    while (currentHead.next) {
        if (currentHead.data == value) {
            return true;
        }
        currentHead = currentHead.next;
    }
    return false;
}

// Instance(example) of the Doubly Linked List class
var dll = new DoublyLinkedList();

// Add
dll.addAtFront(3);
dll.addAtFront(2);
dll.addAtFront(1);

// Search
dll.findStartingHead(1) // Prints "true"

Execution:

// Doubly Linked List Node function DoublyLinkedListNode(data) { this.data = data; this.next = null; this.prev = null; } // Doubly Linked List function DoublyLinkedList() { this.head = null; this.tail = null; this.size = 0; } // Add DoublyLinkedList.prototype.addAtFront = function (value) { if (this.head === null) { this.head = new DoublyLinkedListNode(value); this.tail = this.head; } else { var temp = new DoublyLinkedListNode(value); temp.next = this.head; this.head.prev = temp; this.head = temp; } this.size++; } // Search DoublyLinkedList.prototype.findStartingHead = function (value) { var currentHead = this.head; while (currentHead.next) { if (currentHead.data == value) { return true; } currentHead = currentHead.next; } return false; } // Instance(example) of the Doubly Linked List class var dll = new DoublyLinkedList(); // Add dll.addAtFront(3); dll.addAtFront(2); dll.addAtFront(1); // Search dll.findStartingHead(1) // Prints "true"

Time Complexity: O(n)O(n)

The following code traverses the doubly linked list starting with the tail using prev pointers:

Example:

// Doubly Linked List Node
function DoublyLinkedListNode(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
}

// Doubly Linked List
function DoublyLinkedList() {
    this.head = null;
    this.tail = null;
    this.size = 0;
}

//  Add
DoublyLinkedList.prototype.addAtTail = function (value) {
    if (this.tail === null) {
        this.tail = new DoublyLinkedListNode(value);
        this.head = this.tail;
    } else {
        var temp = new DoublyLinkedListNode(value);
        temp.prev = this.tail;
        this.tail.next = temp;
        this.tail = temp;
    }
    this.size++;
}

// Search
DoublyLinkedList.prototype.findStartingTail = function (value) {
    var currentTail = this.tail;
    while (currentTail.prev) {
        if (currentTail.data == value) {
            return true;
        }
        currentTail = currentTail.prev;
    }
    return false;
}

// Instance(example) of the Doubly Linked List class
var dll = new DoublyLinkedList();

// Add
dll.addAtTail(1);
dll.addAtTail(2);
dll.addAtTail(3);

// Search
dll.findStartingTail(3) // Prints "true"

Execution:

// Doubly Linked List Node function DoublyLinkedListNode(data) { this.data = data; this.next = null; this.prev = null; } // Doubly Linked List function DoublyLinkedList() { this.head = null; this.tail = null; this.size = 0; } // Add DoublyLinkedList.prototype.addAtTail = function (value) { if (this.tail === null) { this.tail = new DoublyLinkedListNode(value); this.head = this.tail; } else { var temp = new DoublyLinkedListNode(value); temp.prev = this.tail; this.tail.next = temp; this.tail = temp; } this.size++; } // Search DoublyLinkedList.prototype.findStartingTail = function (value) { var currentTail = this.tail; while (currentTail.prev) { if (currentTail.data == value) { return true; } currentTail = currentTail.prev; } return false; } // Instance(example) of the Doubly Linked List class var dll = new DoublyLinkedList(); // Add dll.addAtTail(1); dll.addAtTail(2); dll.addAtTail(3); // Search dll.findStartingTail(3) // Prints "true"

Time Complexity: O(n)O(n)

Note (๐Ÿ“): Although the time complexity for search is the same as the singly linked listโ€™s search, only the doubly linked list can search bidirectionally (using prev or next). This means that if given a reference to a doubly linked list node, doubly linked lists can perform a full search, but a singly linked list is limited to only its next pointers. (๐Ÿ˜‰)

Summary (๐Ÿ“š๐Ÿ“š)

Alt text

The linked list works by having a next pointer (and previous, pointer if doubly linked) to a different node. Insertion for both singly and doubly linked lists has a constant time complexity of O(1)O(1) . The time complexity of deleting from the head of the singly and doubly linked lists is O(1)O(1) as well.

However, searching for an item in both singly and doubly linked list takes O(n)O(n) time. Doubly linked lists should be used when bidirectional(two-way) search is required. Furthermore, doubly linked lists allow you to pop from either the tail or the head of the linked list for a fast O(1)O(1) operation.

Challenge (๐Ÿ”ฅ๐Ÿ”ฅ)

Alt text

These challenge on Linked Lists cover varying problems to aid you solidify the information you have learned from this section. And also, don't forget to post your answer in the comment(with explanation too!): (๐Ÿ˜ƒ)


REVERSE A SINGLY LINKED LIST

Problem: To reverse a singly linked list, simply iterate through each node and set the next property on the current node to the previous node. Give me a code with a time complexity of O(n)O(n) and space complexity of O(1)O(1)

Note (๐Ÿ“): To fully reverse a linked list, the entire N elements of the linked list must be traversed.

Sample:

function reverseSingleLinkedList(sll) { // your code here... }

DELETE DUPLICATES IN A LINKED LIST

Problem: Deleting an item in a linked list is simple. Simply iterate and store visited nodes inside an array. Delete the current element if the current element has already been seen previously. Give me a code with a time complexity of O(n2)O\lparen n^{2}\rparen and a space complexity of O(n)O(n)

Note (๐Ÿ“): Use of the JavaScript Object as a hash table to store and check for seen elements cuts it down to O(n)O(n) but O(n)O(n) in space as extra memory is required for the hash table.

Sample:

function deleteDuplicateInUnsortedSll(sll1) { // You code here... }

Problem: However, this algorithm must iterate over the array with the .indexOf() method, which is O(n)O(n) as well as iterating n times. Hence, it is O(n2)O\lparen n^{2}\rparen in time complexity. In addition, the track array grows to size of NN , and this causes the space complexity to be O(n)O(n) . Letโ€™s cut the time complexity down to O(n)O(n) . So, give me a code with a time complexity of O(n)O\lparen n\rparen and a space complexity of O(n)O(n) .

Sample:

function deleteDuplicateInUnsortedSllBest(sll1) { // You code here... }

Up Next๐Ÿ‘‰ Part 14: Caching (๐Ÿ”ฅ๐Ÿ”ฅ) (August 21-22, 2020)


Alt Text

Discussion

markdown guide
 

Okay, in part 14, the concept of caching comes from the world of operating systems. You can read more about it in a lecture presentation by Jeff Zarnett from the University of Waterloo here ๐Ÿ‘‰ L21-slides-Memory_Segmentation_Pag...