컬렉션 프레임워크 - LinkedList 직접 구현해보기

JAVA의 가장 기본이 되는 내용

컬렉션 프레임워크 - LinkedList 직접 구현해보기

cwchoiit 2024. 5. 12. 21:55

728x90

SMALL

참고자료:

김영한의 실전 자바 - 중급 2편 | 김영한 - 인프런

김영한 | 자바 제네릭과 컬렉션 프레임워크를 실무 중심으로 깊이있게 학습합니다. 자료 구조에 대한 기본기도 함께 학습합니다., 국내 개발 분야 누적 수강생 1위, 제대로 만든 김영한의 실전

www.inflearn.com

이전 포스팅에서 ArrayList를 직접 구현해봤다. 이 ArrayList는 내부에서 배열을 가지고 사용하는 자료구조이다.

ArrayList를 사용해서 얻는 장점은 다음과 같다.

조회가 순식간이라는 것. 인덱스를 통해 바로 그 값을 알아낼 수 있다. 조회는 O(1)의 시간복잡도를 가진다.
그냥 배열만 사용하면 사이즈가 꽉 차면 더이상 자료를 담을 수 없지만 ArrayList를 사용해서 사이즈가 꽉차면 더 큰 사이즈를 가지는 새로운 배열을 만들어서 계속 저장할 수 있다.

그러나 단점으로는 다음과 같다.

데이터를 맨앞에 추가하거나 삭제할 때 기존 데이터를 모두 한칸씩 뒤로 밀거나 앞으로 당겨야한다. 이는 O(n)의 시간복잡도를 가진다.
데이터를 중간에 추가하거나 삭제할 때도 중간 인덱스를 기점으로 이후 데이터는 모두 한칸씩 뒤로 밀거나 앞으로 당겨야한다. 이는 O(n)의 시간복잡도를 가진다.
사이즈가 꽉 차면 더 큰 배열로 새로 만드는데 그 때 남는 메모리가 생기고 이는 곧 메모리의 낭비로 이어진다.

이러한 단점들을 극복해주는 LinkedList가 있다. (사실 그렇게 어떤 드라마틱하게 단점을 극복하지는 않는다고 본다. 그 이유는 마지막에 한번 내 생각을 말해보겠다)

LinkedList는 자신이 보관하는 자료와 자신의 다음 자료에 대한 정보를 가지고 있다. 즉 데이터끼리 연결이 되어 있어서 `Linked`List라고 불린다.

이를 한번 직접 구현해보고, 어떤 장점이 있고 어떤 단점이 있는지 직접 느껴보자. 확실히 직접 구현해보니 보이는게 더 많아진다.

LinkedList에서 관리할 Node 클래스

Node

package org.example.collection.link;

public class Node {
    Object item;
    Node next;

    public Node(Object item) {
        this.item = item;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node x = this;

        sb.append("[");

        while (x != null) {
            sb.append(x.item);
            if (x.next != null) {
                sb.append("->");
            }
            x = x.next;
        }

        sb.append("]");
        return sb.toString();
    }
}

간단하게 Node 클래스는 자기가 보관할 데이터인 `item`과 다음 Node에 대한 정보를 가지는 `next`라는 필드를 가지고 있다.

근데 필드에 보면 접근 제어자를 지정하지 않았다. 이러면 default가 기본인데 왜 이렇게 했냐면 사실 Node는 추후에 중첩 클래스로 만들것이다. Node는 밖에서 쓰일 일이 없기 때문이다.

CustomLinkedList

package org.example.collection.link;

public class CustomLinkedList {
    private Node first;
    private int size;

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node x = first;

        builder.append("[");
        while (x != null) {
            builder.append(x.item);
            if (x.next != null) {
                builder.append(", ");
            }
            x = x.next;
        }
        builder.append("]");
        return builder.toString();
    }

    private static class Node {
        Object item;
        Node next;

        public Node(Object item) {
            this.item = item;
        }

        @Override
        public String toString() {
            return item.toString();
        }
    }
}

그래서 위 코드와 같이 Node라는 클래스를 LinkedList 내부에 중첩 클래스로 만든다. 이 상태에서 하나씩 중요 메서드들을 추가해보자.

