Sources Contact Advanced Search Tutorials

An Interest In:

Web News this Week

Search Archive

Some of Our Sources

View All Sources

Help Webnuz

Referal links:

August 14, 2020 03:30 am GMT

Learn Data Structure and Algorithm in JavaScript | Part 13

The Javascript Dude

@dudejavascript

Remember: one of the most important roles for source code is to communicate clearly, not only to you, but your future self and other code collaborators, what your intent is.

#100DaysOfCode #freeCodeCamp #softwaredevelopment

03:12 AM - 13 Aug 2020

7 4

Yehuda Katz #BlackLivesMatter

@wycats

Hot take: w3schools offers a clearer description of JavaScript features than MDN for a broad audience.

17:18 PM - 12 Aug 2020

26 328

Well Paid Geek JavaScript

@wellpaidgeek

HTML + CSS + JavaScript = highly employable person

17:51 PM - 13 Aug 2020

92 797

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 objects 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 (). Lets examine the singly linked list first.() Let's go! ()

Part 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 (). Lets examine the singly linked list first.() Let's go! ()

Singly Linked Lists ()

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

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 Nodefunction 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 Nodefunction SinglyLinkedListNode(data) {    this.data = data;    this.next = null;}// Singly Linked Listfunction SinglyLinkedList() {    this.head = null;    this.size = 0;}// BaseSinglyLinkedList.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 heads 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 Nodefunction SinglyLinkedListNode(data) {    this.data = data;    this.next = null;}// Singly Linked Listfunction SinglyLinkedList() {    this.head = null;    this.size = 0;}// Base: EmptySinglyLinkedList.prototype.isEmpty = function () {    return this.size == 0;}// InsertSinglyLinkedList.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++;}// LogSinglyLinkedList.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 classvar sll = new SinglyLinkedList();// Addsll.insert(1); // 1 -> nullsll.insert(2); // 2 -> 1 -> nullsll.insert(3); // 3 -> 2 -> 1 -> null// Resultsll.log(); // Prints "3 -> 2 -> 1 -> null"

Execution:

    // Singly Linked List Nodefunction SinglyLinkedListNode(data) {    this.data = data;    this.next = null;}// Singly Linked Listfunction SinglyLinkedList() {    this.head = null;    this.size = 0;}// Base: EmptySinglyLinkedList.prototype.isEmpty = function () {    return this.size == 0;}// InsertSinglyLinkedList.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++;}// LogSinglyLinkedList.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 classvar sll = new SinglyLinkedList();// Addsll.insert(1); // 1 -> nullsll.insert(2); // 2 -> 1 -> nullsll.insert(3); // 3 -> 2 -> 1 -> null// Resultsll.log(); // Prints "3 -> 2 -> 1 -> null"

Time Complexity: $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:

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 Nodefunction SinglyLinkedListNode(data) {    this.data = data;    this.next = null;}// Singly Linked Listfunction SinglyLinkedList() {    this.head = null;    this.size = 0;}// Base: EmptySinglyLinkedList.prototype.isEmpty = function () {    return this.size == 0;}// InsertSinglyLinkedList.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++;}// RemoveSinglyLinkedList.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 ListSinglyLinkedList.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 ListSinglyLinkedList.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 classvar sll = new SinglyLinkedList();// Addsll.insert(1); // 1 -> nullsll.insert(2); // 2 -> 1 -> nullsll.insert(3); // 3 -> 2 -> 1 -> null// Resultconsole.log(sll.log1()); // Prints " 3 -> 2 -> 1 -> null"// Removesll.remove(3); // 2 -> 1 -> nullsll.remove(2); // 1 -> null// Resultsll.log2(); // Prints "1 -> null"

Execution:

    // Singly Linked List Nodefunction SinglyLinkedListNode(data) {    this.data = data;    this.next = null;}// Singly Linked Listfunction SinglyLinkedList() {    this.head = null;    this.size = 0;}// Base: EmptySinglyLinkedList.prototype.isEmpty = function () {    return this.size == 0;}// InsertSinglyLinkedList.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++;}// RemoveSinglyLinkedList.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 ListSinglyLinkedList.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 ListSinglyLinkedList.prototype.log2 = function () {    var head = this.head.data;    var next1 = this.head.nextreturn {    Tree: this.head,    Result: head + " -> " + next1};;}// Instance(example) of the SinglyLinkedList classvar sll = new SinglyLinkedList();// Addsll.insert(1); // 1 -> nullsll.insert(2); // 2 -> 1 -> nullsll.insert(3); // 3 -> 2 -> 1 -> null// Resultconsole.log(sll.log1()); // Prints " 3 -> 2 -> 1 -> null"// Removesll.remove(3); // 2 -> 1 -> nullsll.remove(2); // 1 -> null// Resultsll.log2(); // Prints "1 -> null"

Time Complexity: $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)$ . 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)$ . Let's look at some example code below:

