Linked List

LinkedList.js

// https://www.geeksforgeeks.org/linked-list-set-1-introduction/
class Node {
  constructor(val, next) {
    this.val = val;
    this.next = next;
  }
}

function printList(list) {
  // O(N)
  const arr = [];
  let n = list;
  while(n) {
    arr.push(n.val);
    n = n.next;
  }
  return arr;
}

class LinkedList {
  constructor(head) {
    this.head = head;
  }
  // https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/
  push(elm) {
    // O(1)
    let newNode = new Node(elm);
    newNode.next = this.head;
    this.head = newNode;
  }
  insertAfter(node, elm) {
    // O(1)
    if (!node) {
      return;
    }
    let newNode = new Node(elm);
    newNode.next = node.next;
    node.next = newNode;
  }
  append(elm) {
    // O(n)
    let newNode = new Node(elm);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let last = this.head;
    while (last.next) {
      last = last.next;
    }
    last.next = newNode;
  }
  // https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/
  deleteNode(node, key) {
    // O(n)
    if (!node) {
      return;
    }
    let tmp = this.head;
    // When you don't need to update the pointer
    if (tmp.val === key) {
      this.head = tmp.next;
      return;
    }
    // When you need to update the pointer
    let prev = tmp;
    // Look up the key
    while (tmp && tmp.val !== key) {
      prev = tmp;
      tmp = tmp.next;
    }
    // Can't find the key
    if (!tmp) return;
    // Re-link
    prev.next = tmp.next;
  }
  // https://www.geeksforgeeks.org/delete-a-linked-list-node-at-a-given-position/
  deleteNodeByPosition(node, position) {
    if (!node) {
      return;
    }
    let tmp = this.head;
    if (position === 0) {
      this.head = tmp.next;
    }
    let prev = tmp;
    let idx;
    for (idx = 0; idx < position; idx++) {
      prev = tmp;
      tmp = tmp ? tmp.next : null;
    }
    if (tmp) {
      prev.next = tmp.next;
    }
  }
  // https://www.geeksforgeeks.org/find-length-of-a-linked-list-iterative-and-recursive/
  getCount(node) {
    let count = 0;
    let tmp = node;
    while (tmp) {
      tmp = tmp.next;
      count++;
    }
    return count;
  }
  getCountRec(node) {
    return (!node) ? 0 : 1 + this.getCountRec(node.next);
  }
  // https://www.geeksforgeeks.org/search-an-element-in-a-linked-list-iterative-and-recursive/
  search(node, key) {
    let tmp = node;
    while (tmp) {
      if (tmp.val === key) return tmp;
      tmp = tmp.next;
    }
    return false;
  }
  searchRec(node, key) {
    return (!node) ? false : node.val === key ? node : this.searchRec(node.next, key);
  }
  // https://www.geeksforgeeks.org/swap-nodes-in-a-linked-list-without-swapping-data/
  swapNodes(key1, key2) {
    let tmp = this.head;
    let prev;
    let prev1;
    let prev2;
    while (tmp) {
      if (tmp.val === key1) prev1 = prev;
      if (tmp.val === key2) prev2 = prev;
      prev = tmp;
      tmp = tmp.next;
    }
    if (prev1 && !prev2) {
      prev1.next.val = key2;
      this.head.val = key1;
    }
    else if (!prev1 && prev2) {
      this.head.val = key2;
      prev2.next.val = key1;
    }
    else if (prev1 && prev2) {
      prev1.next.val = key2;
      prev2.next.val = key1;
    }
  }
  // https://www.geeksforgeeks.org/pairwise-swap-adjacent-nodes-of-a-linked-list-by-changing-pointers-set-2/
  pairWiseSwap() {
    let tmp = this.head;
    while (tmp) {
      if (tmp && tmp.next) {
        let val = tmp.val;
        tmp.val = tmp.next.val;
        tmp.next.val = val;
      }
      tmp = tmp.next && tmp.next.next ? tmp.next.next : null;
    }
  }
}

const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);

