[CS /Data Structure] 연결 리스트의 모든 것!

---

[Version]
⦁ 2024.04.05 / [CS /Data Structure] 연결 리스트의 모든 것!

 

연결 리스트

연결 리스트는 데이터를 담고 있는 노드를 포인터로 연결하여 구성된 자료 구조로, 공간적인 효율성을 극대화시킨다는 특징을 갖는다. 각 노드는 데이터와 다음 노드를 가르키는 포인터로 구성되어 있다. 이에 따라 연결 리스트는 데이터의 삽입과 삭제가  O(1) 시간 복잡도를 가지며 탐색에 대해서는 연결 리스트의 길이에 비례하는 O(n)의 시간 복잡도를 갖는다.

 

연결리스트는 다음과 같은 종류가 있다.

1. 싱글 연결 리스트
   • 각 노드는 데이터와 다음 노드를 가르키는 하나의 포인터로 구성된다.
   • 각 노드는 다음 노드만을 가리키므로 순방향으로만 탐색이 가능하다.
2. 이중 연결 리스트
   • 각 노드는 데이터와 이전 노드를 가리키는 포인터와 다음 노드를 가리키는 포인터로 구성된다.
   • 이전 노드와 다음 노드를 모두 가리킬 수 있어 순방향과 역방향으로 탐색이 가능하다.

---

싱글 연결 리스트 구현 (Java)

// 노드 클래스: 연결 리스트의 각 노드를 나타냄
class Node {
    int data; // 데이터 필드
    Node next; // 다음 노드를 가리키는 포인터

    // 생성자
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// 단일 연결 리스트 클래스
class SingleLinkedList {
    private Node head; // 연결 리스트의 첫 번째 노드를 가리키는 포인터

    // 생성자: 빈 연결 리스트 생성
    public SingleLinkedList() {
        this.head = null;
    }

    // 삽입 메서드: 연결 리스트의 맨 뒤에 노드를 삽입
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 삭제 메서드: 특정 데이터를 갖는 노드를 삭제
    public void delete(int data) {
        if (head == null) {
            System.out.println("리스트가 비어있습니다.");
            return;
        }

        if (head.data == data) {
            head = head.next;
            return;
        }

        Node current = head;
        while (current.next != null) {
            if (current.next.data == data) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }

        System.out.println("해당하는 데이터를 찾을 수 없습니다.");
    }

    // 출력 메서드: 연결 리스트의 모든 노드를 출력
    public void display() {
        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) {
        SingleLinkedList list = new SingleLinkedList();

        // 데이터 삽입
        list.insert(1);
        list.insert(7);
        list.insert(3);

        // 연결 리스트 출력
        System.out.print("연결 리스트: ");
        list.display(); // 연결 리스트 출력 --> 출력 결과: 1 7 3

        // 데이터 삭제
        list.delete(7);

        // 삭제 후 연결 리스트 출력
        System.out.print("삭제 후 연결 리스트: ");
        list.display(); // 삭제 후 연결 리스트 출력 --> 출력 결과: 1 3
    }
}