Example:

// Singly Linked List Nodefunction SinglyLinkedListNode(data) {    this.data = data;    this.next = null;}// Singly Linked Listfunction SinglyLinkedList() {    this.head = null;    this.size = 0;}// Base: EmptySinglyLinkedList.prototype.isEmpty = function () {    return this.size == 0;}// InsertSinglyLinkedList.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++;}// DeleteSinglyLinkedList.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 ListSinglyLinkedList.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 ListSinglyLinkedList.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 classvar sll = new SinglyLinkedList();// Addsll.insert(1); // 1 -> nullsll.insert(2); // 2 -> 1 -> nullsll.insert(3); // 3 -> 2 -> 1 -> null// Resultconsole.log(sll.log1()); // Prints " 3 -> 2 -> 1 -> null"// Removesll.deleteAtHead(); // 2 -> 1 -> null// Resultsll.log2(); // Prints "1 -> null"

Execution:

    // Singly Linked List Nodefunction SinglyLinkedListNode(data) {    this.data = data;    this.next = null;}// Singly Linked Listfunction SinglyLinkedList() {    this.head = null;    this.size = 0;}// Base: EmptySinglyLinkedList.prototype.isEmpty = function () {    return this.size == 0;}// InsertSinglyLinkedList.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++;}// DeleteSinglyLinkedList.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 ListSinglyLinkedList.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 ListSinglyLinkedList.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 classvar sll = new SinglyLinkedList();// Addsll.insert(1); // 1 -> nullsll.insert(2); // 2 -> 1 -> nullsll.insert(3); // 3 -> 2 -> 1 -> null// Resultconsole.log(sll.log1()); // Prints " 3 -> 2 -> 1 -> null"// Removesll.deleteAtHead(); // 2 -> 1 -> null// Resultsll.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 Nodefunction SinglyLinkedListNode(data) {    this.data = data;    this.next = null;}// Singly Linked Listfunction SinglyLinkedList() {    this.head = null;    this.size = 0;}// Base: EmptySinglyLinkedList.prototype.isEmpty = function () {    return this.size == 0;}// InsertSinglyLinkedList.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++;}// SearchSinglyLinkedList.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 classvar sll = new SinglyLinkedList();// Addsll.insert(1); // 1 -> nullsll.insert(2); // 2 -> 1 -> nullsll.insert(3); // 3 -> 2 -> 1 -> null// Searchsll.find(3); // Prints "true"

Execution:

    // Singly Linked List Nodefunction SinglyLinkedListNode(data) {    this.data = data;    this.next = null;}// Singly Linked Listfunction SinglyLinkedList() {    this.head = null;    this.size = 0;}// Base: EmptySinglyLinkedList.prototype.isEmpty = function () {    return this.size == 0;}// InsertSinglyLinkedList.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++;}// SearchSinglyLinkedList.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 classvar sll = new SinglyLinkedList();// Addsll.insert(1); // 1 -> nullsll.insert(2); // 2 -> 1 -> nullsll.insert(3); // 3 -> 2 -> 1 -> null// Searchsll.find(3); // Prints "true"

Time Complexity: $O (n)$

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

Doubly Linked Lists ()

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 Nodefunction 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 Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}// EmptyDoublyLinkedList.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:

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 nodes next points to the current head, and then the current heads 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 Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// LogDoublyLinkedList.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 classvar dll = new DoublyLinkedList();// Adddll.addAtFront(1);dll.addAtFront(2);dll.addAtFront(3);// Resultdll.log() // Prints "{ head: 3, tail: 1 }"

Execution:

    // Doubly Linked List Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// LogDoublyLinkedList.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 classvar dll = new DoublyLinkedList();// Adddll.addAtFront(1);dll.addAtFront(2);dll.addAtFront(3);// Resultdll.log() // Prints "{ head: 3, tail: 1 }"

Time Complexity: $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 Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// LogDoublyLinkedList.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 classvar dll = new DoublyLinkedList();// Adddll.addAtTail(1);dll.addAtTail(2);dll.addAtTail(3);// Resultdll.log() // Prints "{ head: 1, tail: 3 }"

Example:

    // Doubly Linked List Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// LogDoublyLinkedList.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 classvar dll = new DoublyLinkedList();// Adddll.addAtTail(1);dll.addAtTail(2);dll.addAtTail(3);// Resultdll.log() // Prints "{ head: 1, tail: 3 }"

Time Complexity: $O (1)$

Deletion at the Head ()

Removing a node at the head from a doubly linked list can be done in $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 heads next pointer. Finally, the new heads 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 Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// DeleteDoublyLinkedList.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 1DoublyLinkedList.prototype.log1 = function () {    return {        head: this.head.data,        tail: this.tail.data    };}// Log 2DoublyLinkedList.prototype.log2 = function () {    return {        head: this.head.data,        tail: this.tail.data    };}// Instance(example) of the Doubly Linked List classvar dll = new DoublyLinkedList();// Adddll.addAtFront(1);dll.addAtFront(2);dll.addAtFront(3);// Resultconsole.log(dll.log1()) // Prints "{ head: 3, tail: 1 }"// Deletedll.deleteAtHead();// Resultconsole.log(dll.log2()) // Prints "{ head: 2, tail: 1 }"

