연결리스트(Linked List)

연결 리스트 Linked List 는 데이터를 순서대로 저장하지만 배열과 달리 메모리상에 연속적으로 존재하지 않는 자료구조다.
각 데이터는 노드 Node 라고 부르며, 노드는 실제 데이터를 저장하는 영역과 다음 노드의 주소를 저장하는 포인터로 구성되어 있다.

연결 리스트의 가장 큰 특징은 크기가 가변적이라는 점이다. 즉, 프로그램 실행 중에 노드를 자유롭게 추가하거나 삭제할 수 있다.
배열처럼 메모리를 미리 크게 할당할 필요가 없기 때문에 메모리 효율성이 높다.
하지만 임의 접근이 불가능하다는 단점이 있다. 특정 위치의 데이터를 찾기 위해서는 처음 노드부터 순차적으로 탐색해야 한다.

---

연결 리스트의 종류

1. 단일 연결 리스트 Singly Linked List
   각 노드가 다음 노드의 주소만을 저장하는 형태다.
   마지막 노드는 다음 노드가 없기 때문에 포인터가 NULL을 가리킨다.
2. 이중 연결 리스트 Doubly Linked List
   각 노드가 이전 노드와 다음 노드의 주소를 모두 저장한다.
   양방향으로 이동이 가능하지만 메모리를 더 많이 사용한다.
3. 원형 연결 리스트 Circular Linked List
   마지막 노드의 포인터가 첫 번째 노드를 가리키는 형태다.
   리스트의 처음과 끝 구분이 없기 때문에 순환 구조를 표현할 수 있다.

---

단일 연결 리스트 예시 코드

#include <iostream>
using namespace std;

struct Node {
    int data;        // 데이터 저장
    Node* next;      // 다음 노드의 주소 저장
};

int main() {
    // 첫 번째 노드 생성
    Node* head = new Node;
    head->data = 10;
    head->next = nullptr;

    // 두 번째 노드 생성 및 연결
    Node* second = new Node;
    second->data = 20;
    second->next = nullptr;
    head->next = second;

    // 세 번째 노드 생성 및 연결
    Node* third = new Node;
    third->data = 30;
    third->next = nullptr;
    second->next = third;

    // 노드 순회
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }

    // 메모리 해제
    current = head;
    while (current != nullptr) {
        Node* temp = current;
        current = current->next;
        delete temp;
    }

    return 0;
}

---

정리

연결 리스트는 삽입과 삭제가 빈번한 상황에서 배열보다 효율적이다.
하지만 접근 속도는 배열보다 느리며, 포인터를 관리해야 하므로 구현이 복잡하다.
따라서 상황에 따라 배열과 연결 리스트 중 적합한 자료구조를 선택하는 것이 중요하다.