Linked List

Approach

We can use size property to easily and efficiently delete at head and tail.

Complexity

• Time complexity:
  • get(index): Worst Time complexity $$O(n)$$
  • addAtHead(val): $O(1)$
  • addAtTail(val): $O(1)$
  • addAtIndex(index, val): Worst Time complexity $O(n)$ but for special cases where we want to read at tail, it's $O(1)$
  • deleteAtIndex(index, val): Worst Time complexity $O(n)$ but for special cases where we want to delete at tail, it's $O(1)$

Code

class Node {
    constructor(value) {
        this.value = value;
        this.pre = null;
        this.post = null;
    }
}

var MyLinkedList = function() {
    this.head = null;
    this.tail = null;
    this.size = 0;
};

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
    let node = this.getNodeAtIndex(index);

    if (node == null) {
        return -1;
    }

    return node.value;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    let node = new Node(val);

    if (this.tail == null) {
        this.tail = node;
    }
    
    if (this.head != null) {
        this.head.pre = node;
        node.post = this.head;
    }
    this.head = node;
    this.size++;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    let node = new Node(val);

    if (this.head == null) {
        this.head = node;
    }

    if (this.tail != null) {
        node.pre = this.tail;
        this.tail.post = node;
    }

    this.tail = node;
    this.size++;
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.getNodeAtIndex = function(index) {
    
    let node = this.head;
    for (let i = 0; i < index && node != null; i++) {
        node = node.post;
    }
    return node;
}

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {

    if (index > this.size) {
        return;
    }

    if (index == 0) {
        return this.addAtHead(val);
    }
    if (index == this.size) {
        return this.addAtTail(val);
    }

    let node = this.getNodeAtIndex(index);

    let newNode = new Node(val);

    newNode.post = node;
    newNode.pre = node.pre;

    node.pre.post = newNode;
    node.pre = newNode;
    this.size++;
};


MyLinkedList.prototype.deleteAtHead = function() {
    if (this.head != null) {
        // this.head.pre = null;
        this.head = this.head.post;
        this.size--;
    }

    if (this.size == 0) {
        this.tail = null;
    }
}

MyLinkedList.prototype.deleteAtTail = function() {
    if (this.tail != null) {
        this.tail.pre.post = null;
        this.tail = this.tail.pre;
        this.size--;
    }

    if (this.size == 0) {
        this.head = null;
    }
}

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {

    if (index == 0) {
        this.deleteAtHead();
        return;
    }

    if (index == this.size - 1) {
        this.deleteAtTail();
        return;
    }

    let node = this.getNodeAtIndex(index);

    if (node == null) {
        return;
    }

    this.size--;

    if (this.head == node) {
        this.head = null;
    }

    if (this.tail == node) {
        this.tail = null;
    }

    if (node.pre != null) {
        node.pre.post = node.post;
    }

    if (node.post != null) {
        node.post.pre = node.pre;
    }
};


MyLinkedList.prototype.print = function() {
    let node = this.head;
    let list = ['List:'];
    for ( ; node != null; ) {
        list.push(node.value)
        node = node.post;
    }

    console.log(list.join(' '))
}


let list = new MyLinkedList();

list.addAtHead(1)
list.print()
list.addAtTail(3)
list.print()
list.addAtIndex(1, 2)
list.print()
console.log(list.get(1))
list.print()
list.deleteAtIndex(0)
list.print()
console.log(list.get(0))
list.print()