Execution:

    // Doubly Linked List Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// DeleteDoublyLinkedList.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 1DoublyLinkedList.prototype.log1 = function () {    return {        head: this.head.data,        tail: this.tail.data    };}// Log 2DoublyLinkedList.prototype.log2 = function () {    return {        head: this.head.data,        tail: this.tail.data    };}// Instance(example) of the Doubly Linked List classvar dll = new DoublyLinkedList();// Adddll.addAtFront(1);dll.addAtFront(2);dll.addAtFront(3);// Resultconsole.log(dll.log1()) // Prints "{ head: 3, tail: 1 }"// Deletedll.deleteAtHead();// Resultconsole.log(dll.log2()) // Prints "{ head: 2, tail: 1 }"

Time Complexity: $O (1)$

Deletion at the Tail ()

The tail node can be removed in $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)$ time. Let's look at some example code below:

Example:

// Doubly Linked List Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// DeleteDoublyLinkedList.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 1DoublyLinkedList.prototype.log1 = function () {    return {        head: this.head.data,        tail: this.tail.data    };}// Log 2DoublyLinkedList.prototype.log2 = function () {    return {        head: this.head.data,        tail: this.tail.data    };}// Instance(example) of the Doubly Linked List classvar dll = new DoublyLinkedList();// Adddll.addAtTail(1);dll.addAtTail(2);dll.addAtTail(3);// Resultconsole.log(dll.log1()) // Prints "{ head: 1, tail: 3 }"// Deletedll.deleteAtTail();//  Resultconsole.log(dll.log2()) // Prints "{ head: 1, tail: 2 }"

Execution:

    // Doubly Linked List Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// DeleteDoublyLinkedList.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 1DoublyLinkedList.prototype.log1 = function () {    return {        head: this.head.data,        tail: this.tail.data    };}// Log 2DoublyLinkedList.prototype.log2 = function () {    return {        head: this.head.data,        tail: this.tail.data    };}// Instance(example) of the Doubly Linked List classvar dll = new DoublyLinkedList();// Adddll.addAtTail(1);dll.addAtTail(2);dll.addAtTail(3);// Resultconsole.log(dll.log1()) // Prints "{ head: 1, tail: 3 }"// Deletedll.deleteAtTail();//  Resultconsole.log(dll.log2()) // Prints "{ head: 1, tail: 2 }"

Time Complexity: $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 Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// SearchDoublyLinkedList.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 classvar dll = new DoublyLinkedList();// Adddll.addAtFront(1);dll.addAtFront(2);dll.addAtFront(3);// Searchdll.findStartingHead(1) // Prints "true"

Execution:

    // Doubly Linked List Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// SearchDoublyLinkedList.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 classvar dll = new DoublyLinkedList();// Adddll.addAtFront(1);dll.addAtFront(2);dll.addAtFront(3);// Searchconsole.log(dll.findStartingHead(1)) // Prints "true"

Time Complexity: $O (n)$

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

Example:

// Doubly Linked List Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// SearchDoublyLinkedList.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 classvar dll = new DoublyLinkedList();// Adddll.addAtTail(1);dll.addAtTail(2);dll.addAtTail(3);// Searchdll.findStartingTail(3) // Prints "true"

Execution:

    // Doubly Linked List Nodefunction DoublyLinkedListNode(data) {    this.data = data;    this.next = null;    this.prev = null;}// Doubly Linked Listfunction DoublyLinkedList() {    this.head = null;    this.tail = null;    this.size = 0;}//  AddDoublyLinkedList.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++;}// SearchDoublyLinkedList.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 classvar dll = new DoublyLinkedList();// Adddll.addAtTail(1);dll.addAtTail(2);dll.addAtTail(3);// Searchdll.findStartingTail(3) // Prints "true"

Time Complexity: $O (n)$

Note (): Although the time complexity for search is the same as the singly linked lists 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 ()

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)$ . The time complexity of deleting from the head of the singly and doubly linked lists is $O (1)$ as well.

However, searching for an item in both singly and doubly linked list takes $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)$ operation.

Challenge ()

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)$ and space complexity of $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)$

Note (): Use of the JavaScript Object as a hash table to store and check for seen elements cuts it down to $O (n)$ but $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)$ 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 $N$ , and this causes the space complexity to be $O (n)$ . Lets cut the time complexity down to $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)$ .

Sample:

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

Up Next Part 14: Caching () (August 17-18, 2020)

Original Link: https://dev.to/edisonpebojots/learn-data-structure-and-algorithm-in-javascript-part-13-867

Share this article:

View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To