Design Linked List

문제:

연결 리스트 구현하기

 

Example 1 :

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);                 // return 2
myLinkedList.deleteAtIndex(1);   // now the linked list is 1->3
myLinkedList.get(1);                // return 3

 

제약 조건 :

• 0 <= index, val <= 1000
• Please do not use the built-in LinkedList library.
• At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

 

나의 코드

let singleLinkNode = function(value){
    this.value = value;
    this.next = null;
};

let MyLinkedList = function(head = null) {
    this.head = head;
    this.length = 0;
};

MyLinkedList.prototype.getNode = function(index){
    if(index < 0 || index > this.length - 1) return null;
    let current = this.head;
    let count = 0;
    while(current && count < index){
        current = current.next;
        count++;
    }
    return current;
}

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
    let current = this.getNode(index);
    return current === null ? -1 : current.value;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    let newHead = new singleLinkNode(val);
    newHead.next = this.head;
    this.head = newHead;
    this.length++;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    let current = this.head;
    if(current === null){
        this.head = new singleLinkNode(val);
        current = new singleLinkNode(val);
        this.length++;
        return;
    } 
    while(current && current.next){
        current = current.next;
    }
    current.next = new singleLinkNode(val);
    this.length++;
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    if(index == 0){
        this.addAtHead(val);
    }else if(index == this.length){
        this.addAtTail(val);
    }else if(index < this.length && index > 0){
        let current = this.getNode(index);
        let prev = this.getNode(index - 1);
        let node = new singleLinkNode(val);
        prev.next = node;
        node.next = current;
        this.length++;
    }
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    let current = this.getNode(index);
    if(current === null) return;
    let prev = this.getNode(index - 1);
    let next = current.next;
    if(prev !== null){
        prev.next = next;
    }else{
        this.head = next;
    }
    this.length--;
};

/** 
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

 

단순히 연결 리스트를 구현하는 문제여서 큰 어려움은 없었다.

회사에서 자료구조를 직접 구현할 일은 없지만, 알고리즘 문제를 풀 때 어느 정도 구현할 수 있어야 한다.

중요한 핵심 개념을 완전히 이해하고 넘어가자.