卡拉筆記

 
使用 javascript
  

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

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

  /** 
   * @param {number} index
   * @return {number}
   */
  get = function(index) {
    let res = this.getNode(index);
    if (res)
      return res.val;
    else
      return -1;
  };

  getNode = function(index) {
    if (index < 0 || index > this.length - 1) return null;
  
    let currNode = this.head;
    let currIndex = 0;
    while (currIndex < index) {
      currIndex += 1;
      currNode = currNode.next;
    }
    return currNode;
  }

  /** 
   * @param {number} val
   * @return {void}
   */
  addAtHead = function(val) {
    let newNode = new Node(val);
    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      let orignal = this.head;
      this.head = newNode;
      this.head.next = orignal;
    }
    this.length += 1;
    return;
  };

  /** 
   * @param {number} val
   * @return {void}
   */
  addAtTail = function(val) {
    let newNode = new Node(val);
    if (!this.length) {
      this.addAtHead(val)
    } else {
      this.tail.next = newNode;
      this.tail= newNode;
    }
    this.length += 1;
    return;
  };

  /** 
   * @param {number} index 
   * @param {number} val
   * @return {void}
   */
  addAtIndex = function(index, val) {
    let newNode = new Node(val);
    if (index < 0 || index > this.length) return -1;
    if (index === 0) {
      this.addAtHead(val);
    } else if (index === this.length) {
      this.addAtTail(val);
    } else {
      let prevNode = this.getNode(index - 1);
      let nextNode = prevNode.next;
      prevNode.next = newNode;
      newNode.next = nextNode;
      this.length += 1;
    }
    return;
  };

  /** 
   * @param {number} index
   * @return {void}
   */
  deleteAtIndex = function(index) {
    if (index < 0 || index >= this.length) return;
    if (index === 0) {
      this.head = this.head.next;
    } else {
      let preNode = this.getNode(index - 1);
      let delNode = preNode.next;
      let nextNode = delNode.next;
      preNode.next = nextNode;
      if (!nextNode) {
        this.tail = preNode;
      }
    }
    this.length -= 1;

    if (this.length <= 1) {
      this.tail = this.head;
    }
    return;
  };

  print = function() {
    let currNode = this.head;
    for (let i = 0; i < this.length; i++) {
      if (!currNode) break;
      console.log(currNode.val);
      currNode = currNode.next;
    }
    console.log(`this.head = ${this.head ? this.head.val : 'null'}`);
    console.log(`this.tail = ${this.tail ? this.tail.val : 'null'}`);
  }
}

/** 
 * Your MyLinkedList object will be instantiated and called as such:
  var obj = new MyLinkedList()
  var param_1 = obj.get(1)
  obj.addAtHead('addAtHead')
  obj.addAtTail('addAtTail')
  obj.print()

  obj.addAtIndex('1', 'addAtIndex1')
  obj.addAtIndex(9, 'addAtIndexAt9')
  obj.addAtIndex(2, 'addAtIndex2')
  obj.print()
  obj.deleteAtIndex(2)
  obj.print()

  obj.deleteAtIndex(1)
  obj.print()
  obj.deleteAtIndex(1)
  obj.print()
  obj.deleteAtIndex(0)
  obj.print()

  obj.addAtIndex(0, '0')
  obj.print()
  obj.addAtIndex(0, 'insert at 0')
  obj.print()
  obj.addAtIndex(1, 'insert at 1')
  obj.print()
  obj.addAtIndex(2, 'insert tail')
  obj.print()
 */

 
參考文章
JavaScript 學演算法（五）- 鏈結串列 Linked list