가장 중요한 메서드 중 하나는 역시나 `add()`메서드다.

public void add(Object item) {
    Node newNode = new Node(item);
    if (size == 0) {
        first = newNode;
    } else {
        Node lastNode = getLastNode();
        lastNode.next = newNode;
    }
    size++;
}

public void add(int index, Object item) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException();
    }
    
    Node newNode = new Node(item);
    if (index == 0) {
        newNode.next = first;
        first = newNode;
    } else {
        Node prevNode = getNode(index - 1);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
    }
    size++;
}

private Node getNode(int index) {
    Node x = first;
    for (int i = 0; i < index; i++) {
        x = x.next;
    }
    return x;
}

private Node getLastNode() {
    Node x = first;
    while (x.next != null) {
        x = x.next;
    }
    return x;
}

우선, `add(Object item)`은 가장 마지막에 노드를 하나 추가하는 메서드이다. 현재 사이즈가 0인 경우엔 리스트의 첫번째 노드가 되면 되고 그게 아닌 경우 마지막 노드를 가져와서 그 노드의 다음 노드로 추가하면 된다.

두번째 `add(int index, Object item)`은 원하는 인덱스에 추가하는 경우다. 이 경우는 인덱스가 0인 경우와 그렇지 않은 경우가 나뉘어진다. 0이 아닌 경우는 추가하고자하는 인덱스의 바로 전 노드를 알아내야 한다. 추가하고자 하는 노드의 `next`가 index 노드가 되어야하고 `index - 1` 노드가 index의 노드를 알고 있기 때문이다.

그리고 그 과정에서 사용할 편의 메서드 `getNode(int index)`, `getLastNode()`를 만들었다.

여기까지 하고 실행해보자.

CustomLinkedListMain

package org.example.collection.link;

public class CustomLinkedListMain {
    public static void main(String[] args) {
        CustomLinkedList list = new CustomLinkedList();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        System.out.println("list = " + list);
        System.out.println("list.size() = " + list.size());
        list.add(2, "E");

        System.out.println("list = " + list);
        System.out.println("list.size() = " + list.size());

        list.add(0, "F");
        System.out.println("list = " + list);
        System.out.println("list.size() = " + list.size());
    }
}

실행결과

list = [A, B, C, D]
list.size() = 4
list = [A, B, E, C, D]
list.size() = 5
list = [F, A, B, E, C, D]
list.size() = 6

또 중요한 메서드 중 하나인 `get(int index)`와 `set(int index, Object item)`을 만들어보자.

public Object get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    Node currentNode = getNode(index);
    return currentNode.item;
}

public Object set(int index, Object item) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    Node oldNode = getNode(index);
    Object oldItem = oldNode.item;
    oldNode.item = item;
    return oldItem;
}

`get(int index)` 같은 경우는 이미 만들어 놓은 `getNode()` 메서드를 사용하면 간단하게 구현할 수 있다. `set(int index, Object item)`도 마찬가지로 `getNode()`를 사용하면 간단하게 구현이 가능하다.

이제 `remove()`를 구현해보자. 이 녀석은 맨 마지막에 있는것과 특정 인덱스가 주어졌을 때 두가지 케이스를 구현해보겠다.

public Object remove() {
    if (size == 0) {
        return null;
    }

    Node prevLastNode = getNode(size - 2);
    Object removedItem = prevLastNode.next.item;
    prevLastNode.next.item = null;
    prevLastNode.next = null;

    size--;
    return removedItem;
}

public Object remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    Object oldValue;
    if (index == 0) {
        Node newFirst = first.next;
        oldValue = first.item;
        first.item = null;
        first = newFirst;
    } else {
        Node prevNode = getNode(index - 1);
        Node removeNode = getNode(index);
        oldValue = removeNode.item;
        prevNode.next = removeNode.next;

        removeNode.next = null;
        removeNode.item = null;
    }
    size--;
    return oldValue;
}

`add()`를 구현하는 것과 비슷하다. 마지막 노드를 지우려면 마지막 노드의 전 노드를 구해서 `next`값을 지워주면 된다. 그리고 마지막 노드의 `item`을 null로 만들어주면 된다. 특정 위치의 노드는 0번일때와 그렇지 않을때로 구분해서 지우면 된다.

