[Java | 자료구조] 연결 리스트(Linked List) 정리

연결 리스트란?

연결 리스트(Linked List)는 데이터를 저장하는 방식 중 하나로, 각 요소가 다음 요소에 대한 참조를 가지고 있으며, 요소들이 연속된 메모리 공간에 저장되지 않고 각각의 요소를 연결하여 구현되는 자료구조이다.

 

 

연결리스트의 구성요소

1. Node

연결 리스트의 기본 단위이다. 각 노드는 데이터와 하나 이상의 포인터를 포함한다.

• 데이터 필드: 노드가 저장하는 실제 데이터
• 포인터 필드: 다음 노드(또는 이전 노드)를 가리키는 포인터이다.

2. Head Node

연결 리스트의 시작을 가리키는 포인터이다 리스트의 첫 번째 노드를 가리키며, 이를 통해 리스트의 모든 노드에 접근할 수 있다.

3. Tail Node

리스트의 끝을 가리키는 노드로, 이를 활용하면 리스트의 끝에 요소를 빠르게 추가할 수 있다.

Tail Node는 자신의 다음에 가리킬 노드가 없기 때문에 pointer필드는 null 이다.

 

---

 

연결리스트의 특징

1. 각 요소가 이전 요소와 다음 요소에 대한 참조를 가지고 있다.

연결 리스트의 각 요소(노드)는 데이터와 함께 한 개의 참조(포인터)를 가지고 있다.
이러한 참조를 통해 노드들이 서로 연결되어 리스트를 구성한다.

2. 연속된 메모리 공간에 요소를 저장하지 않고 각각의 요소를 연결하여 구현된다.

배열과 달리, 연결 리스트의 요소들은 메모리에 연속적으로 저장되지 않는다.
각 노드는 독립적으로 메모리에 할당되며, 노드 간의 참조를 통해 리스트가 구성된다.

3.  유연성

중간에 요소를 추가하거나 삭제할 때, 단순히 노드의 참조만 변경하면 된다.
예를 들어, 노드를 추가할 때는 새로운 노드의 참조를 이전 노드와 다음 노드에 연결하면 되고,
노드를 삭제할 때는 이전 노드의 참조를 다음 노드로 연결하면 된다.

4. 인덱스로 바로 접근하는것이 느리다.

연결 리스트는 인덱스를 사용한 접근이 비효율적이다.배열과 달리 인덱스를 통해 바로 접근할 수 없기 때문에,
특정 인덱스의 요소에 접근하려면 리스트의 처음부터 순차적으로 접근해야 한다.
이는 시간 복잡도가 O(n)으로, 리스트의 길이가 길어질수록 접근 시간이 증가한다.

 

---

 

연결리스트의 장점

1. 동적 크기

연결 리스트는 동적으로 크기를 조절할 수 있다. 메모리가 허용하는 한, 필요한 만큼 요소를 추가할 수 있다.
각 노드는 독립적으로 메모리에 할당된다.
즉, 배열과 달리, 연결 리스트는 요소들이 연속된 메모리 공간에 저장될 필요가 없다.
새로운 요소가 추가될 때마다 새로운 노드를 생성하여 리스트에 연결하면 된다.
따라서 리스트의 크기는 메모리의 한계 내에서 자유롭게 증가하거나 감소할 수 있다.

2. 효율적인 요소 삽입 및 삭제

중간에 요소를 삽입하거나 삭제하는 작업이 배열에 비해 효율적이다.
열에서는 중간에 요소를 삽입하거나 삭제할 때 나머지 요소들을 이동해야 하지만,
연결 리스트에서는 단순히 포인터를 변경하는 것으로 충분하다.

3. 메모리 효율성

연결 리스트는 메모리가 허용하는 한, 요소의 수를 동적으로 조절할 수 있어 메모리의 낭비를 줄일 수 있다.
배열은 고정된 크기를 가지기 때문에 미리 할당된 메모리가 비효율적으로 사용될 수 있다.

 

---

 

연결 리스트의 단점

1. 인덱스 접근의 비효율성

