Daily Leetcoding Challenge 707. Design Linked List

연결리스트(링크드리스트)를 직접 설계해 보는 문제다. 연결리스트 문제를 풀다 보면 Singly linked list가 자주 보이기 때문에 그다지 어려운 문제는 아니지만, Doubly linked list를 구현해 볼 수 있는 기회가 잘 없으니 이중 연결 리스트를 구현해 봤다. 구현해야 하는 메서드 중에 addAtTail 메서드가 있기 때문에 그 편이 시간을 감소시켜 줄 수 있기도 하다.

https://leetcode.com/problems/design-linked-list

Design Linked List - LeetCode

직관

보통의 Singly linked list는 head의 레퍼런스만 가지고 있어서 tail에 노드를 추가하는 경우 시간 복잡도가 O(n)으로 늘어나지만 tail 레퍼런스를 추가하면 O(1)에 추가가 가능하다. 그리고 head나 tail 값을 null로 초기화하는 경우 null체크를 해줘야하는 불편함이 있다. 그래서 dummy 노드를 추가하여 초기화하면 null 체크할 필요가 없어서 구현이 더 깔끔해진다.

접근법

addAtHead, addAtTail에 관한 접근법은 앞에서 어느정도 설명이 됐고, get, addAtIndex, deleteAtIndex 구현에 대해서 생각해 보자.

세 함수 모두 index까지 커서를 이동해야 한다. 내 구현은 index, size 값에 관계없이 head부터 커서를 움직였는데 거리에 따라 (doubly linked list에 한해서) head에서부터 커서를 옮길지, tail부터 커서를 옮길지 생각해 본다면 더 최적화할 수 있을 것이다.

커서는 dummy 포함 index번 이동 시키면 커서가 index-1 번째 노드를 가리킬 것이다. index-1 번째 노드의 next, index+1 번째 노드의 prev를 추가/삭제에 따라 적절히 바꿔주면 되겠다. get의 경우는 index에 있는 노드의 값을 리턴해야 하기 때문에 간단히 cur.next.val로 리턴한다.

복잡도

addAtHead, addAtTail 시간 복잡도 O(1), 공간 복잡도 O(1)

get, addAtIndex, deleteAtIndex 시간 복잡도 O(n), 공간 복잡도 O(1)

코드

class MyLinkedList {

    public static class Node {
        int val;
        Node prev;
        Node next;

        public Node(int val) {
            this.val = val;
            prev = null;
            next = null;
        }
    }

    Node head, tail;
    int size;

    public MyLinkedList() {
        head = new Node(0);
        tail = new Node(0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }
    
    public int get(int index) {
        if (index >= size) {
            return -1;
        }
        int i=0;
        Node cur = head;
        while(i < index) {
            cur = cur.next;
            i++;
        }
        return cur.next.val;
    }
    
    public void addAtHead(int val) {
        Node node = new Node(val);
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
        size++;
    }
    
    public void addAtTail(int val) {
        Node node = new Node(val);
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        int i=0;
        Node cur = head;
        while(i < index) {
            cur = cur.next;
            i++;
        }
        Node node = new Node(val);
        node.next = cur.next;
        node.prev = cur;
        cur.next.prev = node;
        cur.next = node;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if (index >= size) {
            return;
        }
        int i=0;
        Node cur = head;
        while(i < index) {
            cur = cur.next;
            i++;
        }
        cur.next = cur.next.next;
        cur.next.prev = cur;
        size--;
    }
}

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