링크드리스트 LinkedList

---

• 링크드 리스트 linked list는 데이터 요소들이 연결linked된 선형적인 자료구조입니다.

• 각각의 요소는 다음 요소를 가리키는 포인터(참조)를 가지고 있어서 다음 요소를 쉽게 찾을 수 있습니다.

LinkedList 종류

---

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

  • 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 있는 형태입니다.

  • 노드를 순회할 때는 첫 번째 노드부터 마지막 노드까지 차례로 방문합니다.

• 이중 연결 리스트(Doubly Linked List)

  • 각 노드가 데이터와 이전 노드를 가리키는 포인터와 다음 노드를 가리키는 포인터를 가지고 있는 형태입니다.

  • 양쪽으로 순회할 수 있습니다.

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

  • 마지막 노드가 첫 번째 노드를 가리키고, 첫 번째 노드가 마지막 노드를 가리키는 형태입니다.

  • 단일 연결 리스트와 이중 연결 리스트 모두 원형 연결 리스트로 구현할 수 있습니다.

• 이중 원형 연결 리스트(Doubly Circular Linked List)

  • 마지막 노드가 첫 번째 노드를 가리키고, 첫 번째 노드가 마지막 노드를 가리키는 형태입니다.

  • 양쪽으로 순회할 수 있습니다.

LinkedList 특성

---

• 장점

  • 삽입 및 삭제 연산이 상수 시간(complexity) O(1)으로 수행 가능합니다.

  • 메모리 사용이 유연하게 가능합니다.

    • 링크드 리스트는 각 노드가 포인터로 연결되어 있으므로 동적으로 크기를 조정할 수 있습니다.

  • 배열과 달리 데이터의 중간 삽입이나 삭제가 용이합니다.

    • 링크드 리스트는 각 노드가 독립적으로 연결되어 있으므로 상대적으로 용이합니다.

• 단점

  • 랜덤 접근이 불가능합니다.

    • 링크드 리스트는 각 노드가 포인터로 연결되어 있기 때문에, 원하는 위치에 접근하기 위해서는 처음부터 차례대로 탐색해야 합니다. 따라서, 인덱스로 원소를 접근하는 경우 배열에 비해 느릴 수 있습니다.

  • 포인터를 위한 추가적인 메모리 공간이 필요합니다.

    • 각 노드는 다음 노드를 가리키는 포인터를 가지고 있기 때문에, 배열에 비해 메모리 사용이 더 많아질 수 있습니다.

  • 캐시 효율이 떨어질 수 있습니다.

    • 링크드 리스트는 데이터가 연속된 메모리 공간에 저장되어 있지 않기 때문에, 캐시 메모리를 이용한 데이터 접근 효율이 떨어질 수 있습니다.

Java의 LinkedList Class

---

• Java에서는 java.util.LinkedList를 제공합니다.

• 제네릭 타입을 사용하여 다양한 타입의 객체를 저장할 수 있습니다.

• add(E e) : 리스트의 끝에 요소를 추가합니다.

• add(int index, E element) : 리스트의 특정 인덱스에 요소를 추가합니다.

• get(int index) : 리스트의 특정 인덱스에 있는 요소를 반환합니다.

• getFirst() : 리스트의 첫 번째 요소를 반환합니다.

• getLast() : 리스트의 마지막 요소를 반환합니다.

• remove(int index) : 리스트의 특정 인덱스에 있는 요소를 삭제합니다.

• removeFirst() : 리스트의 첫 번째 요소를 삭제합니다.

• removeLast() : 리스트의 마지막 요소를 삭제합니다.

• size() : 리스트의 크기를 반환합니다.

import java.util.LinkedList;

public class ExampleLinkedList {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<String> linkedList = new LinkedList<>();

        // 리스트에 데이터 추가
        linkedList.add("apple");
        linkedList.add("banana");
        linkedList.add("cherry");

        // 리스트의 크기 출력
        System.out.println("LinkedList size: " + linkedList.size());

        // 리스트의 모든 요소 출력
        System.out.println("LinkedList elements: " + linkedList);

        // 리스트의 특정 인덱스에 데이터 추가
        linkedList.add(1, "orange");

        // 리스트의 첫 번째 요소 출력
        System.out.println("First element: " + linkedList.getFirst());

        // 리스트의 마지막 요소 출력
        System.out.println("Last element: " + linkedList.getLast());

        // 리스트의 모든 요소 출력
        System.out.println("LinkedList elements: " + linkedList);

        // 리스트의 특정 인덱스에 있는 요소 삭제
        linkedList.remove(2);

        // 리스트의 모든 요소 출력
        System.out.println("LinkedList elements: " + linkedList);

        // 리스트의 첫 번째 요소 삭제
        linkedList.removeFirst();

        // 리스트의 모든 요소 출력
        System.out.println("LinkedList elements: " + linkedList);

        // 리스트의 마지막 요소 삭제
        linkedList.removeLast();

        // 리스트의 모든 요소 출력
        System.out.println("LinkedList elements: " + linkedList);
    }
}

LinkedList 구현

---

• 가장 기본적인 구현 방법은 Node 클래스를 만들고, 각 노드가 다음 노드를 가리키는 포인터를 갖도록 하는 것입니다.

public class Node<T> {
    T data;
    Node<T> next;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedList<T> {
    Node<T> head;
    int size;

    public LinkedList() {
        this.head = null;
        this.size = 0;
    }

    public void add(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
        } else {
            Node<T> curr = head;
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = newNode;
        }
        size++;
    }

    public void add(int index, T data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        Node<T> newNode = new Node<>(data);
        if (index == 0) {
            newNode.next = head;
            head = newNode;
        } else {
            Node<T> curr = head;
            for (int i = 0; i < index - 1; i++) {
                curr = curr.next;
            }
            newNode.next = curr.next;
            curr.next = newNode;
        }
        size++;
    }

    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node<T> curr = head;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr.data;
    }

    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node<T> removedNode;
        if (index == 0) {
            removedNode = head;
            head = head.next;
        } else {
            Node<T> curr = head;
            for (int i = 0; i < index - 1; i++) {
                curr = curr.next;
            }
            removedNode = curr.next;
            curr.next = removedNode.next;
        }
        removedNode.next = null;
        size--;
        return removedNode.data;
    }

    public int size() {
        return size;
    }

    public void printList() {
        Node<T> curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

• Node 클래스를 정의하고, 각 노드가 데이터를 저장하고 다음 노드를 가리키는 next 포인터를 갖도록 합니다.

• LinkedList 클래스를 정의하고 head 노드를 가리키는 변수와 size 변수를 갖도록 합니다.

• add(T data), add(int index, T data), get(int index), remove(int index) 메소드는 각각 요소를 맨 뒤에 추가, 특정 인덱스에 요소를 추가, 특정 인덱스에 있는 요소를 반환, 특정 인덱스에 있는 요소를 삭제하는 역할을 합니다. size() 메소드는 현재 링크드리스트의 크기를 반환하며, printList() 메소드는 링크드리스트의 모든 요소를 출력합니다.