연결 리스트는 인덱스를 통해 직접 접근할 수 없다.
특정 인덱스의 요소에 접근하려면 처음부터 순차적으로 접근해야 하므로 시간 복잡도가 O(n)이다. 

2.추가 메모리 사용

각 노드는 데이터 외에 하나 또는 두 개의 포인터를 저장해야 하므로 추가적인 메모리가 필요하다.
이로 인해 연결 리스트는 배열에 비해 메모리 오버헤드가 발생할 수 있다.

3.연산의 복잡성

연결 리스트는 요소를 찾는 연산이 비효율적이다.
특정 요소를 찾기 위해서는 리스트의 처음부터 끝까지 순차적으로 탐색해야 하므로 시간 복잡도가 O(n)이다.

 

연결리스트의 종류

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

• 각 노드가 다음 노드에 대한 참조만을 가지고 있다.
• 단방향으로만 이동할 수 있다.

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

• 각 노드가 이전 노드와 다음 노드에 대한 참조를 모두 가지고 있다.
• 양방향으로 이동할 수 있다.

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

• 마지막 노드가 첫 번째 노드를 가리키는 구조이다.
• 리스트의 끝에서 다시 처음으로 돌아갈 수 있다.

 

연결리스트 사용하기

자바에서 연결 리스트를 사용하는 방법에는 크게 두 가지가 있다. 하나는 자바에서 제공하는 LinkedList 클래스를 사용하는 것이고, 다른 하나는 사용자 정의 연결 리스트를 구현하여 사용하는 것이다. 

 

자바의 내장 LinkedList 클래스 사용

자바의 LinkedList 클래스는 java.util 패키지에 포함되어 있으며, List, Deque 인터페이스를 구현하고 있다.

이 클래스를 사용하면 연결 리스트를 쉽게 사용할 수 있다.

LinkedList<String> list = new LinkedList<>();

list.add("A");
list.add("B");
list.add("C");

list.add(1, "D");

System.out.println("요소 B의 인덱스를 반환 " + list.indexOf("B"));
System.out.println("리스트에 요소 C가 있는지 확인 " + list.contains("C"));

list.remove("B"); 
list.remove(2); 

 System.out.println("LinkedList: " + list);

 

사용자 정의 연결 리스트 구현

자바의 LinkedList 클래스를 사용하는 대신, 직접 연결 리스트를 구현할 수도 있다.

이는 연결 리스트의 내부 동작을 이해하는 데 도움이 된다.

class Node {
    int data;
    Node next;

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

class SinglyLinkedList {
    Node head;
    Node tail;

    // 리스트의 끝에 새로운 노드 추가
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }

    // 특정 위치에 노드 삽입
    public void insertAfter(Node prevNode, int newData) {
        if (prevNode == null) {
            System.out.println("The given previous node cannot be null");
            return;
        }
        Node newNode = new Node(newData);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
        if (newNode.next == null) {
            tail = newNode;
        }
    }

    // 특정 값을 가진 노드 삭제
    public void deleteNode(int key) {
        Node temp = head, prev = null;

        // head 노드가 삭제하려는 값인 경우
        if (temp != null && temp.data == key) {
            head = temp.next;
            if (head == null) {
                tail = null;
            }
            return;
        }

        // 삭제할 노드를 찾기 위해 리스트 탐색
        while (temp != null && temp.data != key) {
            prev = temp;
            temp = temp.next;
        }

        // 값을 찾지 못한 경우
        if (temp == null) return;

        // 노드를 리스트에서 제거
        prev.next = temp.next;
        if (prev.next == null) {
            tail = prev;
        }
    }

    // 리스트의 모든 노드 출력
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        // 요소 추가
        list.add(1);
        list.add(2);
        list.add(3);

        // 리스트 출력
        System.out.print("Initial list: ");
        list.printList();

        // 요소 삽입
        list.insertAfter(list.head.next, 4);
        System.out.print("After insertion: ");
        list.printList();

        // 요소 삭제
        list.deleteNode(2);
        System.out.print("After deletion: ");
        list.printList();
    }
}