[컬렉션 프레임워크] LinkedList

ArrayList의 한계

 

ArrayList는 내부적으로 배열(Array)을 기반으로 작동하며, 이 구조는 조회에는 빠르지만 삽입/삭제가 빈번한 경우에 비효율적이다.

 

* ArrayList의 한계

• 크기 고정 문제 : 배열 기반이므로 요소가 많아지면 배열을 새로 생성하고 복사해야 함 -> 성능 저하
• 중간 삽입/삭제 비효율 : 배열의 요소를 하나씩 이동해야 하므로 시간 복잡도 O(n)
• 삽입/삭제 성능 저하 : 대량의 데이터를 다루거나 빈번하게 요소를 조작할 때 비효율적

 

=> 이러한 문제를 해결하기 위해 LinkedList 사용

---

LinkedList

 

1. LinkedList란?

자바에서 제공하는 List 인터페이스의 구현체 중 하나로, 노드(Node)를 기반으로 데이터를 연결해서 관리하는 연결 리스트 구조이다.

ArrayList는 배열 기반이라 요소 간의 물리적 순서가 중요하지만, LinkedList는 노드들이 참조를 통해 논리적으로 연결된다.

 

2. 노드(Node)와 연결 구조

* 노드(Node)란?

• 하나의 노드는 데이터, next 포인터, prev 포인터와 같은 정보를 가진다.
  • 데이터(data) : 저장할 값
  • next 포인터 : 다음 노드의 주소를 가리킴
  • prev 포인터 : 이전 노드의 주소를 가리킴(이중 연결 리스트의 경우)
• + 즉, 이중 연결 리스트(Doubly Linked List)는 이전 노드(prev)와 다음 노드(next)를 모두 가진다.

Node {
   Object data;
   Node next;
}


// 이중 연결 리스트
Node {
   Object data;
   Node next;
   Node prev;
}

 

* 연결 구조

• 각 노드는 자신과 다음 노드를 참조하고, 필요에 따라 이전 노드도 참조
• 동적으로 크기를 조절할 수 있고, 요소를 중간에 넣거나 빼기 쉬움
• 단방향 연결 리스트 : next 만 존재
• 이중 연결 리스트(자바의 LinkedList) : next, prev 모두 존재

3.  LinkedList 작동 원리

1. 처음 추가
   • 첫 노드가 생성되면 head와 tail이 동일한 노드를 가리킴
2. 뒤에 추가(addLast)
   • 새 노드를 만들고 기존 tail의 next가 새 노드를 가리킴
   • 새 노드의 prev가 기존 tail을 가리킴
   • tail을 새 노드로 업데이트
3. 앞에 추가(addFirst)
   • 새 노드를 만들고 기존 head의 prev가 새 노드를 가리킴
   • 새 노드의 next가 기존 head를 가리킴
   • head를 새 노드로 업데이트

package collection.link;

public class MyLinkedListV2 {

    private Node first;
    private int size = 0;

    public void add(Object e) {
        Node newNode = new Node(e);

        if (first == null) {
            first = newNode;
        } else {
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

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

    // 추가 코드
    public void add(int index, Object e) {
        Node newNode = new Node(e);
        if (index == 0) {
            newNode.next = first;
            first = newNode;
        } else {
            Node prev = getNode(index - 1);
            newNode.next = prev.next;
            prev.next = newNode;
        }
        size++;
    }

    public Object set(int index, Object element) {
        Node x = getNode(index);
        Object oldValue = x.item;
        x.item = element;
        return oldValue;
    }

    // 추가 코드
    public Object remove(int index) {
        Node removeNode = getNode(index);
        Object removedItem = removeNode.item;

        if (index == 0) {
            first = removeNode.next;
        } else {
            Node prev = getNode(index - 1);
            prev.next = removeNode.next;
        }
        removeNode.item = null;
        removeNode.next = null;
        size--;
        return removedItem;
    }

    public Object get(int index) {
        Node node = getNode(index);
        return node.item;
    }

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

    public int indexOf(Object o) {
        int index = 0;
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                return index;
            }
            index++;
        }

        return -1;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyLinkedListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }
}

 

* 삽입과 삭제

• 연결된 노드 포인터만 업데이트 하면 됨
• 삽입(Insertion)
  • 리스트의 앞 : addFirst
  • 리스트의 끝 : addLast
  • 중간 위치 : add(index, element)
  • 시간 복잡도
    • 맨 앞 / 뒤 삽입 : O(1)
    • 중간 삽입 : O(n) -> 해당 위치까지 순회
• 삭제(Removal)
  • 리스트의 앞 : removeFirst
  • 리스트의 끝 : removeLast
  • 중간 위치 : remove(index)
  • 시간 복잡도
    • 맨 앞 / 뒤 삽입 : O(1)
    • 중간 삽입 : O(n) -> 해당 위치까지 순회

* 삽입/삭제가 빠른 이유

• 노드는 포인터만 바꾸면 되기 때문에 요소 하나를 삽입/삭제할 때 연결 관계인 next, prev만 조정하면 되고, 전체 데이터를 이동시킬 필요가 없음
• 따라서 중간 삽입/삭제가 O(1), 하지만 위치를 찾는 데 O(n) 필요
• 단, 조회할 때는 순차적으로 노드를 따라가야 하므로 조회 성능은 낮음