여기까지 만들면 get(), set(), remove()를 테스트 해볼 수 있다.

CustomLinkedListMain

package org.example.collection.link;

public class CustomLinkedListMain {
    public static void main(String[] args) {
        CustomLinkedList list = new CustomLinkedList();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        System.out.println("list = " + list);
        System.out.println("list.size() = " + list.size());
        list.add(2, "E");

        System.out.println("list = " + list);
        System.out.println("list.size() = " + list.size());

        list.add(0, "F");
        System.out.println("list = " + list);
        System.out.println("list.size() = " + list.size());

        Object item = list.get(1);
        System.out.println("item = " + item);

        list.set(1, "AA");
        System.out.println("list = " + list);

        
        Object removed = list.remove();
        System.out.println("removed = " + removed);
        System.out.println("list = " + list);
        Object removed2 = list.remove(1);
        System.out.println("removed2 = " + removed2);
        System.out.println("list = " + list);
        Object removed3 = list.remove(0);
        System.out.println("removed3 = " + removed3);
        System.out.println("list = " + list);
    }
}

실행결과

list = [A, B, C, D]
list.size() = 4
list = [A, B, E, C, D]
list.size() = 5
list = [F, A, B, E, C, D]
list.size() = 6
item = A
list = [F, AA, B, E, C, D]
removed = D
list = [F, AA, B, E, C]
removed2 = AA
list = [F, B, E, C]
removed3 = F
list = [B, E, C]

이제 마지막으로 `indexOf()`를 구현해보자.

public int indexOf(Object item) {
    Node x = first;
    for (int i = 0; i < size; i++) {
        if (x.item.equals(item)) {
            return i;
        }
        x = x.next;
    }
    return -1;
}

어느정도 구현해야 할 중요한 메서드들은 구현이 완료됐다. 이렇게 만들고 나니 LinkedList의 장단점이 하나씩 보이기 시작하는데 그 전에 모든 타입에 대해 허용하고 있으니 제네릭으로 바꿔주자.

제네릭을 도입한 CustomLinkedList

CustomLinkedList

package org.example.collection.link;

public class CustomLinkedList<E> {
    private Node<E> first;
    private int size;

    public int size() {
        return size;
    }

    public void add(E item) {
        Node<E> newNode = new Node<>(item);
        if (size == 0) {
            first = newNode;
        } else {
            Node<E> lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

    public void add(int index, E item) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> newNode = new Node<>(item);
        if (index == 0) {
            newNode.next = first;
            first = newNode;
        } else {
            Node<E> prevNode = getNode(index - 1);
            newNode.next = prevNode.next;
            prevNode.next = newNode;
        }
        size++;
    }

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> currentNode = getNode(index);
        return currentNode.item;
    }

    public E set(int index, E item) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> oldNode = getNode(index);
        E oldItem = oldNode.item;
        oldNode.item = item;
        return oldItem;
    }

    public E remove() {
        if (size == 0) {
            return null;
        }

        Node<E> prevLastNode = getNode(size - 2);
        E removedItem = prevLastNode.next.item;
        prevLastNode.next.item = null;
        prevLastNode.next = null;

        size--;
        return removedItem;
    }

    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        E oldValue;
        if (index == 0) {
            Node<E> newFirst = first.next;
            oldValue = first.item;
            first.item = null;
            first = newFirst;
        } else {
            Node<E> prevNode = getNode(index - 1);
            Node<E> removeNode = getNode(index);
            oldValue = removeNode.item;
            prevNode.next = removeNode.next;

            removeNode.next = null;
            removeNode.item = null;
        }
        size--;
        return oldValue;
    }

    public int indexOf(E item) {
        Node<E> x = first;
        for (int i = 0; i < size; i++) {
            if (x.item.equals(item)) {
                return i;
            }
            x = x.next;
        }
        return -1;
    }

    private Node<E> getNode(int index) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node<E> x = first;

        builder.append("[");
        while (x != null) {
            builder.append(x.item);
            if (x.next != null) {
                builder.append(", ");
            }
            x = x.next;
        }
        builder.append("]");
        return builder.toString();
    }

    private Node<E> getLastNode() {
        Node<E> x = first;
        while (x.next != null) {
            x = x.next;
        }
        return x;
    }

    private static class Node<E> {
        E item;
        Node<E> next;

        public Node(E item) {
            this.item = item;
        }

        @Override
        public String toString() {
            return item.toString();
        }
    }
}

