[CS] 연결 리스트(Linked List)

giggle·2023년 8월 20일

📌 연결 리스트(Linked List)란?

데이터 요소들을 순서대로 저장하는 선형 자료구조입니다. 배열과는 달리 연속적인 메모리 공간을 필요로 하지 않고, 각 요소가 다음 요소의 주소를 가리키는 방식으로 구현됩니다. 연결 리스트는 각 노드(Node)가 데이터와 다음 노드를 가리키는 포인터(Pointer)로 구성되어 있습니다.

포인터를 통해 연결되며 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성되어 있습니다.

장점

크기 변경이 용이: 배열과 달리 연결 리스트는 동적으로 크기를 변경할 수 있습니다. 새로운 노드를 추가하거나 기존 노드를 삭제하는 작업이 비교적 간단합니다.

메모리 공간의 효율적 사용: 연결 리스트는 각 노드가 독립적으로 할당되므로 불필요한 메모리 공간이 낭비되지 않습니다. 배열은 미리 정해진 크기를 가지므로 미사용 공간이 발생할 수 있습니다.

삽입과 삭제 연산이 효율적: 특정 위치에 노드를 추가하거나 삭제하는 작업이 O(1) 또는 O(n)의 시간 복잡도로 수행될 수 있습니다. 이는 배열과는 달리 데이터를 미루거나 뒤로 당기지 않아도 되기 때문입니다.

단점

접근이 느림: 특정 인덱스로 접근하려면 처음부터 순회해야 하므로 O(n)의 시간 복잡도를 가집니다. 배열의 경우 O(1)에 접근이 가능합니다.

추가적인 포인터 필요: 각 노드마다 다음 노드를 가리키는 포인터가 필요하므로 메모리 사용이 배열보다 더 많을 수 있습니다.

메모리 오버헤드: 각 노드에 추가적인 포인터가 필요하므로 메모리 오버헤드가 발생할 수 있습니다. 작은 데이터를 저장하는데에도 각 노드마다 포인터 공간이 필요합니다.

순회 필요: 리스트 내의 특정 데이터를 찾거나 작업하기 위해서는 순회해야 하므로 성능이 다소 떨어질 수 있습니다.

📌 구현(Java)

class Node {
    int data;
    Node next;

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

앞쪽에 노드 추가

public void push(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }

특정 노드 다음에 추가

public void insertAfter(Node prev_node, int new_data) {
        if (prev_node == null) {
            System.out.println("이전 노드가 NULL이 아니어야 합니다.");
            return;
        }

        Node new_node = new Node(new_data);
        new_node.next = prev_node.next;
        prev_node.next = new_node;
    }

끝쪽에 노드 추가

public void append(int new_data) {
        Node new_node = new Node(new_data);
        if (head == null) {
            head = new_node;
            return;
        }

        Node last = head;
        while (last.next != null) {
            last = last.next;
        }

        last.next = new_node;
    }