4. ArrayList vs LinkedList

항목	ArrayList	LinkedList
내부 구조	배열 기반	노드 기반
크기 관리	고정 배열, 자동 확장 필요	동적 크기
조회 성능	빠름 O(1)	느림 O(n)
삽입/삭제	느림(요소 이동 필요)	빠름
메모리 사용	연속된 공간	분산된 공간, 참조 공간 필요

• ArrayList는 조회가 빠르고, LinkedList는 삽입/삭제가 빠름
• ArrayList는 인덱스 기반 O(1) 조회, LinkedList는 순차탐색 O(n)
• LinkedList는 데이터 구조가 유연하고, 스택/큐 등으로 활용하기 쉬움

 

* LinkedList의 특징

• 삽입/삭제 성능 우수 : 연결만 바꾸면 되므로 O(1)
• 조회 성능 낮음 : 특정 인덱스를 찾기 위해 처음부터 순회해야 하므로 느림
• 메모리 사용 증가 : 데이터 외에 참조값(포인터) 공간 필요
• 스택, 큐 등의 자료구조로 쉽게 활용 가능

5.  LinkedList의 메서드

메서드	설명
addFirst() / addLast()	앞 / 뒤에 요소 추가
removeFirst() / removeLast()	앞 / 뒤에서 삭제
get(index)	인덱스로 요소 조회
contains(Object o)	특정 요소 포함 여부 확인
size()	요소 개수 반환

 

6. LinkedList에 제네릭 적용

LinkedList도 내부적으로 Object 배열을 사용해서 요소를 저장하기 때문에 타입 안정성이 떨어지고 형변환이 필요

=> 제네릭 사용

 

* 제네릭 사용

• 타입 안정성 확보 : 잘못된 타입 입력 시 컴파일 단계에서 오류
• 불필요한 형변환 제거
• 코드 가독성 향상 및 유지보수 용이

package collection.link;

public class MyLinkedListV3<E> {

    private Node<E> first;
    private int size = 0;

    public void add(E e) {
        Node<E> newNode = new Node<>(e);

        if (first == null) {
            first = newNode;
        } else {
            Node<E> lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

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

    // 추가 코드
    public void add(int index, E e) {
        Node<E> newNode = new Node<>(e);
        if (index == 0) {
            newNode.next = first;
            first = newNode;
        } else {
            Node<E> prev = getNode(index - 1);
            newNode.next = prev.next;
            prev.next = newNode;
        }
        size++;
    }

    public Object set(int index, E element) {
        Node<E> x = getNode(index);
        E oldValue = x.item;
        x.item = element;
        return oldValue;
    }

    // 추가 코드
    public E remove(int index) {
        Node<E> removeNode = getNode(index);
        E removedItem = removeNode.item;

        if (index == 0) {
            first = removeNode.next;
        } else {
            Node<E> prev = getNode(index - 1);
            prev.next = removeNode.next;
        }
        removeNode.item = null;
        removeNode.next = null;
        size--;
        return removedItem;
    }

    public E get(int index) {
        Node<E> node = getNode(index);
        return node.item;
    }

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

    public int indexOf(E o) {
        int index = 0;
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                return index;
            }
            index++;
        }

        return -1;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyLinkedListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }

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

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

        // [A -> B -> C]
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            Node<E> 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();
        }
    }
}

* 중첩 클래스 사용(예시 코드)

• 클래스 안에 선언된 또 다른 클래스
• 내부 클래스(Inner Class)와는 다르게 static이 없는 중첩 클래스는 인스턴스에 종속됨
• 외부 클래스에서만 사용되며 외부에 노출되지 않음
• 사용 이유
  • Node는 LinkedList 내부에서만 사용하는 구조체이므로 외부에서 직접 접근할 필요가 없음
  • private static class Node<E>와 같이 선언한 경우 캡슐화가 지켜짐
  • 내부에서만 사용하고 LinkedList의 구현 세부사항을 외부에 숨길 수 있음

최종 결론 : LinkedList를 언제 사용해야 할까?

• 삽입과 삭제가 빈번한 작업이 많을 때
• 조회보다는 데이터 수정(조작)이 많은 경우
• 리스트를 스택이나 큐로 활용하고 싶은 경우

---

총정리

• LinkedList 구조
  • 노드(Node)를 연결해 데이터를 저장하는 구조로 동적 크기 조절 가능
  • 각 노드는 데이터 + 다음 노드 주소로 구성
• 삽입/삭제에 유리
  • 요소 간 포인터만 변경하면 되기 때문에 중간 삽입/삭제가 빠름
• 조회는 비효율적
  • 인덱스로 직접 접근할 수 없어 순차 탐색 -> O(n)
  • 자주 조회해야 한다면 ArrayList가 적합
• 활용
  • 삽입/삭제가 빈번한 구조인 큐, 스택 등에 효과적

---

<참고> - 김영한의 실전 자바 중급2편 강의 섹션 5. 컬렉션 프레임워크 LinkedList