Data Structures

Jan 29, 2018 JS Front-End

esther

From data structure to algorithm…?
Still working on the tree removing part T^T

References

6 Data Structures in 6 Minutes
How do you use Queue, Stack, List, Map, and Set in Java?
用 JavaScript 學習資料結構和演算法系列

Array

@tooto1985

Stack

Last In First Out (LIFO)

tutorialspoint

function Stack() {
  var items = [];
  this.push = function(element) {
    items.push(element);
  }
  this.pop = function() {
    return items.pop();
  }
  this.peek = function() {
    return items[items.length - 1];
  }
  this.isEmpty = function() {
    return items.length === 0;
  }
  this.clear = function() {
    items = [];
  }
  this.size = function() {
    return items.length;
  }
  this.print = function() {
    console.log(items.toString());
  }
}

var stack = new Stack();
stack.push('Book I');
stack.push('Book II');
stack.push('Book III');
stack.push('Book IV');
stack.pop();                   // remove BookIV

console.log(stack.size());     // 3
console.log(stack.peek());     // Book III
stack.clear();                 // Clear stack
console.log(stack.isEmpty());  // true

Queue

First In First Out (FIFO): In Rear, Out Front

tutorialspoint

function Queue() {
  let items = [];
  this.enqueue = function(element) {
    items.push(element);
  };
  this.dequeue = function() {
    return items.shift();
  };
  this.front = function() {
    return items[0];
  };
  this.isEmpty = function() {
    return items.length === 0;
  };
  this.clear = function() {
    items = [];
  };
  this.size = function() {
    return items.length;
  };
  this.print = function() {
    console.log(items.toString());
  }
}

const queue = new Queue();

console.log(queue.isEmpty());     // true

queue.enqueue('Car 1');
queue.enqueue('Car 2');
queue.enqueue('Car 3');
queue.enqueue('Car 4');

console.log(queue.front());       // Car 1
console.log(queue.size());        // 4
queue.print();                    // Car 1,Car 2,Car 3,Car 4
queue.dequeue();                  // remove Car 1
console.log(queue.front());       // Car 2
console.log(queue.size());        // 3
queue.print();                    // Car 2,Car 3,Car 4

Priority Queue

Set priority to each item in array.

netmatze

function PriorityQueue() {
  let items = [];
  function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
  }
  this.enqueue = function(element, priority) {
    const queueElement = new QueueElement(element, priority);
    if(this.isEmpty()) {
      items.push(queueElement);
    } else {
      let added = false;
      for(let i = 0; i < items.length; i++) {
        if(queueElement.priority < items[i].priority) {
          items.splice(i, 0, queueElement);
                    added = true;
                    break;
        }
      }
      if(!added) {
        items.push(queueElement);
      }
    }
  }
  this.dequeue = function() {
    return items.shift();
  };
  this.front = function() {
    return items[0];
  };
  this.isEmpty = function() {
    return items.length === 0;
  };
  this.clear = function() {
    items = [];
  };
  this.size = function() {
    return items.length;
  };
  this.print = function() {
    console.log(JSON.stringify(items));
  }
}

const priorityQueue = new PriorityQueue();

console.log(priorityQueue.isEmpty());      // true

priorityQueue.enqueue('Tom', 2);
priorityQueue.enqueue('Jane', 1);
priorityQueue.enqueue('Ann', 4);
priorityQueue.enqueue('Tina', 3);

console.log(priorityQueue.front());        // {element: "Jane", priority: 1}
console.log(priorityQueue.size());         // 4
priorityQueue.print();                     // [{element: "Jane", priority: 1}, {element: "Tom", priority: 2}, ...]
priorityQueue.dequeue();                   // remove Jane
console.log(priorityQueue.front());        // {element: "Tom", priority: 2}
console.log(priorityQueue.size());         // 3
priorityQueue.print();                     // [{element: "Tom", priority: 2}, {element: "Tina", priority: 3}, ...]

Linked List

A sequence of data structures which are connected together via links.

Link − Each Link of a linked list can store a data called an element.
Next − Each Link of a linked list contain a link to next link called Next.
LinkedList − A LinkedList contains the connection link to the first Link called First.

tutorialspoint

