Linked List

It consists of nodes where each node contains data and a reference (link) to the next node in the sequence.

This allows for dynamic memory allocation and efficient insertion and deletion operations compared to arrays.

Node Structure: A node in a linked list typically consists of two components: Data: It holds the actual value or data associated with the node. Next Pointer: It stores the memory address (reference) of the next node in the sequence.

Head and Tail: The linked list is accessed through the head node, which points to the first node in the list. The last node in the list points to NULL or nullptr, indicating the end of the list. This node is known as the tail node.

Types:

• Single-Linked List: each node contains a reference to the next node in the sequence. Traversing a singly linked list is done in a forward direction.

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }

    append(data) {
        const newNode = new Node(data);
        if (!this.head) this.head = newNode;
        else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.length++;
    }

    prepend(data) {
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
    }

    remove(data) {
        let current = this.head;
        let previous = null;
        while (current !== null) {
            if (current.data === data) {
                if (previous === null) this.head = current.next;
                else previous.next = current.next;
                this.length--;
                return current.data;
            }
            previous = current;
            current = current.next;
        }
        return null;
    }

    getNodeAtIndex(index) {
        let counter = 0;
        let currentNode = this.head;
        while (counter !== index && currentNode !== null) {
            currentNode = currentNode.next;
            counter++;
        }
        return currentNode;
    }
    
    insertAt(data, index) {

        if (index < 0 || index > this.length) return false;

        if (index === 0) { this.prepend(data); return true; }

        const newNode = new Node(data);

        let current = this.head;
        let count = 0;
        let previous = null;

        while (count < index) {
            previous = current;
            current = current.next;
            count++;
        }

        newNode.next = current;
        previous.next = newNode;

        this.length++;
        return true;
    }

    removeAt(index) {
        if (index < 0 || index >= this.length) return null;

        let current = this.head;

        if (index === 0) this.head = current.next;

        else {
            let count = 0;
            let previous = null;

            while (count < index) {
                previous = current;
                current = current.next;
                count++;
            }

            previous.next = current.next;
        }

        this.length--;
        return current.data;
    }

    reverse() {
        let prev = null;
        let current = this.head;
        let next = null;

        while (current !== null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        this.head = prev;
    }


    rotate(k) {
        if (k <= 0 || this.head === null || this.head.next === null) return;

        let current = this.head;

        let count = 1;

        while (count < k && current !== null) {
            current = current.next;
            count++;
        }

        if (current === null) return;

        let kthNode = current;

        while (current.next !== null) {
            current = current.next;
        }

        current.next = this.head;

        this.head = kthNode.next;

        kthNode.next = null;
    }

    getSize() { return this.length };

    isEmpty() { return this.length === 0 };

    printList() {
        let current = this.head;
        let result = '';
        while (current) {
            result += current.data + ' -> ';
            current = current.next;
        }
        result += 'null';
        console.log(result);
    }
}


const myLinkedList = new LinkedList();

myLinkedList.append(2);

myLinkedList.append(3);

myLinkedList.append(4);

myLinkedList.prepend(1);

myLinkedList.printList();

myLinkedList.rotate(2);

myLinkedList.printList();

myLinkedList.remove(1);

myLinkedList.printList();

myLinkedList.insertAt(4, 0);

myLinkedList.printList();

myLinkedList.reverse();

myLinkedList.printList();

myLinkedList.removeAt(1);

myLinkedList.printList();

• Double-Linked List: each node contains references to both the next and previous nodes. This allows for traversal in both forward and backward directions, but it requires additional memory for the backward reference.

  

class Node {
    constructor(data) {
        this.prev = null;
        this.data = data;
        this.next = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    append(data) {
        const newNode = new Node(data);
        if (!this.head) this.head = newNode;
        else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.length++;
    }

    prepend(data) {
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
    }

    remove(data) {
        let current = this.head;
        let previous = null;
        while (current !== null) {
            if (current.data === data) {
                if (previous === null) this.head = current.next;
                else previous.next = current.next;
                this.length--;
                return current.data;
            }
            previous = current;
            current = current.next;
        }
        return null;
    }

    getNodeAtIndex(index) {
        let counter = 0;
        let currentNode = this.head;
        while (counter !== index && currentNode !== null) {
            currentNode = currentNode.next;
            counter++;
        }
        return currentNode;
    }

    insertAt(data, index) {

        if (index < 0 || index > this.length) return false;

        if (index === 0) { this.prepend(data); return true; }

        const newNode = new Node(data);

        let current = this.head;
        let count = 0;
        let previous = null;

        while (count < index) {
            previous = current;
            current = current.next;
            count++;
        }

        newNode.next = current;
        previous.next = newNode;

        this.length++;
        return true;
    }

    removeAt(index) {
        if (index < 0 || index >= this.length) return null;

        let current = this.head;

        if (index === 0) this.head = current.next;

        else {
            let count = 0;
            let previous = null;

            while (count < index) {
                previous = current;
                current = current.next;
                count++;
            }

            previous.next = current.next;
        }

        this.length--;
        return current.data;
    }

    reverse() {
        let prev = null;
        let current = this.head;
        let next = null;

        while (current !== null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        this.head = prev;
    }


    rotate(k) {
        if (k <= 0 || this.head === null || this.head.next === null) return;

        let current = this.head;

        let count = 1;

        while (count < k && current !== null) {
            current = current.next;
            count++;
        }

        if (current === null) return;

        let kthNode = current;

        while (current.next !== null) {
            current = current.next;
        }

        current.next = this.head;

        this.head = kthNode.next;

        kthNode.next = null;
    }

    getSize() { return this.length };

    isEmpty() { return this.length === 0 };

    printList() {
        let current = this.head;
        let result = '';
        while (current) {
            result += current.data + ' <-> ';
            current = current.next;
        }
        result += 'null';
        console.log(result);
    }
}


const myDoublyLinkedList = new DoublyLinkedList();

myDoublyLinkedList.append(2);

myDoublyLinkedList.append(3);

myDoublyLinkedList.append(4);

myDoublyLinkedList.prepend(1);

myDoublyLinkedList.printList();

myDoublyLinkedList.rotate(2);

myDoublyLinkedList.printList();

myDoublyLinkedList.remove(1);

myDoublyLinkedList.printList();

myDoublyLinkedList.insertAt(4, 0);

myDoublyLinkedList.printList();

myDoublyLinkedList.reverse();

myDoublyLinkedList.printList();

myDoublyLinkedList.removeAt(1);

myDoublyLinkedList.printList();

• Circular-Linked List: the last node points back to the head node, creating a circular structure. It can be either singly or doubly linked.

  

class CircularLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  // Method to add a node to the end of the list
  append(value) {
    const newNode = {
      value: value,
      next: null
    };

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = this.head; // Circular link
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
      this.tail.next = this.head; // Circular link
    }
  }

