Links

ΜΆ
Adam I. Gerard
TBD
TBD
TBD

Linked Lists

Basic operations for Linked Lists: appending a Node, checking cycles, deleting Nodes by value, prepending a Node, and inserting a Node.

  • Difficulty: Easy
  • Kind: Data Structures
  • Platform: Personal
  • Solved: N/A
  • Time Complexity: O(N)
  • Space Complexity: O(N)
  • Answer Rank: Top N/A

Insights

The main insight I think for working with LinkedLists involves traversal - iterating through the Linked List. It's often easier to work with arrays than Linked Lists directly.
// ES5 compliant.
window.onload = function() {

  function append(head, val) {
    if (head == null) head = new LinkedList(val, null);
    else {
      var current = head;
      while (current.next != null) {
        current = current.next;
      }
      current.next = new LinkedList(val, null);
    }
    return head;
  };

  function prepend(head, val) {
    if (head == null) head = new LinkedList(val, null);
    else {
      var current = head;
      head = new LinkedList(val, current);
    }
    return head;
  };

  /** Remove by value not by index. */
  function del(head, val) {
    let current = head, arr = []
    
    while (current != null) {
        if (current.val != val) arr.push(current.val)
        current = current.next
    }
  
    return buildList(arr);
  };

  /** - Starting At 1 */
  function insrt(head, val, position) {
    if (head == null) head = new LinkedList(val, null);
    else {
      var current = head;
      var last = head;
      for (var i = 1; i < position; i++) {
        last = current;
        current = current.next;
      }
      current = new LinkedList(val, current);
      last.next = current;
    }
    return head;
  };

  function checkCycle(head) {
    if (head == null) return false;
    else {
      var alreadyIn = [];
      var current = head;
      while (current != null) {
        if (alreadyIn.indexOf(current.val) == -1) alreadyIn.push(current.val);
        else return true;
        current = current.next;
      }
      return false;
    }
  };
  
  // Reinitialize each time
  function init() { 
    return new LinkedList(1, new LinkedList(2, new LinkedList(3, new LinkedList(4, null))));
  }

  function cycle() {
    return new LinkedList(1, new LinkedList(2, new LinkedList(1, null)));
  }

  var testA = init();
  var expectationA = new LinkedList(1, new LinkedList(2, new LinkedList(3, new LinkedList(4, new LinkedList(5, null)))));
  var resultA = append(testA, 5);
  declare_result(traverseList(testA) + " append 5", traverseList(expectationA), traverseList(resultA), array_equals(traverseList(expectationA), traverseList(resultA)));

  var testB = init();
  var resultB = checkCycle(testB)
  declare_result(traverseList(testB) + " check is cycle", false, resultB, resultB === false);

  var testC = cycle();
  var resultC = checkCycle(testC)
  declare_result(traverseList(testC) + " check is cycle", true, resultC, resultC === true);

  var testD = init();
  var expectationD = new LinkedList(5, new LinkedList(1, new LinkedList(2, new LinkedList(3, new LinkedList(4, null)))));
  var resultD = prepend(testD, 5)
  declare_result(traverseList(testD) + " prepend 5", traverseList(expectationD), traverseList(resultD), array_equals(traverseList(expectationD), traverseList(resultD)));

  var testE = null;
  var resultE = del(testE, 3);
  declare_result("null delete 3", null, null, null === resultE);

  var testF = init();
  var expectationF = new LinkedList(1, new LinkedList(2, new LinkedList(4, null)));
  var resultF = del(testF, 3)
  declare_result(traverseList(testF) + " delete 3", traverseList(expectationF), traverseList(resultF), array_equals(traverseList(expectationF), traverseList(resultF)));

  var testG = init();
  var expectationG =new LinkedList(1, new LinkedList(2, new LinkedList(3, null)));
  var resultG = del(testG, 4)
  declare_result(traverseList(testG) + " delete 4", traverseList(expectationG), traverseList(resultG), array_equals(traverseList(expectationG), traverseList(resultG)));

  var testH = init();
  var expectationH = new LinkedList(1, new LinkedList(5, new LinkedList(2, new LinkedList(3, new LinkedList(4, null)))));
  var resultH = insrt(init(), 5, 2)
  declare_result(traverseList(testH) + " insert 5 at 2", traverseList(expectationH), traverseList(resultH), array_equals(traverseList(expectationH), traverseList(resultH)));
};

Test Cases

      Links