LinkedList

LinkedList

 

자바의 LinkedList 클래스는 List 인터페이스를 구현한 대표적인 클래스 중 하나로, 이중 연결 리스트(doubly linked list)를 기반으로 합니다. 이는 각 요소가 데이터와 함께 다음 및 이전 요소에 대한 참조를 가지고 있는 데이터 구조입니다. LinkedList는 특히 요소의 삽입과 삭제 작업이 빈번한 경우에 유용합니다.

---

 

단일 연결 리스트 (Singly Linked List)

단일 연결 리스트는 각 노드가 다음 노드를 가리키는 참조만 가지고 있는 구조입니다. 이는 메모리 사용 측면에서 효율적이지만, 노드 삭제나 이전 노드로 이동하는 작업이 비효율적일 수 있습니다.

 

원형 연결 리스트 (Circular Linked List)

원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 구조입니다. 이를 통해 리스트의 끝과 시작을 쉽게 연결할 수 있습니다.

 

설명

• 단일 연결 리스트 (Singly Linked List):
  • 각 노드는 다음 노드에 대한 참조만을 가집니다.
  • 메모리 사용이 효율적입니다.
  • 노드를 삭제하거나 이전 노드를 참조하는 것이 어려울 수 있습니다.
• 원형 연결 리스트 (Circular Linked List):
  • 마지막 노드가 첫 번째 노드를 가리켜 원형 구조를 만듭니다.
  • 리스트의 끝과 시작을 쉽게 연결할 수 있습니다.
  • 순환적인 구조로 인해 리스트의 처음으로 쉽게 돌아갈 수 있습니다.

---

주요 특징

1. 이중 연결 리스트: 각 노드는 이전 노드와 다음 노드에 대한 참조를 가집니다.
2. 빠른 삽입 및 삭제: 리스트의 처음이나 중간에 요소를 삽입하거나 삭제하는 작업이 빠릅니다.
3. 순차 접근: 임의 접근은 배열 기반 리스트에 비해 느립니다. 리스트의 요소를 순차적으로 접근해야 합니다.

주요 메서드

LinkedList는 List 인터페이스를 구현하므로, ArrayList와 유사한 메서드를 제공합니다. 또한, Deque 인터페이스도 구현하여 큐(queue) 및 덱(deque)과 관련된 메서드도 사용할 수 있습니다.

• add(E e): 리스트의 끝에 요소를 추가합니다.
• add(int index, E element): 지정된 위치에 요소를 삽입합니다.
• remove(): 리스트의 첫 번째 요소를 제거하고 반환합니다.
• remove(int index): 지정된 위치의 요소를 제거합니다.
• get(int index): 지정된 위치의 요소를 반환합니다.
• size(): 리스트의 요소 개수를 반환합니다.
• clear(): 리스트의 모든 요소를 제거합니다.
• addFirst(E e): 리스트의 첫 번째 위치에 요소를 추가합니다.
• addLast(E e): 리스트의 마지막 위치에 요소를 추가합니다.
• getFirst(): 리스트의 첫 번째 요소를 반환합니다.
• getLast(): 리스트의 마지막 요소를 반환합니다.

 

다음은 LinkedList를 사용하는 간단한 예제입니다.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        // 요소 추가
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");
        list.addFirst("Apricot");
        list.addLast("Date");

        // 리스트 출력
        System.out.println("List: " + list);

        // 첫 번째 요소 제거 및 출력
        System.out.println("Removed first element: " + list.removeFirst());

        // 마지막 요소 제거 및 출력
        System.out.println("Removed last element: " + list.removeLast());

        // 특정 위치의 요소 가져오기
        System.out.println("Element at index 1: " + list.get(1));

        // 리스트의 크기 출력
        System.out.println("Size of the list: " + list.size());

        // 리스트의 모든 요소 제거
        list.clear();
        System.out.println("List after clearing: " + list);
    }
}

 

List: [Apricot, Apple, Banana, Cherry, Date]
Removed first element: Apricot
Removed last element: Date
Element at index 1: Banana
Size of the list: 3
List after clearing: []

 

 

내부 구현

LinkedList는 이중 연결 리스트를 기반으로 하며, 각 노드는 다음과 같은 구조를 가집니다:

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

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

 

• item: 노드가 저장하는 데이터.
• next: 다음 노드를 가리키는 참조.
• prev: 이전 노드를 가리키는 참조.

 

장점

• 빠른 삽입 및 삭제: 요소를 리스트의 중간에 삽입하거나 삭제하는 작업이 빠릅니다.
• 유연한 메모리 사용: 필요에 따라 노드를 동적으로 생성하고 제거하므로 메모리 사용이 효율적입니다.

단점

• 느린 임의 접근: 임의 접근이 배열보다 느리며, 리스트의 처음부터 순차적으로 접근해야 합니다.
• 메모리 오버헤드: 각 요소가 두 개의 참조(다음 및 이전)를 추가로 저장해야 하므로 메모리 오버헤드가 발생합니다.

 

---

1. ArrayList와 LinkedList:
   • ArrayList는 동적 배열을 사용하여 요소를 저장합니다. 요소에 대한 접근 속도가 빠르지만, 중간에 요소를 삽입하거나 삭제하는 작업은 느릴 수 있습니다.
   • LinkedList는 이중 연결 리스트를 사용하여 요소를 저장합니다. 중간에 요소를 삽입하거나 삭제하는 작업이 빠르지만, 요소에 대한 접근 속도는 느릴 수 있습니다.
2. List 인터페이스:
   • List 인터페이스를 사용하면 ArrayList나 LinkedList의 내부 구현 방식에 관계없이 동일한 방식으로 컬렉션을 조작할 수 있습니다.
   • printList 메서드는 List 인터페이스를 파라미터로 받아 리스트의 모든 요소를 출력합니다.

내부 구현의 차이점

• ArrayList:
  • 내부적으로 배열을 사용하여 요소를 저장합니다.
  • 요소 접근 속도가 빠르며, 인덱스를 사용하여 랜덤 접근이 가능합니다.
  • 배열 크기가 고정되어 있어 크기를 동적으로 변경해야 하는 경우 배열을 재할당해야 합니다.
• LinkedList:
  • 내부적으로 이중 연결 리스트를 사용하여 요소를 저장합니다.
  • 요소 삽입 및 삭제가 빠르며, 특히 리스트 중간에서의 작업이 효율적입니다.
  • 요소 접근 속도가 느리며, 리스트의 처음부터 순차적으로 접근해야 합니다.