4. Linked List (1)

baba-sun 2025. 11. 7. 15:00

2025. 11. 7. 15:00

List

리스트(List) : 순서가 있는 데이터의 모음(Sequence of items)
각 요소가 고유한 위치를 가지고 있음.

1. Array-based List (배열 기반 리스트)

배열에 데이터를 순서대로 저장하는 방식.
데이터가 메모리상에 연속된 공간에 저장됨.
C에서는 배열을 통해 순차 리스트를 구현할 수 있음

인덱스를 이용한 빠른 접근 가능: O(1)
하지만 삽입/삭제 시 요소를 이동해야 하므로 O(n)
리스트 크기가 고정되어 있어 유연성이 떨어짐

배열 기반 리스트에서 삽입/삭제 시의 변화 예시)

연산	설명	[5, 12, 23, 14, 13]
삽입	중간에 데이터를 넣기 위해 뒤의 요소들을 한 칸씩 이동	Insert 10 at index 3 → [5, 12, 23, 10, 14, 13]
삭제	삭제 후 남은 요소들을 한 칸씩 앞으로 당김	Delete index 2 → [5, 12, 10, 14, 13]

📉 시간복잡도

평균: O(n/2)
최악(맨 앞 삽입): O(n)

이처럼 배열은 랜덤 접근은 빠르지만, 삽입·삭제는 비효율적임.

이를 해결하기 위한 구조가 바로 Linked List

2. Pointer-based List (Linked List)

연결 리스트는 각 데이터를 노드(Node) 단위로 저장하고, 각 노드가 다음 노드의 주소를 포인터로 연결하는 구조
즉, 데이터들이 메모리상에 연속적으로 위치할 필요가 없음.
필요할 때마다 동적으로 노드를 생성하여 연결할 수 있
= 삽입/삭제 시 포인터만 수정하면 되므로 배열보다 유연함.

구조

각 노드는 다음 두 가지 정보를 가짐:

data – 실제 값
link – 다음 노드의 주소(pointer)

리스트의 첫 번째 노드는 head(또는 first)가 가리키며,

(첫 Node가 어디에 저장되어있는지를 알아야하므로 head pointer 필요함.)
마지막 노드는 NULL을 가리켜 리스트의 끝을 의미함.

구현 예시 (C)

typedef struct Node {
    int data;
    struct Node* link;
} Node;

Node* head = NULL;

노드 생성

Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = 10;
newNode->link = NULL;

삽입 (맨 앞, 중간, 맨 뒤)

중간에 삽입할 경우 삽입하고자 하는 앞의 link 와 삽입할 data를 연결, 삽입할 data의 link와 다음에 올 data를 연결하면 됨.

// 새 노드를 기존 노드 뒤에 연결
newNode->link = head;
head = newNode;

삭제

특정 노드를 삭제하려면 이전 노드의 링크를 다음 노드로 변경하면 됨

prev->link = target->link;
free(target);

출력

void printList(Node *head) {
    for (Node *cur = head; cur != NULL; cur = cur->next)
        printf("%d -> ", cur->data);
    printf("NULL\n");
}

특징

장점: 삽입/삭제 O(1) (위치만 알면 됨), 크기 동적 조절 가능
단점: 인덱스 접근 불가(O(n)), 추가 메모리(포인터) 필요

정리하자면,

항목	array list	linked list
메모리 구조	연속된 공간	불연속적, 동적 할당
접근 속도	빠름 (O(1))	느림 (O(n))
삽입/삭제	느림 (O(n))	빠름 (O(1))
크기 조절	불가능	가능
추가 메모리	없음	포인터 저장 필요

== 삽입/삭제가 빈번하고 데이터 크기가 동적으로 변한다면 Linked List가 유리하다.

3. Linked Array & Linked Queue & Linked Stack

- Linked Array

배열 + 연결 리스트의 절충형.
구조는 배열이지만, 배열 내 각 원소가 다음 인덱스를 가리키는 링크를 가짐.
메모리 풀(memory pool) 방식으로 구현해 메모리 단편화 최소화.

typedef struct {
    int data;
    int next; // 다음 요소의 인덱스
} Node;

Node node[MAX];
int head = -1;
int avail = 0;

head는 첫 노드의 인덱스를,
avail은 사용 가능한 다음 빈 공간을 나타냄.
실제로는 배열 안에 링크 정보를 저장하므로,
메모리 연속성 + 동적 연결의 장점을 일부 가짐.

이 방식은 주로 임베디드 환경이나 메모리 제약 시스템에서 사용됨.

- Linked Queue

연결 리스트를 사용하여 큐(Queue) 를 구현한 구조
큐(Queue): FIFO (First In First Out) 구조.
배열 기반 큐는 공간이 꽉 차면 이동 필요 → 비효율적.
연결 리스트 기반 큐 는 노드 추가/삭제가 유연함.

크기 제한 없음 (동적 노드 생성 가능)
삽입/삭제 모두 O(1)
포인터 관리 필요 (메모리 누수 주의)

구조 정의

typedef struct Node {
    int data;
    struct Node* link;
} Node;

typedef struct {
    Node* front;
    Node* rear;
} LinkedQueue;

주요 연산

// 초기화
void initQueue(LinkedQueue* q) {
    q->front = q->rear = NULL;
}

// 삽입(enqueue)
void enqueue(LinkedQueue* q, int val) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = val;
    newNode->link = NULL;
    if (q->rear == NULL)
        q->front = q->rear = newNode;
    else {
        q->rear->link = newNode;
        q->rear = newNode;
    }
}

// 삭제(dequeue)
int dequeue(LinkedQueue* q) {
    if (q->front == NULL) return -1;
    Node* tmp = q->front;
    int val = tmp->data;
    q->front = q->front->link;
    if (q->front == NULL)
        q->rear = NULL;
    free(tmp);
    return val;
}

- Linked Stack

연결 리스트를 사용하여 스택(Stack) 를 구현한 구조
스택(Stack): LIFO (Last In, First Out) 구조.

크기 제한 없음 (동적 노드 생성 가능)
삽입/삭제 모두 O(1)

Top → [30] → [20] → [10] → NULL

push: 새 노드를 head(Top) 앞에 삽입
pop: head를 삭제