const linkedList = new LinkedList(head);
console.log('init', printList(linkedList.head).join(',') === '1,2,3');
linkedList.push(4);
console.log('push', printList(linkedList.head).join(',') === '4,1,2,3');
linkedList.insertAfter(linkedList.head.next, 0);
console.log('insertAfter', printList(linkedList.head).join(',') === '4,1,0,2,3');
linkedList.append(5);
console.log('append', printList(linkedList.head).join(',') === '4,1,0,2,3,5');
// https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/
linkedList.deleteNode(linkedList.head, 4);
console.log('deleteNode', printList(linkedList.head).join(',') === '1,0,2,3,5');
linkedList.deleteNode(linkedList.head, 3);
console.log('deleteNode', printList(linkedList.head).join(',') === '1,0,2,5');
// https://www.geeksforgeeks.org/delete-a-linked-list-node-at-a-given-position/
linkedList.deleteNodeByPosition(linkedList.head, 1);
console.log('deleteNodeByPosition', printList(linkedList.head).join(',') === '1,2,5');
// https://www.geeksforgeeks.org/find-length-of-a-linked-list-iterative-and-recursive/
console.log('getCount', linkedList.getCount(linkedList.head) === 3 && linkedList.getCount(linkedList.head.next) === 2)
console.log('getCountRec', linkedList.getCountRec(linkedList.head) === 3 && linkedList.getCountRec(linkedList.head.next) === 2)
// https://www.geeksforgeeks.org/search-an-element-in-a-linked-list-iterative-and-recursive/
console.log('search', linkedList.search(linkedList.head, 2).val === 2);
console.log('search', linkedList.search(linkedList.head, 9) === false);
console.log('searchRec', linkedList.searchRec(linkedList.head, 2).val === 2);
console.log('searchRec', linkedList.searchRec(linkedList.head, 9) === false);

// https://www.geeksforgeeks.org/swap-nodes-in-a-linked-list-without-swapping-data/
const swapEx1 = new LinkedList();
[10,15,12,13,20,14].map((val) => swapEx1.append(val));
console.log('swap1:pre',printList(swapEx1.head).join(',') === '10,15,12,13,20,14');
swapEx1.swapNodes(12,20);
console.log('swap1:post',printList(swapEx1.head).join(',') === '10,15,20,13,12,14');

const swapEx2 = new LinkedList();
[10,15,12,13,20,14].map((val) => swapEx2.append(val));
console.log('swap2:pre',printList(swapEx2.head).join(',') === '10,15,12,13,20,14');
swapEx2.swapNodes(10,20);
console.log('swap2:post',printList(swapEx2.head).join(',') === '20,15,12,13,10,14');

const swapEx3 = new LinkedList();
[10,15,12,13,20,14].map((val) => swapEx3.append(val));
console.log('swap3:pre',printList(swapEx3.head).join(',') === '10,15,12,13,20,14');
swapEx3.swapNodes(12,13);
console.log('swap3:post',printList(swapEx3.head).join(',') === '10,15,13,12,20,14');

// https://www.geeksforgeeks.org/pairwise-swap-adjacent-nodes-of-a-linked-list-by-changing-pointers-set-2/
const pairSwapEx1 = new LinkedList();
[1,2,3,4,5,6,7].map((val) => pairSwapEx1.append(val));
console.log('pairSwap1:pre',printList(pairSwapEx1.head).join(',') === '1,2,3,4,5,6,7');
pairSwapEx1.pairWiseSwap();
console.log('pairSwap1:post',printList(pairSwapEx1.head).join(',') === '2,1,4,3,6,5,7');

const pairSwapEx2 = new LinkedList();
[1,2,3,4,5,6].map((val) => pairSwapEx2.append(val));
console.log('pairSwap1:pre',printList(pairSwapEx2.head).join(',') === '1,2,3,4,5,6');
pairSwapEx2.pairWiseSwap();
console.log('pairSwap1:post',printList(pairSwapEx2.head).join(',') === '2,1,4,3,6,5');