[Java] LinkedList 구현 및 Array와 차이점

자료구조와 알고리즘을 학습하며 LinkedList를 자주 접하게 되었다. LinkedList는 배열과 비슷한 구조로 자주 비교되곤 하는데, 이번에 배열과 LinkedList가 어떤 부분에서 다른지 확인해보려 한다. 앞으로 설명할 예시 데이터 형태는 int이다.

Array / 배열

---

1. 배열은 인덱스를 사용하여 요소에 직접 접근이 가능하다. 이 말은 인덱스를 알고 있으면 상수 시간 O(1)에 해당 요소에 접근할 수 있다는 뜻이다.
2. 모든 요소는 메모리에 연속되어 저장된다. 첫 번째 요소의 인덱스(주소)를 알면 다른 요소에도 빠르게 접근이 가능하다.
3. 배열은 생성시 크기가 고정된다. 계속해서 값을 추가하는 등의 작업이 있다면 효율적이지 않고 더 큰 배열을 만들어야 한다.

장점

1. 조회 및 검색에 빠르다.

단점

1. 삽입과 삭제가 느리다.
   • 마지막 값을 삭제할 때는 문제가 없지만 처음이나 중간의 값을 삭제할 때 요소들이 한칸씩 이동해야 한다. (최악의 경우 O(n))
2. 배열의 크기 조정은 요소 복사로 비용이 많이 들 수 있다.

LinkedList / 리스트

---

1. LinkedList는 data값과 다음 노드의 주소를 담고있는 하나의 노드로 구성된다.
2. 연속된 메모리 주소가 아닌 단순히 다음 노드의 주소값을 갖고있기에 저장에 빠르다.
3. 인덱스를 사용하여 LinkedList의 요소로 직접 이동할 수 없다. 원하는 노드에 도달할 때까지 처음부터 목록을 순회해야 함. (인덱스로 요소에 접근할 때 최악의 경우 O(n))

장점

1. 삽입 및 삭제에 빠르며 리스트의 크기를 조정할 필요 없다.

단점

1. 주소값(포인터)을 저장하기에 더 많은 공간이 필요할 수 있으며 배열에 비해 특정 요소에 대한 조회 시간이 느리다. 포인터/참조의 추가 저장으로 인해 저장 공간에 더 많은 오버헤드가 발생합니다.

---

LinkedList가 갖는 다음 주소값이 무엇을 말하는지, 노드는 어떻게 저장되는지 직접 알아보기 위해 Java코드로 구현해보았다.

총 6가지 기능을 구현할 예정이며 아래와 같다.

1. 리스트의 처음에 요소를 저장하는 (addFirst)
2. 마지막에 저장(addLast)
3. 중간에 저장(add)
4. 저장된 모든 데이터를 확인하는 printAll
5. index로 값을 조회하는 get
6. index로 값을 삭제하는 remove

public class LinkedList {

    private Node head; // 가장 처음의 값을 저장하는 head
    private Node tail; // 가장 마지막 값을 저장하는 tail
    private int size; // list에 담긴 요소 갯수 파악

    static class Node {
        private int data; // 각 노드별 data값이 담긴 변수
        private Node next; // 각 노드별 다음 노드의 주소가 담긴 변수

        public Node(int data) { // 처음 노드 생성시 다음 노드의 주소는 null
            this.data = data;
            this.next = null;
        }
    }

    private void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;

        if(head.next == null) tail = head;
        size++;

        System.out.println("next = " + newNode.next + " data = " + newNode.data + " tail = " + tail);
        System.out.println("----first 끝");
    }

    private void addLast(int data) {
        if(size == 0) {
            addFirst(data);
        } else {
            Node newNode = new Node(data);
            tail.next = newNode;
            tail = newNode;
            size++;
        }
        System.out.println("----Last 끝");
    }

    public void add(int data, int index) {
        if(size == 0) {
            addFirst(data);
        } else if(size-1 == index) {
            addLast(data);
        } else {
            Node newNode = new Node(data);
            Node current = head;
            for(int i=0; i<index-1 ; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
            size++;
        }
        System.out.println("---- add 끝");
    }

    private void printAll() {
        Node current = head;
        while(current != null) {
            System.out.println("data = " + current.data);
            System.out.println("next = " + current.next);
            current = current.next;
        }
        System.out.println("size = " + size);
        System.out.println("---- printAll 끝");
    }

    private Node get(int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index out of bounds");
        if (size == 0) throw new IllegalStateException("List is empty");

        if (index == 0) {
            return head;
        } else if (index == size - 1) {
            return tail;
        } else {
            Node current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            System.out.println("---- get 끝");
            return current;
        }
    }

    public int remove(int index) {
        Node currentNode = null;

        if(index >= size || index < 0) {
            throw new IndexOutOfBoundsException("check Index" + index);
        } else if(index == 0) {
            currentNode = head;
            head = head.next;
        } else {
            Node prevNode = get(index-1);
            currentNode = prevNode.next;
            prevNode.next = currentNode.next;
        }
        size--;
        System.out.println("---- remove 끝");
        return currentNode.data;
    }
}

위의 remove 메서드에서 이전 노드를 get 메서드를 사용하여 가져오는데 노드를 또 다시 돌며 시간복잡도가 증가하는 것이 아닌가? 라는 의문이 있었다. 아래는 get메서드를 사용하지 않고 다른 코드를 작성한 것이다.


두 remove 메서드의 최종적인 시간복잡도는 O(n)으로 같을 것으로 예상되지만 get메서드를 불러오는 과정에서 한번 더 리스트를 탐색하는 시간은 줄 것이라 예상된다.

public int remove(int index) {
        Node currentNode = head;

        if(index >= size || index < 0) {
            throw new IndexOutOfBoundsException("check Index" + index);
        } else if(index == 0) {
            head = head.next;
            size--;
            if (size == 0) {
                tail = null;
            }
            return currentNode.data;
        } else {
            Node prevNode = null;
            for(int i=0; i<index; i++) {
                prevNode = currentNode;
                currentNode = currentNode.next;
            }
            prevNode.next = currentNode.next;

            if (currentNode == tail) {
                tail = prevNode;
            }
            size--;
        }
        System.out.println("---- remove 끝");
        return currentNode.data;
    }