[LeetCode] 707. Design Linked List, Medium

1. 문제

• 단일 연결 리스트 혹은 이중 연결 리스트를 만들어라. 조건은 다음과 같다.
  • 생성자로 객체를 생성하며, 매개변수는 받지 않는다.
  • get 함수는 index를 매개변수로 받고 해당 인덱스의 value롤 반환하고, 없으면 -1을 반환하라.
  • addAtHead 함수는 새로운 노드를 연결 리스트의 맨 처음에 추가하라.
  • addAtTail 함수는 새로운 노드를 연결 리스트의 맨 마지막에 추가하라.
  • addAtIndex 함수는 주어진 인덱스에 새로운 노드를 추가하되, 만약 인덱스가 전체 길이와 같을 때도 추가하고 전체 길이보다 큰 경우는 무시한다.
  • deleteAtIndex 함수는 해당 index의 노드를 제거하라.

2. 해결

class Node { // 노드 클래스
    value: number;
    next: Node | null;
    constructor(value: number) {
        this.value = value;
        this.next = null;
    }
}

class MyLinkedList { // 단일 연결 리스트.
    head: Node | null;
    size: number;

    constructor() { // 생성자.
        this.head = null;
        this.size = 0;
    }

    get(index: number): number { // get 함수.
        let pointer = this.head; 
        let idx = 0;

        while (pointer) { // pointer가 null이 아닐 때 까지 반복.
            if (idx === index) return pointer.value; // index가 일치하는 Node의 value 반환.
            pointer = pointer.next; // 다음 노드로 갱신.
            idx++; // 현재 인덱스 갱신.
        }

        return -1; // 없으면 -1 반환.
    }

    addAtHead(val: number): void { // addAtHead 함수.
        const newNode = new Node(val); // 새로운 노드.
        newNode.next = this.head; // 현재 head를 새로운 노드의 next로 지정.
        this.head = newNode; // 새로운 노드를 head로 지정.
        this.size++; // size 증가.
    }

    addAtTail(val: number): void { // addAtTail 함수.
        const newNode = new Node(val); // 새로운 노드.

        if (!this.head) { // 비어 있으면, head로 지정.
            this.head = newNode;
        } else { // 비어 있지 않으면,
            let pointer = this.head;
            while (pointer.next) { // node를 탐색해서 next가 null인 노드를 찾고.
                pointer = pointer.next;
            }
            pointer.next = newNode; // 해당 노드의 next에 새로운 노드를 지정.
        }

        this.size++; // size 증가.
    }

    addAtIndex(index: number, val: number): void { // addAtIndex 함수.
        if (index > this.size) return; // index가 size보다 크면 무시.

        if (index === 0) { // index가 0이면 addAtHead 함수 호출.
            this.addAtHead(val);
            return;
        }

        const newNode = new Node(val); // 새로운 노드 생성.
        let pointer = this.head;
        let idx = 0;

        while (pointer && idx < index - 1) { // 변경 위치 노드 탐색.
            pointer = pointer.next;
            idx++;
        }

        if (pointer) { // 만약 변경 위치에 노드가 존재하면, 
            newNode.next = pointer.next; // 해당 노드의 next를 새로운 노드의 next로 지정.
            pointer.next = newNode; // 해당 노드의 next를 새로운 노드로 지정.
            this.size++; // size 증가.
        }
    }

    deleteAtIndex(index: number): void { // deleteAtIndex 함수.
        if (index < 0 || index >= this.size) return; // 범위를 벗어나는 index는 무시.

        if (index === 0) { // 0번 인덱스를 지우는 경우,
            this.head = this.head!.next; // 현재 head의 next를 head로 지정.
        } else { // 그 외.
            let pointer = this.head;
            let idx = 0;

            while (pointer && idx < index - 1) { // 삭제 위치 노드 탐색.
                pointer = pointer.next;
                idx++;
            }

            if (pointer && pointer.next) { // 삭제 위치 노드의 next 갱신.
                pointer.next = pointer.next.next;
            }
        }

        this.size--; // size 감소.
    }
}

• 일반적인 연결 리스트 구현이 아니라 몇몇 조건들이 있어서 애좀 먹었다. 침착하게 풀면 괜찮을 거 같다.