제네릭까지 도입해서 타입 안정성도 확보했다. 이제 내 결론을 내려고 한다.

결론

ArrayList와 LinkedList는 이런 차이가 있다.

연산	ArrayList	LinkedList (Custom)
조회	O(1)	O(n)
탐색	O(n)	O(n)
맨 앞 추가(삭제)	O(n)	O(1)
중간 추가(삭제)	O(n)	O(n)
마지막 추가(삭제)	O(1)	O(n)
사이즈 조정	메모리 낭비 있을 수 있음	메모리 낭비 없음 (표면적으론)

조회: ArrayList가 더 유리하다. 배열은 인덱스로 바로 알아낼 수 있으니까. 그러나 LinkedList는 첫번째부터 계속 하나씩 찾아나가야 한다.
탐색: 둘 다 처음부터 끝까지 하나씩 찾아나간다.
맨 앞에 추가 또는 삭제: LinkedList가 더 유리하다. 배열은 추가하거나 삭제하려면 모든 자료를 한칸씩 뒤로 밀거나 앞으로 당겨야 한다. 반면 LinkedList는 연결 정보만 바꿔주면 된다.
중간 추가 또는 삭제: 배열은 추가하는 작업 자체는 O(1)이지만 중간지점부터 마지막까지 한칸씩 밀거나 당겨야한다. LinkedList는 추가, 삭제 작업 모두 O(1)으로 끝낼 수 있지만 중간까지 찾아나가는 작업이 O(n)이다.
마지막 추가 또는 삭제: 이건 지금 만든 CustomLinkedList 기준 ArrayList가 더 유리하다. 근데 자바가 만들어놓은 LinkedList는 첫번째 노드뿐만 아니라 마지막 노드도 가지고 있다. 그래서 자바가 만들어놓은 LinkedList는 O(1)이 될 수 있다.

사이즈는 LinkedList는 남는 메모리는 존재하지 않는다. 하나씩 다음 노드를 저장만 해 놓으면 되니까. 근데, 다음 노드를 저장하는 공간에 대한 메모리가 사용된다. 그러니까 어떻게 보면.. 메모리가 사용 측면에서 더 효율적이지 않을 수도 있을것같다.

그래서 결론은 더 유리하고 덜 유리한 자료구조 관계가 아니라 그때 그때 더 유리하게 작용될 수 있는 자료구조를 직접 선택해 나가야 한다는 것이다. (근데 대부분의 경우 ArrayList가 더 유리하다. 다만, 맨 앞에 자료가 추가(삭제)가 되는 경우가 많으면 LinkedList를 고려해보자.)

이제 보니까 ArrayList도 LinkedList도 메서드 시그니쳐가 거의 똑같거나 아예 똑같다. 그러면 자바는 이걸 어떻게 하더라? 추상화한다. 그래서 지금까지 사용했던 리스트에 대한 타입이 List<T>인 이유가 여기에 있는것 같다. 아래와 같이 사용하곤 했다.

List<String> list = new ArrayList<>();

그래서 추상화 하는 것을 알아보고자 한다.

728x90

LIST

저작자표시

'JAVA의 가장 기본이 되는 내용' 카테고리의 다른 글

컬렉션 프레임워크 - Set 직접 구현해보기 (hash, hashCode()에 대해) (0)	2024.05.14
컬렉션 프레임워크 - List 인터페이스 (0)	2024.05.13
컬렉션 프레임워크 - ArrayList 직접 구현해보기 (0)	2024.05.10
제네릭 (0)	2024.05.08
예외 처리 3 (예외 처리 도입) (0)	2024.04.23

현재글컬렉션 프레임워크 - LinkedList 직접 구현해보기

250x250

Spring cloud, JPA, IAC, Design Pattern, MSA, typescript, MongoDB, packer, Proxy Pattern, AOP, aws lambda, Spring, ansible, Linux, EC2, AWS, terraform, Spring boot, troubleshooting, 스프링 AOP,

Today :
Yesterday :

일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

programmer.cwchoiit