JS - Linear Data Structures 01

Linear Data Structures

Linked List

  • The list is comprised of a series of nodes as shown in the diagram.
  • Is a sequential chain of nodes
  • The head node is the node at the beginning of the list.
  • Each node contains data and a link (or pointer) to the next node in the list.
  • The list is terminated when a node's link is null. This is called the tail node.
  • Can be unidirectional or bidirectional
  • The LinkedList class only kept track of the head of the list.
Create a Singly LinkedList
// LinkedList.js
const Node = require('./Node');
 
class LinkedList {
  constructor() {
    this.head = null;
  }
 
  addToHead(data) {
    const newHead = new Node(data);
    const currentHead = this.head;
    this.head = newHead;
    if (currentHead) {
      this.head.setNextNode(currentHead);
    }
  }
 
  addToTail(data) {
    // temp tail
    let tail = this.head;
    if (!tail) {
      // if no head, the list is empty, we will add the head
      this.head = new Node(data);
    } else {
      // if there is head, we will iterate until the last node (tail)
      while (tail.getNextNode() !== null) {
        tail = tail.getNextNode();
      }
      tail.setNextNode(new Node(data));
    }
  }
 
  removeHead() {
    const removedHead = this.head;
    if (!removedHead) {
      return;
    }
    // remove head by setting head to equal to the next node
    this.head = removedHead.getNextNode();
    return removedHead.data;
  }
 
  printList() {
    let currentNode = this.head;
    let output = '<head> ';
    while (currentNode !== null) {
      output += currentNode.data + ' ';
      currentNode = currentNode.getNextNode();
    }
    output += '<tail>';
    console.log(output);
  }
}
 
module.exports = LinkedList;

Test the LinkedList:

Test the LinkedList
// season.js
const LinkedList = require('./LinkedList');
 
const seasons = new LinkedList();
seasons.printList();
 
seasons.addToHead('summer');
seasons.addToHead('spring');
seasons.printList();
 
seasons.addToTail('fall');
seasons.addToTail('winter');
seasons.printList();
 
seasons.removeHead();
seasons.printList();

You should see this in the terminal

<head> <tail>
<head> spring summer <tail>
<head> spring summer fall winter <tail>
<head> summer fall winter <tail>

Doubly Linked Lists

  • Are comprised of nodes that contain links to the next and previous nodes
  • Are bidirectional, meaning it can be traversed in both directions
  • Have a pointer to a single head node, which serves as the first node in the list
  • Have a pointer to a single tail node, which serves as the last node in the list
  • Require the pointers at the head of the list to be updated after addition to or removal of the head
  • Require the pointers at the tail of the list to be updated after addition to or removed of the tail
  • Require the pointers of the surrounding nodes to be updated after removal from the middle of the list
Create a Doubly LinkedList
// DoublyLinkedList.js
const Node = require('./Node');
 
class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
 
  addToHead(data) {
    const newHead = new Node(data);
    const currentHead = this.head;
    if (currentHead) {
      currentHead.setPreviousNode(newHead);
      newHead.setNextNode(currentHead);
    }
    this.head = newHead;
    if (!this.tail) {
      this.tail = newHead;
    }
  }
 
  addToTail(data) {
    const newTail = new Node(data);
    const currentTail = this.tail;
    if (currentTail) {
      currentTail.setNextNode(newTail);
      newTail.setPreviousNode(currentTail);
    }
    this.tail = newTail;
    if (this.head) {
      this.head.setPreviousNode(null);
    }
  }
 
  removeHead() {
    // current head is the head to be removed
    const removedHead = this.head;
    // if no current head, nothing to remove
    if (!removedHead) {
      return;
    }
    this.head = removedHead.getNextNode();
    if (this.head) {
      // head of list has no prev node
      this.head.setPreviousNode(null);
    }
    // if removedHead is also the tail
    // means only 1 element in the list
    if (removedHead === this.tail) {
      this.removeTail();
    }
    return removedHead.data;
  }
 
  removeTail() {
    // current tail is the tail to be removed
    const removedTail = this.tail;
    if (!removedTail) {
      return;
    }
    //update the list’s tail = current tail’s previous node
    this.tail = removedTail.getPreviousNode();
    // if there is still tail, meaning > 1 elemnet in list
    if (this.tail) {
      // update the next node to null
      this.tail.setNextNode(null);
    }
    // if there is only 1 element in the list
    if (removedTail === this.head) {
      this.removeHead();
    }
    return removedTail.data;
  }
 
  removeByData(data) {
    let nodeToRemove;
    let currentNode = this.head;
    // iterate to find the nodeToRemove
    while (currentNode !== null) {
      if (currentNode.data === data) {
        nodeToRemove = currentNode;
        break;
      }
      currentNode = currentNode.getNextNode();
    }
    // if no such node, return null
    if (!nodeToRemove) {
      return null;
    }
    // 3 cases of removing
    // if the node is the head, just call removeHead method
    if (nodeToRemove === this.head) {
      this.removeHead();
    }
    // if the node is the tail, just call removeTail method
    else if (nodeToRemove === this.tail) {
      this.removeTail();
    }
    // if node is neither head or tail
    // To remove it, need to reset the pointers for the nodes around it
    else {
      const nextNode = nodeToRemove.getNextNode();
      const previousNode = nodeToRemove.getPreviousNode();
      // make nextNode & previousNode point to each other
      nextNode.setPreviousNode(previousNode);
      previousNode.setNextNode(nextNode);
    }
    return nodeToRemove;
  }
 
  printList() {
    let currentNode = this.head;
    let output = '<head> ';
    while (currentNode !== null) {
      output += currentNode.data + ' ';
      currentNode = currentNode.getNextNode();
    }
    output += '<tail>';
    console.log(output);
  }
}
 
module.exports = DoublyLinkedList;

Test the DoublyLinkedList with

Test the DoublyLinkedList
// subway.js
const subway = new DoublyLinkedList();
 
subway.addToHead('TimesSquare');
subway.addToHead('GrandCentral');
subway.addToHead('CentralPark');
subway.printList();
 
subway.addToTail('PennStation');
subway.addToTail('WallStreet');
subway.addToTail('BrooklynBridge');
subway.printList();
 
subway.removeHead();
subway.removeTail();
subway.printList();
 
subway.removeByData('TimesSquare');
subway.printList();

Queues

Stacks

Hash Maps