  // Method to add a node to the beginning of the list
  prepend(value) {
    const newNode = {
      value: value,
      next: null
    };

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = this.head; // Circular link
    } else {
      newNode.next = this.head;
      this.head = newNode;
      this.tail.next = this.head; // Update tail's next to head for circular link
    }
  }

  // Method to remove a node from the list
  remove(value) {
    if (!this.head) return;

    let current = this.head;
    let prev = null;

    // Find the node to remove
    while (current.value !== value) {
      if (current.next === this.head) return; // Node not found
      prev = current;
      current = current.next;
    }

    // If the node to remove is the head
    if (current === this.head) {
      this.head = this.head.next;
      this.tail.next = this.head; // Update tail's next to head for circular link
    } else if (current === this.tail) { // If the node to remove is the tail
      prev.next = this.head;
      this.tail = prev;
    } else {
      prev.next = current.next;
    }
  }

  // Method to insert a node after a specific node
  insertAfter(after, value) {
    const newNode = {
      value: value,
      next: null
    };
    let current = this.head;

    do {
      if (current.value === after) {
        newNode.next = current.next;
        current.next = newNode;
        if (current === this.tail) this.tail = newNode; // Update tail if necessary
        return;
      }
      current = current.next;
    } while (current !== this.head);
  }

  // Method to print the circular linked list
  printList() {
    let current = this.head;

    if (!current) {
      console.log("Empty list");
      return;
    }

    do {
      console.log(current.value);
      current = current.next;
    } while (current !== this.head);
  }
}

// Example usage
const myList = new CircularLinkedList();

myList.append(1);
myList.append(2);
myList.append(4);

myList.prepend(0);

myList.insertAfter(2, 3);

myList.remove(0);
myList.remove(4);

myList.printList(); // Output: 1 2 3

Operations:

1. Insertion: Adding a new node to a linked list involves adjusting the pointers of the existing nodes to maintain the proper sequence. Insertion can be performed at the beginning, end, or any position within the list

2. Deletion: Removing a node from a linked list requires adjusting the pointers of the neighboring nodes to bridge the gap left by the deleted node. Deletion can be performed at the beginning, end, or any position within the list.

3. Searching: Searching for a specific value in a linked list involves traversing the list from the head node until the value is found or the end of the list is reached.

Applications:

• The list of songs in the music player is linked to the previous and next songs.

• In a web browser, previous and next web page URLs are linked through the previous and next buttons.

• In the image viewer, the previous and next images are linked with the help of the previous and next buttons.

• Switching between two applications is carried out by using “alt+tab” in windows and “cmd+tab” in mac book. It requires the functionality of a circular linked list.

• In mobile phones, we save the contacts of people. The newly entered contact details will be placed at the correct alphabetical order.

• This can be achieved by a linked list to set contact at the correct alphabetical position.

• The modifications that we made in the documents are actually created as nodes in doubly linked list. We can simply use the undo option by pressing Ctrl+Z to modify the contents. It is done by the functionality of a linked list.

Advantages:

• Dynamic Data structure: The size of memory can be allocated or de-allocated at run time based on the operation insertion or deletion.

• Ease of Insertion/Deletion: The insertion and deletion of elements are simpler than arrays since no elements need to be shifted after insertion and deletion, Just the address needed to be updated.

• Efficient Memory Utilization: As we know Linked List is a dynamic data structure the size increases or decreases as per the requirement so this avoids the wastage of memory.

• Implementation: Various advanced data structures can be implemented using a linked list like a stack, queue, graph, hash maps, etc.

Disadvantages:

• Memory usage: The use of pointers is more in linked lists hence, complex and requires more memory.

• Accessing a node: Random access is not possible due to dynamic memory allocation.

• Search operation costly: Searching for an element is costly and requires O(n) time complexity.

• Traversing in reverse order: Traversing is more time-consuming and reverse traversing is not possible in singly linked lists.

.

Data Structures and Algorithms Cheatsheet - 11

Linked Lists Good at 😀:

• Fast insertion

• Fast deletion

• Ordered

• Flexible size

Linked Lists Bad at 😒:

• Slow Lookup

• More Memory

What is a pointer?

In computer science, a pointer is an object in many programming languages that stores a memory address.

This can be that of another value located in computer memory, or in some cases, that of memory-mapped computer hardware.

A pointer references a location in memory, and obtaining the value stored at that location is known as dereferencing the pointer.

As an analogy, a page number in a book's index could be considered a pointer to the corresponding page;

dereferencing such a pointer would be done by flipping to the page with the given page number and reading the text found on that page.

EX:

Data Structures and Algorithms Cheatsheet - 8

Person and newPerson in the example above both point to the same location in memory.