function LinkedList() {
  const Node = function(element) {
    this.element = element;
    this.next = null;
  };

  let length = 0;            // 存放 LinkedList 長度
  let head = null;           // 第一個節點的指標

  this.getHead = function() {
    return head;
  }

  this.append = function(element) {
    const node = new Node(element)
    let current;

    if(head === null) {
      head = node;
    } else {
      current = head;
      while(current.next) {
          current = current.next;
      }
      current.next = node;
    }
    length++;
  };

  this.insert = function(position, element) {
    if(position >= 0 && position <= length) {
      let node = new Node(element);
      let current = head;
      let previous;
      let index = 0;

      if(position === 0) {
        node.next = current;
        head = node;
      } else {
        while(index++ < position) {
            previous = current;
            current = current.next;
        }
        node.next = current;
        previous.next = node;
      }
      length++;
      return true;
    } else {
      return false;
    }
  };

  this.remove = function(element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  };

  this.removeAt = function(position) {
    if(position > -1 && position < length) {
      let current = head;
      let previous;
      let index = 0;
      if(position === 0) {
        head = current.next;
      } else {
        while(index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      length--;
      return current.element;
    } else {
      return null;
    }
  };

  this.indexOf = function(element) {
    var current = head;
    var index = -1;

    while(current) {
      if(element === current.element) {
          return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  };

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

  this.size = function() {
      return length;
  };

  this.toString = function() {
    let current = head;
    let string = '';
    while(current) {
      string += current.element;
      current = current.next;
    }
    return string;
  };

  this.print = function() {
    console.log(this.toString());
  };
};

const linkdeList = new LinkedList();

console.log(linkdeList.isEmpty());     // true

linkedList.append('A');
linkedList.append('B');
linkedList.append('C');
linkedList.append('D');
linkedList.print();                    // ABCD
linkedList.insert(2, 'X');             // add X after node2(B)
linkedList.print();                    // ABbCD
linkedList.remove('B');                // remove B
console.log(linkedList.size());        // 4
linkedList.removeAt(0);                // remove node0 (A)
linkedList.print();                    // XCD
console.log(linkedList.indexOf('X'));  // -1
console.log(linkedList.indexOf('D'));  // 1
console.log(linkedList.getHead());     // { element: "X", next: { element: "C", next: { ... } } }

Types

Singly Linked List
Doubly Linked List
Circular Linked List

Set

wikistack

function Set() {
  var items = {};

  this.add = function(value) {
    if(!this.has(value)) {
      items[value] = value;
      return true;
    }
    return false;
  };

  this.remove = function(value) {
    if(this.has(value)) {
      delete items[value];
      return true;
    }
    return false;
  };

  this.has = function(value) {
    return items.hasOwnProperty(value);
  };

  this.clear = function() {
    items = {};
  };

  this.size = function() {
    let count = 0;
    for(let key in items) {
      ++count;
    }
    return count;
  };

  this.value = function() {
    let keys = [];
    for(let key in items) {
      keys.push(key);
    }
    return keys;
  };

  this.union = function(otherSet) {
    let unionSet = new Set();
    let value = this.value();
    for(var i = 0; i < value.length; i++) {
      unionSet.add(value[i]);
    }
    value = otherSet.value();
    for(var j = 0; j < value.length; j++) {
      unionSet.add(value[j]);
    }
    return unionSet;
  };

  this.intersection = function(otherSet) {
  let intersectionSet = new Set();
  let value = this.value();
  for(var i = 0; i < value.length; i++) {
    if(otherSet.has(value[i])) {
      intersectionSet.add(value[i]);
    }
  }
  return intersectionSet;
  };

  this.difference = function(otherSet) {
    let differenceSet = new Set();
    let value = this.value();
    for(var i = 0; i < value.length; i++) {
      if(!otherSet.has(value[i])) {
        differenceSet.add(value[i]);
      }
    }
    return differenceSet;
  }

  this.isSub = function(otherSet) {
    if(this.size() > otherSet.size()) {
      return false;
    } else {
      let value = this.value();
      for(var i = 0; i < value.length; i++) {
        if(!otherSet.has(value[i])) {
          return false;
        }
      }
      return true;
    }
  };
}

const set = new Set();

set.add(12);                                         // add 12
console.log(set.value());                            // ['12']
console.log(set.has(12));                            // true
console.log(set.size());                             // 1
set.add(15);                                         // add 15
set.remove(12);                                      // remove 12
console.log(set.has(12));                            // false
console.log(set.value());                            // ['15']

let setA = new Set();
setA.add('A');
setA.add('B');
setA.add('C');
setA.add('D');
console.log(setA.value());                           // ["A", "B", "C", "D"]

let setB = new Set();
setB.add('A');
setB.add('C');
setB.add('E');
setB.add('F');
console.log(setB.value());                           // ["A", "C", "E", "F"]

let setC = new Set();
setC.add('A');
setC.add('B');

const unionSet = setA.union(setB);
console.log(unionSet.value());                       // ["A", "B", "C", "D", "E", "F"]

const intersectionSet = setA.intersection(setB);
console.log(intersectionSet.value());                // ["A", "C"]

const differenceSet = setA.difference(setB);
console.log(differenceSet.value());                  // ["A", "C"]

console.log(setB.isSub(setA));                       // false
console.log(setC.isSub(setA));                       // true

Tree

inorder: left -> root -> right (A -> B -> C)
preorder: root -> left -> right (B -> A -> C)
postorder: left -> right -> root (A -> C -> B)

medium

function BinarySearchTree() {
  const Node = function(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  };

  let root = null;

  this.insert = function(key) {
    let newNode = new Node(key);

    if(root === null) {
      root = newNode;
    } else {
      insertNode(root, newNode);
    }
  };
  const insertNode = function(node, newNode) {
    if(newNode.key < node.key) {
      if(node.left === null) {
        node.left = newNode;
      } else {
        insertNode(node.left, newNode);
      }
    } else {
      if(node.right === null) {
        node.right = newNode;
      } else {
        insertNode(node.right, newNode);
      }
    }
  };

  this.inOrderTraverse = function(callback) {
    inOrderTraverseNode(root, callback);
  };
  const inOrderTraverseNode = function(node, callback) {
    if(node !== null) {
      inOrderTraverseNode(node.left, callback);
      callback(node.key);
      inOrderTraverseNode(node.right, callback);
    }
  }

  this.preOrderTraverse = function(callback) {
    preOrderTraverseNode(root, callback);
  };
  const preOrderTraverseNode = function(node, callback) {
    if(node !== null) {
      callback(node.key);
      preOrderTraverseNode(node.left, callback);
      preOrderTraverseNode(node.right, callback);
    }
  };

  this.postOrderTraverse = function(callback) {
    postOrderTraverseNode(root, callback);
  };
  const postOrderTraverseNode = function(node, callback) {
    if(node !== null) {
      postOrderTraverseNode(node.left, callback);
      postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  };

  this.search = function(key) {
    return searchNode(root, key);
  };
  const searchNode = function(node, key) {
    if(node === null) {
      return false;
    }
    if (key === node.key) {
      return true;
    }
    if (key < node.key) {
      return searchNode(node.left, key);
    } else if (key > node.key) {
      return searchNode(node.right, key);
    }
  };

  this.min = function() {
    return minNode(root);
  };
  const minNode = function(node) {
    if(node) {
      while(node && node.left !== null) {
        node = node.left;
      }
      return node.key;
    }
    return null;
  };

  this.max = function() {
    return maxNode(root);
  };
  const maxNode = function(node) {
    if(node) {
      while(node && node.right !== null) {
        node = node.right;
      }
      return node.key;
    }
    return null;
  };

  this.remove = function(key) {
    if(this.search(key)) {
      return removeAt(root, key);
    } else {
      console.log('No such node.');
    }
  };
  const removeAt = function(node, key) {
    if(node === null) {
      node.left = removeAt(node.left, key);
      return node;
    } else if(key > node.key) {
      node.right = removeAt(node.right, key);
    } else {
      if(node.left === null) {
        node = node.right;
        return node;
      }
      if(node.left === null) {
        node = node.right;
        return node;
      } else if(node.right === null) {
        node = node.left;
        return node;
      }
      const aux = this.search(node.right);
      node.key = removeAt(node.right, aux.key);
      return node;
    }
  };
};

function printNode(value) {
  console.log(value);
}

let tree = new BinarySearchTree();
tree.insert(35);
tree.insert(22);
tree.insert(7);
tree.insert(2);
tree.insert(4);
tree.insert(5);
tree.insert(32);
tree.insert(40);
tree.inOrderTraverse(printNode);            // 2 4 5 7 22 32 35 40
tree.preOrderTraverse(printNode);           // 35 22 7 2 4 5 32 40
tree.postOrderTraverse(printNode);          // 5 4 2 7 32 22 40 35

// tree.remove(5);
// tree.inOrderTraverse(printNode);            // 2 4 5 7 22 32 35 40
tree.remove(1);
tree.inOrderTraverse(printNode);            // 2 4 5 7 22 32 35 40

console.log(tree.min());                    // 2
console.log(tree.max());                    // 40
console.log(tree.search(8));                // false
console.log(tree.search(22));               // true