리스트

리스트

• 순서를 가진 항목들의 모임
• 각 항목은 해당 리스트 내에서 유일한 위치를 가짐

리스트의 예

• 요일: (일요일, 월요일, ..., 토요일)
• 한글 자음 모임: (ㄱ, ㄴ, ..., ㅎ)
• 카드: (Ace, 2, 3, ..., King)[[1]]
• 스마트폰 문자 메시지 목록: 시간 순서대로 정렬된 메시지들
• 다항식의 각 항들: $3x^2 + 2x - 5$ 에서 $(3x^2, 2x, -5)$ 와 같이 각 항들이 순서를 가짐
• 버킷 리스트 또는 위시 리스트: 해야 할 일이나 갖고 싶은 물건들을 순서대로 나열한 목록

[[1]]: Ace, 2, 3, ... 순서로 특정 규칙에 따른 순서가 있기에 리스트로 볼 수 있다.

리스트의 구조

• 요소들이 순서대로 나열되어 있으며, 중간에 비어있는 위치는 없어야 함
• 삽입과 삭제가 임의의 위치에서 가능

스택, 큐, 덱과의 비교

• 공통점: 모두 선형 자료구조. 항목들이 일렬로 나열
• 차이점: 자료의 접근, 삽입, 삭제 위치에 제약이 있음
  • 스택(Stack): 한쪽 끝(top)에서만 삽입/삭제 (LIFO)
  • 큐(Queue): 한쪽 끝(rear)에서 삽입, 다른 쪽 끝(front)에서 삭제 (FIFO)
  • 덱(Deque): 양쪽 끝에서 삽입/삭제 가능
  • 리스트(List): 임의의 위치에서 삽입/삭제 가능

리스트의 ADT

• 데이터: 임의의 접근 방법을 제공하는, 같은 유형의 요소들로 이루어진 순서 있는 모임
• 연산
  • init(): 리스트를 초기화
  • insert(pos, e): pos 위치에 새로운 요소 e를 삽입
  • delete(pos): pos 위치에 있는 요소를 삭제하고 반환
  • get_entry(pos): pos 위치에 있는 요소를 반환
  • is_empty(): 리스트가 비어 있는지 검사
  • is_full(): 리스트가 가득 차 있는지 검사
  • find(item): 리스트에 요소 item이 있는지 확인하고 위치를 반환
  • replace(pos, item): pos 위치의 요소를 새로운 item으로 교체
  • size(): 리스트 안의 요소 개수를 반환

리스트 구현 방법

배열을 이용한 구현

• 장점
  • 구현이 비교적 간단
  • 특정 위치 요소 접근 빠름 $O(1)$
• 단점
  • 삽입, 삭제 시 요소들을 이동해야 하므로 오버헤드 발생 $O(n)$
  • 리스트의 크기가 초기에 고정되어, 항목 개수 제한

연결 리스트를 이용한 구현

• 장점
  • 삽입, 삭제가 효율적 (특정 위치를 안다면 $O(1)$, 찾는 시간 포함 시 $O(n)$)
  • 크기가 동적으로 변할 수 있어 제한 없음 (메모리 한도 내)
• 단점
  • 구현이 배열보다 복잡
  • 특정 위치 요소 접근 시 처음부터 순회해야 함 $O(n)$
  • 각 요소마다 다음 요소를 가리키는 포인터 공간 추가 필요

배열을 이용한 리스트

배열 리스트의 구조

• MAX_SIZE까지 요소를 저장할 수 있는 1차원 배열에 항목들을 순서대로 저장
• size 변수로 현재 저장된 항목의 개수를 추적

배열 리스트 구현

• 종이 한 장 (배열): 미리 정해진 칸 수(크기)만큼만 할 일을 적을 수 있음
• 할 일 (요소): "장보기", "책 읽기", "운동하기" 등
• 적힌 할 일 개수 (num_todos): 현재 목록에 있는 할 일의 수

#define MAX_TODOS 100 // 최대 100개의 할 일을 저장할 수 있는 리스트

typedef struct {
    char description[256]; // 할 일 내용
    int completed;         // 완료 여부 (0: 미완료, 1: 완료)
} TodoItem;

TodoItem todo_list[MAX_TODOS]; // 할 일들을 저장할 배열
int num_todos = 0;             // 현재 저장된 할 일의 개수

배열 리스트의 상태 검사

• is_empty(): 리스트가 비었는지 검사 (num_todos == 0)
• is_full(): 리스트가 꽉 찼는지 검사 (num_todos == MAX_TODOS)

삽입 연산: insert(pos, e)

• pos 위치에 새로운 요소 e를 삽입
• 과정
  1. 리스트가 꽉 찼는지 확인 (오버플로우 체크)
  2. pos 위치가 유효한지 확인 (0 <= pos <= num_todos)
  3. 삽입할 위치(pos)부터 리스트의 마지막 요소까지 모든 요소를 한 칸씩 뒤로 이동 (맨 뒤 요소부터 이동 시작)
  4. pos 위치에 새로운 요소 e를 저장
  5. num_todos를 1 증가
• 시간 복잡도: ($O(n)$)[[2]]

[[2]]: 맨 앞에 삽입하는 최악의 경우이다.

// 1. 삽입할 위치(pos) 이후의 할 일들을 한 칸씩 뒤로 민다.
//    (예: 3번째 할 일로 "새 회의 준비"를 추가하려면, 기존 3번째부터 마지막 할 일까지 뒤로 이동)
for (int i = num_todos - 1; i >= pos; i--) {
    todo_list[i + 1] = todo_list[i];
}
// 2. pos 위치에 새 할 일을 삽입한다.
todo_list[pos] = new_todo;
// 3. 전체 할 일 개수를 증가시킨다.
num_todos++;

삭제 연산: delete(pos)

• pos 위치의 요소를 삭제하고 반환
• 과정
  1. 리스트가 비었는지 확인 (언더플로우 체크)
  2. pos 위치가 유효한지 확인 (0 <= pos < num_todos)
  3. 삭제할 요소 e를 임시 변수에 저장 (반환용)
  4. 삭제된 위치(pos) 다음부터 리스트의 마지막 요소까지 모든 요소를 한 칸씩 앞으로 이동 (맨 앞 요소부터 이동 시작)
  5. num_todos를 1 감소
  6. 임시 변수에 저장된 e를 반환
• 시간 복잡도: $O(n)$[[3]]

[[3]]: 맨 앞을 삭제하는 최악의 경우이다.

// 1. 삭제할 할 일을 임시 저장한다.
TodoItem removed_todo = todo_list[pos];
// 2. 삭제할 위치(pos) 다음의 할 일들을 한 칸씩 앞으로 당긴다.
//    (예: 2번째 할 일 "점심 약속"을 삭제하면, 3번째 할 일부터 앞으로 이동)
for (int i = pos; i < num_todos - 1; i++) {
    todo_list[i] = todo_list[i + 1];
}
// 3. 전체 할 일 개수를 감소시킨다.
num_todos--;
// 4. 삭제된 할 일을 반환한다.
return removed_todo;

탐색 연산: get_entry(pos)

• pos 위치의 요소를 반환 (삭제하지 않음)
• 과정
  1. 리스트가 비었는지 확인
  2. pos 위치가 유효한지 확인
  3. todo_list[pos]를 반환
• 시간 복잡도: $O(1)$[[4]]

[[4]]: 배열은 인덱스로 직접 접근 가능하므로 즉시 연산 가능하다.

// pos 위치의 할 일을 바로 반환한다.
return todo_list[pos]; // ex) 0번 인덱스의 할 일 반환

배열 리스트 전체 구현

#include <stdio.h>
#include <string.h>

#define MAX_TODOS 5 // 예시를 위해 작은 크기로 설정
#define MAX_DESC_LEN 50

typedef struct {
    char description[MAX_DESC_LEN];
    int id; // 간단한 식별자
} TodoItem;

TodoItem todo_list[MAX_TODOS];
int num_todos = 0;
int next_id = 1; // ID 자동 부여용

// 리스트 초기화
void init_list() {
    num_todos = 0;
    next_id = 1;
}

// 리스트가 꽉 찼는지 검사
int is_full() {
    return num_todos == MAX_TODOS;
}

// 리스트가 비었는지 검사
int is_empty() {
    return num_todos == 0;
}

// 특정 위치에 할 일 추가
void add_todo_at(int pos, const char* desc) {
    if (is_full()) {
        printf("오류: 할 일 목록이 꽉 찼습니다!\n");
        return;
    }
    if (pos < 0 || pos > num_todos) { // 삽입은 size 위치까지 허용
        printf("오류: 잘못된 삽입 위치입니다!\n");
        return;
    }

    TodoItem new_todo;
    new_todo.id = next_id++;
    strncpy(new_todo.description, desc, MAX_DESC_LEN - 1);
    new_todo.description[MAX_DESC_LEN - 1] = '\0';

    for (int i = num_todos - 1; i >= pos; i--) {
        todo_list[i + 1] = todo_list[i];
    }
    todo_list[pos] = new_todo;
    num_todos++;
}

// 특정 위치의 할 일 삭제
TodoItem remove_todo_at(int pos) {
    TodoItem removed_item;
    removed_item.id = -1; // 오류 시 반환될 값
    if (is_empty()) {
        printf("오류: 할 일 목록이 비어있습니다!\n");
        return removed_item;
    }
    if (pos < 0 || pos >= num_todos) {
        printf("오류: 잘못된 삭제 위치입니다!\n");
        return removed_item;
    }

    removed_item = todo_list[pos];
    for (int i = pos; i < num_todos - 1; i++) {
        todo_list[i] = todo_list[i + 1];
    }
    num_todos--;
    return removed_item;
}

// 특정 위치의 할 일 가져오기
TodoItem get_todo_at(int pos) {
    TodoItem item;
    item.id = -1; // 오류 시 반환될 값
    if (is_empty() || pos < 0 || pos >= num_todos) {
        printf("오류: 잘못된 접근 위치이거나 목록이 비어있습니다!\n");
        return item;
    }
    return todo_list[pos];
}

// 전체 할 일 목록 출력
void print_todos(const char* title) {
    printf("%s [%d개]:\n", title, num_todos);
    if (is_empty()) {
        printf("  (비어 있음)\n");
        return;
    }
    for (int i = 0; i < num_todos; i++) {
        printf("  %d. [ID:%d] %s\n", i, todo_list[i].id, todo_list[i].description);
    }
    printf("\n");
}

int main() {
    init_list();
    print_todos("초기 상태");

    add_todo_at(0, "자료구조 공부"); // [자료구조 공부]
    add_todo_at(0, "모조 꽃받침 돌기"); // [모조 꽃받침 돌기, 자료구조 공부]
    add_todo_at(1, "차분화 우주 돌기"); // [모조 꽃받침 돌기, 차분화 우주 돌기, 자료구조 공부]
    print_todos("3개 추가 후");

    add_todo_at(num_todos, "저녁 메뉴 고르기"); // 맨 뒤에 추가
    add_todo_at(2, "산책하기");
    print_todos("총 5개 추가 후 (꽉 참)");

    add_todo_at(0, "추가 시도"); // 꽉 차서 실패해야 함

    TodoItem removed = remove_todo_at(2); // "산책하기" 삭제
    printf("삭제된 할 일: [ID:%d] %s\n", removed.id, removed.description);
    print_todos("1개 삭제 후");

    TodoItem item = get_todo_at(0);
    printf("0번 인덱스 할 일: [ID:%d] %s\n", item.id, item.description);

    return 0;
}

배열 리스트 추가 연산

추가 연산 정의

• append(e): 리스트 맨 뒤에 요소 e를 추가 ( insert(num_todos, e)와 동일 )
• pop(): 리스트 맨 뒤의 요소를 삭제하고 반환 ( delete(num_todos - 1)와 동일 )
• replace(pos, e): pos 위치의 요소를 e로 수정
• find(e): 리스트에서 요소 e를 찾아 그 위치(인덱스)를 반환

추가 연산 구현

// 맨 뒤에 할 일 추가
void append_todo(const char* desc) {
    add_todo_at(num_todos, desc); // ex) 현재 3개의 할 일이 있다면, 3번 인덱스(맨 뒤)에 추가
}

// 맨 뒤 할 일 삭제 및 반환
TodoItem pop_todo() {
    return remove_todo_at(num_todos - 1); // ex) 현재 3개의 할 일이 있다면, 2번 인덱스(맨 뒤) 삭제
}

// 특정 위치 할 일 내용 수정
void replace_todo(int pos, const char* new_desc) {
    if (is_empty() || pos < 0 || pos >= num_todos) {
        printf("오류: 잘못된 수정 위치이거나 목록이 비어있습니다!\n");
        return;
    }
    strncpy(todo_list[pos].description, new_desc, MAX_DESC_LEN - 1);
    todo_list[pos].description[MAX_DESC_LEN - 1] = '\0'; // ex) 0번 할 일 내용을 새 내용으로 변경
}

// 특정 ID를 가진 할 일 찾기
int find_todo_by_id(int id) {
    for (int i = 0; i < num_todos; i++) {
        if (todo_list[i].id == id) {
            return i; // ex) ID가 3인 할 일을 찾아 인덱스 반환
        }
    }
    return -1; // 찾지 못함
}

연결된 구조를 이용한 리스트

단순 연결 리스트 (Singly Linked List)

• 각 노드(Node)는 데이터와 다음 노드를 가리키는 링크(Link) (포인터)로 구성
• 노드들이 링크로 연결되어 사슬과 같은 구조를 형성
• 리스트의 첫 번째 노드는 헤드 포인터(Head Pointer)로 접근
• 마지막 노드의 링크 값은 NULL (더 이상 연결된 노드가 없음을 의미)

노드 구조체와 헤드 포인터

#include <stdlib.h> // malloc, free 사용

typedef struct {
    char title[100];
    char artist[50];
} SongData;

typedef struct PlaylistNode {
    SongData song;                // 저장할 노래 정보 (데이터 필드)
    struct PlaylistNode* next_song; // 다음 곡을 가리키는 포인터 (링크 필드)
} PlaylistNode;

PlaylistNode* playlist_head = NULL; // 재생 목록의 첫 번째 곡을 가리키는 헤드 포인터

• PlaylistNode* playlist_head = NULL;: 현재 재생 목록이 비어있음을 의미

연결 리스트 기본 연산

초기화: init()

• 헤드 포인터를 NULL로 설정
• playlist_head = NULL;: 재생 목록을 비움

상태 검사: is_empty(), is_full()

• is_empty(): 헤드 포인터가 NULL인지 확인
  • return playlist_head == NULL;: 헤드가 NULL이면 재생 목록이 비어있음
• is_full(): 동적 메모리 할당을 사용하므로, 이론적으로는 메모리가 허용하는 한 계속 추가 가능, 보통 FALSE를 반환

연결 리스트 크기 및 항목 참조

크기 연산: size()

• 헤드부터 시작하여 NULL을 만날 때까지 노드를 순회하며 개수를 셈
• 시간 복잡도: $O(n)$

int get_playlist_size() {
    int count = 0;
    PlaylistNode* current = playlist_head; // current 포인터로 재생 목록 순회
    while (current != NULL) {
        count++;
        current = current->next_song; // 다음 곡으로 이동
    }
    return count; // ex) 현재 재생 목록의 곡 수 반환
}

특정 위치 노드 찾기: get_node(pos)

• pos 위치(0부터 시작)에 있는 노드의 포인터를 반환
• 헤드부터 pos번 만큼 링크를 따라 이동
• 시간 복잡도: $O(n)$

PlaylistNode* get_song_node_at(int pos) {
    if (pos < 0) return NULL;
    PlaylistNode* current = playlist_head;
    for (int i = 0; i < pos && current != NULL; i++) {
        current = current->next_song; // ex) pos가 1이면, head에서 한 번 next_song으로 이동
    }
    return current; // 해당 위치의 노드 또는 NULL (위치가 범위를 벗어난 경우) 반환
}

특정 위치 데이터 가져오기: get_entry(pos)

• get_node(pos)를 호출하여 해당 위치의 노드를 찾은 후, 그 노드의 데이터 필드를 반환
• 시간 복잡도: $O(n)$

SongData get_song_data_at(int pos) {
    PlaylistNode* node = get_song_node_at(pos);
    SongData empty_song = {"", ""}; // 오류 시 반환할 빈 데이터
    if (node != NULL) {
        return node->song; // ex) 찾은 노드의 노래 정보 반환
    }
    return empty_song; // 또는 오류 처리
}

연결 리스트 추가 연산

항목 교체: replace(pos, e)

• get_node(pos)로 노드를 찾아 데이터만 교체
• 시간 복잡도: $O(n)$

void replace_song_at(int pos, SongData new_song_data) {
    PlaylistNode* node_to_replace = get_song_node_at(pos);
    if (node_to_replace != NULL) {
        node_to_replace->song = new_song_data; // ex) pos 위치 곡 정보를 new_song_data로 변경
    }
}

항목 탐색: find(e) (데이터 기반 탐색)

• 헤드부터 순회하며 데이터가 e와 일치하는 노드를 찾아 포인터 반환 (여기서는 곡 제목으로 탐색 예시)
• 시간 복잡도: $O(n)$

PlaylistNode* find_song_by_title(const char* title) {
    PlaylistNode* current = playlist_head;
    while (current != NULL) {
        if (strcmp(current->song.title, title) == 0) {
            return current; // ex) 제목이 일치하는 첫 번째 곡 노드 반환
        }
        current = current->next_song;
    }
    return NULL; // 해당 제목의 곡 없음
}

리스트 정리: clear_list()

• 모든 노드의 메모리를 해제하고 헤드 포인터를 NULL로 설정
• 시간 복잡도: $O(n)$

void clear_playlist() {
    PlaylistNode* current = playlist_head;
    PlaylistNode* next_node;
    while (current != NULL) {
        next_node = current->next_song; // 다음 노드 미리 저장
        free(current);                 // 현재 노드 메모리 해제
        current = next_node;           // 다음 노드로 이동
    }
    playlist_head = NULL; // 재생 목록 비우기 완료
}

삽입 연산: insert(pos, e)

• 새로운 노드를 생성하고 데이터를 저장한 후, 리스트의 pos 위치에 삽입

맨 앞에 삽입 (pos = 0)

1. 새 노드 생성 및 데이터 저장
2. 새 노드의 next_song이 기존 playlist_head를 가리키도록 설정
3. playlist_head가 새 노드를 가리키도록 변경

• 시간 복잡도: $O(1)$

예: 재생목록 맨 앞에 새 곡(P) 추가
초기: head -> B -> C -> NULL
1. 새 노드 P 생성: P [data|next_song=NULL]
2. P.next_song = head (현재 B): P -> B -> C -> NULL
3. head = P: head -> P -> B -> C -> NULL

중간 또는 맨 뒤에 삽입 (pos > 0)

1. pos-1 위치의 노드 (before_node)를 찾음 (만약 before_node가 NULL이면 잘못된 위치)
2. 새 노드 생성 및 데이터 저장
3. 새 노드의 next_song이 before_node의 next_song을 가리키도록 설정
4. before_node의 next_song이 새 노드를 가리키도록 변경

• 시간 복잡도: before_node 찾는 데 $O(n)$ 삽입 자체는 $O(1)$ 전체적으로 $O(n)$[[5]]

[[5]]: 만약 before_node를 이미 알고 있다면 $O(1)$

예: 곡 B와 C 사이에 새 곡(P) 추가 (pos=1, before_node는 B)
초기: head -> B -> C -> NULL
1. before_node (B) 찾기
2. 새 노드 P 생성: P [data|next_song=NULL]
3. P.next_song = before_node.next_song (현재 C): P -> C -> NULL
4. before_node.next_song = P: head -> B -> P -> C -> NULL

삭제 연산: delete(pos)

• pos 위치의 노드를 리스트에서 제거하고 메모리 해제 후 데이터 반환

맨 앞 노드 삭제 (pos = 0)

1. 삭제할 노드(removed_node)는 playlist_head (리스트가 비어있으면 안 됨)
2. playlist_head를 removed_node의 next_song으로 변경
3. removed_node의 메모리 해제 후 데이터 반환

• 시간 복잡도: $O(1)$

예: 재생목록 맨 앞 곡(P) 삭제
초기: head -> P -> B -> C -> NULL
1. removed_node = head (P)
2. head = removed_node.next_song (B): head -> B -> C -> NULL,  P는 홀로 남음
3. P 메모리 해제

중간 또는 맨 뒤 노드 삭제 (pos > 0)

1. pos-1 위치의 노드 (before_node)를 찾음
2. 삭제할 노드(removed_node)는 before_node의 next_song
   (만약 before_node나 removed_node가 NULL이면 잘못된 위치)
3. before_node의 next_song을 removed_node의 next_song으로 변경
   (삭제할 노드를 건너뛰어 연결)
4. removed_node의 메모리 해제 후 데이터 반환

• 시간 복잡도: before_node 찾는 데 $O(n)$, 삭제 자체는 $O(1)$ [[6]]

[[6]]: 만약 before_node를 이미 알고 있다면 $O(1)$이다.

예: 곡 P 삭제 (A -> P -> B 상황에서, before_node는 A)
초기: head -> A -> P -> B -> NULL
1. before_node (A) 찾기
2. removed_node = before_node.next_song (P)
3. before_node.next_song = removed_node.next_song (B): head -> A -> B -> NULL, P는 홀로 남음
4. P 메모리 해제

단순 연결 리스트 전체 구현

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// SongData, PlaylistNode 구조체 정의는 위에 있음

// (함수 프로토타입들)
void init_playlist();
int is_playlist_empty();
void add_song_at(int pos, SongData data);
SongData remove_song_at(int pos);
void print_playlist(const char* title);
// ... (get_playlist_size, get_song_node_at 등 다른 함수들도 필요)

void init_playlist() {
    // clear_playlist를 호출하여 기존 목록이 있다면 정리
    PlaylistNode* current = playlist_head;
    PlaylistNode* next_node;
    while (current != NULL) {
        next_node = current->next_song;
        free(current);
        current = next_node;
    }
    playlist_head = NULL;
}

int is_playlist_empty() {
    return playlist_head == NULL;
}

// PlaylistNode* get_song_node_at(int pos) 함수는 위에 정의됨

void add_song_at(int pos, SongData data) {
    if (pos < 0) {
        printf("오류: 잘못된 삽입 위치입니다.\n");
        return;
    }

    PlaylistNode* new_node = (PlaylistNode*)malloc(sizeof(PlaylistNode));
    if (new_node == NULL) {
        printf("오류: 메모리 할당 실패!\n");
        return;
    }
    new_node->song = data;
    new_node->next_song = NULL;

    if (pos == 0) { // 맨 앞에 삽입
        new_node->next_song = playlist_head;
        playlist_head = new_node;
    } else { // 중간 또는 맨 뒤에 삽입
        PlaylistNode* before_node = get_song_node_at(pos - 1);
        if (before_node == NULL) {
            printf("오류: 삽입 위치의 이전 노드를 찾을 수 없습니다 (pos=%d).\n", pos);
            free(new_node); // 할당된 메모리 해제
            return;
        }
        new_node->next_song = before_node->next_song;
        before_node->next_song = new_node;
    }
}

SongData remove_song_at(int pos) {
    SongData removed_song_data = {"<삭제실패>", ""}; // 실패 시 반환될 값
    if (is_playlist_empty() || pos < 0) {
        printf("오류: 재생 목록이 비었거나 잘못된 삭제 위치입니다.\n");
        return removed_song_data;
    }

    PlaylistNode* removed_node = NULL;
    if (pos == 0) { // 맨 앞 노드 삭제
        removed_node = playlist_head;
        playlist_head = removed_node->next_song;
    } else { // 중간 또는 맨 뒤 노드 삭제
        PlaylistNode* before_node = get_song_node_at(pos - 1);
        if (before_node == NULL || before_node->next_song == NULL) {
            printf("오류: 삭제할 노드 또는 그 이전 노드를 찾을 수 없습니다 (pos=%d).\n", pos);
            return removed_song_data;
        }
        removed_node = before_node->next_song;
        before_node->next_song = removed_node->next_song;
    }

    if (removed_node != NULL) {
        removed_song_data = removed_node->song;
        free(removed_node);
    }
    return removed_song_data;
}

void print_playlist(const char* title) {
    printf("%s\n", title);
    if (is_playlist_empty()) {
        printf("  (재생 목록 비어 있음)\n");
        return;
    }
    PlaylistNode* current = playlist_head;
    int i = 0;
    while (current != NULL) {
        printf("  %d. \"%s\" - %s\n", i++, current->song.title, current->song.artist);
        current = current->next_song;
    }
    printf("\n");
}

int main() {
    init_playlist();
    print_playlist("초기 재생 목록 상태");

    SongData song1 = {"Bohemian Rhapsody", "Queen"};
    SongData song2 = {"Imagine", "John Lennon"};
    SongData song3 = {"Stairway to Heaven", "Led Zeppelin"};
    SongData song4 = {"Like a Rolling Stone", "Bob Dylan"};

    add_song_at(0, song1); // [Queen]
    add_song_at(0, song2); // [Lennon, Queen]
    add_song_at(1, song3); // [Lennon, Led Zeppelin, Queen]
    print_playlist("3곡 추가 후");

    // get_playlist_size() 와 같은 함수를 호출하여 크기 확인 가능
    // int current_size = get_playlist_size(); printf("현재 곡 수: %d\n", current_size);

    add_song_at(get_playlist_size(), song4); // 맨 뒤에 추가 (size() 함수 필요)
    print_playlist("맨 뒤에 1곡 추가 후");


    SongData removed = remove_song_at(1); // "Led Zeppelin" 삭제
    printf("삭제된 곡: \"%s\" - %s\n", removed.title, removed.artist);
    print_playlist("1곡 삭제 후");

    // 프로그램 종료 전 할당된 모든 노드 메모리 해제
    init_playlist(); // 여기서는 init_playlist가 clear 기능도 겸함

    return 0;
}

헤드 포인터와 헤드 노드

헤드 노드 (Head Node)

• 리스트의 실제 데이터 시작 부분 앞에 위치하는 특별한 노드
• 데이터 필드는 사용되지 않거나 리스트 전체에 대한 정보(리스트 크기)를 저장하는 데 사용될 수 있음
• 실제 리스트의 첫 번째 데이터 노드는 헤드 노드의 link(또는 next)가 가리킴

헤드 노드 사용의 이점

• 삽입/삭제 로직 간소화: 맨 앞 노드에 대한 특별한 경우(if-else)를 줄일 수 있음
  예를 들어, 삽입 시 항상 before_node->link = new_node; 와 같은 형태로 처리 가능 (맨 앞 삽입 시 before_node는 헤드 노드)

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

• 단순 연결 리스트는 다음 노드로만 이동 가능함. 따라서 이전 노드로 돌아가기 어려움 (다시 처음부터 검색)
• 특정 노드의 선행 노드를 쉽게 찾을 수 있다면 연산이 더 편리해짐

이중 연결 리스트 노드 구조

• 각 노드는 데이터 필드 외에 두 개의 링크 필드를 가짐
  • prev: 이전 노드를 가리키는 포인터
  • next: 다음 노드를 가리키는 포인터
• 헤드 노드의 prev는 NULL, 마지막 노드의 next는 NULL [[7]]

[[7]]: 원형 이중 연결 리스트에서는 헤드 노드와 마지막 노드가 연결된다.

typedef struct {
    char url[256];
    char title[100];
} WebPageData;

typedef struct BrowserHistoryNode {
    WebPageData page;                     // 현재 웹 페이지 정보
    struct BrowserHistoryNode* prev_page; // 이전 방문 페이지 노드
    struct BrowserHistoryNode* next_page; // 다음 방문 페이지 노드
} BrowserHistoryNode;

// 헤드 노드(더미 노드) 사용 방식
BrowserHistoryNode history_head_node; // 헤드 노드. history_head_node.next_page가 실제 첫 방문 기록.
                                    // history_head_node.prev_page는 보통 NULL 또는 마지막 노드(원형)

// 초기화 시 (헤드 노드 사용)
// history_head_node.next_page = NULL; (또는 원형이면 자기 자신을 가리킴)
// history_head_node.prev_page = NULL; (또는 원형이면 자기 자신을 가리킴)

• p == p->next_page->prev_page: p가 마지막 노드가 아닐 때
• p == p->prev_page->next_page: p가 첫 노드가 아닐 때

이중 연결 리스트와 헤드 노드

• 단순 연결 리스트와 마찬가지로, 이중 연결 리스트도 헤드 노드(더미 노드)를 사용하면 구현이 간결해지는 경우가 많음
• 헤드 노드 org를 사용하면, org.next가 실제 첫 번째 데이터 노드를, org.prev는 NULL(또는 원형일 경우 마지막 노드)을 가리킴
• 모든 데이터 노드는 유효한 prev와 next를 가짐 (리스트의 양 끝 노드의 prev 또는 next는 헤드 노드를 가리키거나 NULL이 됨)

이중 연결 리스트 연산

특정 위치 노드 참조: get_node(pos)

• history_head_node.next_page 부터 시작하여 pos번 만큼 next_page 링크를 따라 이동

BrowserHistoryNode* get_history_node_at(int pos) {
    if (pos < 0) return NULL;
    // 헤드 노드의 다음 노드(실제 첫번째 데이터 노드)부터 시작
    BrowserHistoryNode* current = history_head_node.next_page;
    for (int i = 0; i < pos && current != NULL; i++) {
        current = current->next_page;
    }
    return current;
}

삽입 연산: insert(pos, e)

• pos 위치에 새 페이지 e를 삽입
• before_node는 pos-1 위치의 노드
  (만약 pos=0이면 before_node는 헤드 노드 history_head_node)

1. 새 노드 p 생성 및 데이터 저장
2. p->next_page = before_node->next_page;
3. p->prev_page = before_node;
4. 만약 before_node->next_page (원래 p 다음에 올 노드)가 NULL이 아니었다면, (before_node->next_page)->prev_page = p;
5. before_node->next_page = p;

• 시간 복잡도: before_node를 찾는데 $O(n)$, before_node를 알고 있는 경우[[8]] $O(1)$

[[8]]: pos=0이라 헤드노드가 before 역할인 경우

삭제 연산: delete(pos)

• pos 위치의 노드 p를 삭제

1. 삭제할 노드 p = get_history_node_at(pos) (p가 NULL이면 오류)
2. p->prev_page->next_page = p->next_page; (p의 이전 노드가 p의 다음 노드를 가리킴)
3. 만약 p->next_page가 NULL이 아니었다면, p->next_page->prev_page = p->prev_page; (p의 다음 노드가 p의 이전 노드를 가리킴)
4. p 메모리 해제 후 데이터 반환

• 시간 복잡도: 삭제할 노드 p를 안다면 $O(1)$, 찾는 시간 포함 시 $O(n)$

이중 연결 리스트 전체 구현

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// WebPageData, BrowserHistoryNode 구조체 정의는 위에 있음
// BrowserHistoryNode history_head_node; // 전역 헤드 노드 선언 또는 main에서 관리

// 헤드 노드를 사용한 이중 연결 리스트 초기화
void init_history_list(BrowserHistoryNode* head_node) {
    head_node->prev_page = NULL; // 또는 원형이면 head_node 자신
    head_node->next_page = NULL; // 또는 원형이면 head_node 자신
    // head_node->page는 사용 안 함 (더미 데이터)
}

// BrowserHistoryNode* get_history_node_at(BrowserHistoryNode* head_node, int pos) 함수는 위와 유사하게 구현 (head_node를 인자로 받도록 수정)

// 삽입 (헤드 노드를 인자로 받음)
void add_history_page_at(BrowserHistoryNode* head_node, int pos, WebPageData data) {
    if (pos < 0) { /* 오류 처리 */ return; }

    BrowserHistoryNode* new_page_node = (BrowserHistoryNode*)malloc(sizeof(BrowserHistoryNode));
    if (!new_page_node) { /* 메모리 할당 오류 처리 */ return; }
    new_page_node->page = data;

    BrowserHistoryNode* before_node = head_node; // pos=0일 때, before_node는 헤드 노드
    if (pos > 0) {
        before_node = get_history_node_at(pos-1); // 실제 get_node는 head_node를 인자로 받도록 수정 필요
                                                     // 여기서는 간략화 위해 전역 head_node 기준으로 설명
                                                     // BrowserHistoryNode* current = head_node->next_page;
                                                     // for (int i = 0; i < pos - 1 && current != NULL; i++) current = current->next_page;
                                                     // before_node = current;
        if(before_node == NULL) { /* 오류: pos-1 위치 없음. free(new_page_node); return; */ }
    }
    
    // 연결 작업
    new_page_node->next_page = before_node->next_page;
    new_page_node->prev_page = before_node;
    if (before_node->next_page != NULL) {
        before_node->next_page->prev_page = new_page_node;
    }
    before_node->next_page = new_page_node;
}

// 삭제 (헤드 노드를 인자로 받음)
WebPageData remove_history_page_at(BrowserHistoryNode* head_node, int pos) {
    WebPageData removed_page_data = {"<삭제실패>", ""};
    if (pos < 0 || head_node->next_page == NULL /*리스트 비어있음*/) { /* 오류 처리 */ return removed_page_data; }

    BrowserHistoryNode* node_to_remove = get_history_node_at(pos); // 실제 get_node는 head_node를 인자로 받도록 수정 필요
                                                                      // BrowserHistoryNode* current = head_node->next_page;
                                                                      // for (int i = 0; i < pos && current != NULL; i++) current = current->next_page;
                                                                      // node_to_remove = current;

    if (node_to_remove == NULL) { /* 오류: 삭제할 노드 없음 */ return removed_page_data; }

    // 연결 해제 작업
    node_to_remove->prev_page->next_page = node_to_remove->next_page;
    if (node_to_remove->next_page != NULL) {
        node_to_remove->next_page->prev_page = node_to_remove->prev_page;
    }

    removed_page_data = node_to_remove->page;
    free(node_to_remove);
    return removed_page_data;
}

void print_history(BrowserHistoryNode* head_node, const char* title) {
    printf("%s\n", title);
    BrowserHistoryNode* current = head_node->next_page; // 실제 데이터는 헤드 노드의 다음부터
    if (current == NULL) {
        printf("  (방문 기록 비어 있음)\n");
        return;
    }
    int i = 0;
    while (current != NULL) {
        printf("  %d. [%s] %s (prev: %s, next: %s)\n", i++,
               current->page.url, current->page.title,
               (current->prev_page == head_node || current->prev_page == NULL) ? "HEAD" : current->prev_page->page.title, // prev_page가 헤드노드면 "HEAD"
               (current->next_page == NULL) ? "NULL" : current->next_page->page.title);
        current = current->next_page;
    }
    printf("\n");
}

Lab: 이중 연결 구조 기반 덱(Deque) 연산 구현

• 덱(Deque: Double-Ended Queue)은 리스트의 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조
• 이중 연결 리스트는 덱을 구현하기에 매우 적합 (맨 앞/뒤 접근이 $O(1)$ - 헤드/테일 포인터 또는 헤드노드 사용 시)

후단 삭제: delete_rear() (덱의 연산 중 하나)

• 이중 연결 리스트의 마지막 노드를 삭제 (헤드 노드와 별개로 테일 포인터가 있거나, 헤드 노드만으로 관리한다면 마지막 노드를 찾아야 함, 여기서는 헤드/테일 포인터 또는 헤드노드를 활용해 $O(1)$ 가능한 구조 가정)
• 만약 front와 rear 포인터 (또는 헤드 노드와 연결된 첫 노드와 마지막 노드)를 관리한다면
  1. 리스트가 비었는지 확인
  2. 삭제할 노드 p = rear
  3. 만약 front == rear (요소가 하나뿐): front = rear = NULL
  4. 아니면: rear = rear->prev; rear->next = NULL;
  5. p 메모리 해제, 데이터 반환
• 시간 복잡도: rear 포인터를 유지하고 있는 경우 $O(1)$

// Deque 구현을 위한 DNode (이전 BrowserHistoryNode와 유사)
DNode* front, *rear; // 덱의 양 끝을 가리키는 포인터

Element delete_rear() {
   if (is_empty()) error("Deque is empty");
   DNode* p = rear;
   Element item = p->data;
   if (front == rear) { // 요소가 하나뿐인 경우
       free(p);
       front = rear = NULL;
   } else {
       rear = rear->prev;
       rear->next = NULL;
       free(p);
   }
   return item;
}

리스트 응용: 맛집 웨이팅 프로그램

• 맛집에 도착한 손님들이 대기 순서에 따라 리스트에 등록
• 직원은 리스트 순서대로 손님을 호출
• 손님은 자기 순서를 확인하거나, 웨이팅을 취소하거나, 순서를 뒤로 미룰 수 있음
• 이중 연결 리스트를 사용하면 순서 변경(뒤로 밀기), 중간 취소 등이 효율적

맛집 웨이팅 프로그램 기능 정의

1. reserve(nperson, info): 새로운 웨이팅 등록 (인원수, 전화번호 등 정보) 리스트 맨 뒤에 추가
2. find(wid): 웨이팅 번호(wid)로 현재 대기 순서(앞에 몇 팀, 몇 명) 확인
3. cancel(wid): 웨이팅 번호(wid)로 등록된 웨이팅 취소. 리스트에서 해당 손님 삭제
4. delay(wid): 웨이팅 번호(wid)의 손님 순서를 한 칸 뒤로 미룸 (해당 노드를 다음 노드 뒤로 이동)
5. print(): 전체 웨이팅 리스트 출력
6. service(): 맨 앞 손님 입장 처리. 리스트에서 맨 앞 손님 삭제

맛집 웨이팅 프로그램 구현

웨이팅 정보 구조체 및 리스트 초기화

// DblLinkedList.h 에 이중 연결 리스트 구현이 있다고 가정
// 여기서는 필요한 함수만 간략히 정의하거나 설명을 위해 직접 작성

typedef struct {
    int id;         // 대기번호 (자동 부여)
    int nperson;    // 인원수
    char info[32];  // 전화번호 등 기타 정보
} WaitingInfo;      // Element 타입으로 사용

// 이중 연결 리스트의 노드 구조 (DNode)
typedef struct DNode {
    WaitingInfo data;
    struct DNode* prev;
    struct DNode* next;
} DNode;

DNode head_node; // 헤드 노드(더미 노드) 사용
int waiting_id_counter = 0; // 대기번호 자동 증가용

void init_waiting_list() {
    head_node.prev = &head_node; // 원형으로 초기화 (공백 시 자신을 가리킴)
    head_node.next = &head_node; // 원형으로 초기화
    waiting_id_counter = 0;
}
// 실제 size() 함수는 헤드 노드를 제외하고 세어야 함.
int get_waiting_list_size() {
    int count = 0;
    DNode* current = head_node.next;
    while(current != &head_node) { // 원형이므로 헤드 노드로 돌아오면 끝
        count++;
        current = current->next;
    }
    return count;
}

새로운 웨이팅 등록: reserve(nperson, info)

• 리스트의 맨 뒤에 추가

void reserve(int nperson, const char* info_str) {
    DNode* new_node = (DNode*)malloc(sizeof(DNode));
    if (!new_node) { /* 오류 처리 */ return; }

    new_node->data.id = ++waiting_id_counter;
    new_node->data.nperson = nperson;
    strncpy(new_node->data.info, info_str, sizeof(new_node->data.info) - 1);
    new_node->data.info[sizeof(new_node->data.info) - 1] = '\0';

    // 헤드 노드의 이전에 삽입 (원형이므로 맨 뒤에 해당)
    DNode* tail_prev = head_node.prev; // 현재 실제 마지막 노드

    new_node->next = &head_node;    // 새 노드의 다음은 헤드
    new_node->prev = tail_prev;     // 새 노드의 이전은 기존 마지막 노드
    tail_prev->next = new_node;     // 기존 마지막 노드의 다음은 새 노드
    head_node.prev = new_node;      // 헤드의 이전은 새 노드 (새로운 마지막 노드)

    printf("<등록> 번호 %d: 인원 %d명 %s\n", new_node->data.id, nperson, info_str);
}

웨이팅 순서 확인: find(wid)

void find_waiting_info(int wid) {
    DNode* current = head_node.next;
    int team_count = 0;
    int people_count = 0;
    while (current != &head_node) {
        if (current->data.id == wid) {
            printf("<확인> 번호 %d번 앞 대기팀: %d팀 %d명\n", wid, team_count, people_count);
            return;
        }
        team_count++;
        people_count += current->data.nperson;
        current = current->next;
    }
    printf("<확인> 번호 %d번을 찾을 수 없습니다.\n", wid);
}

웨이팅 취소: cancel(wid)

void cancel_waiting(int wid) {
    DNode* current = head_node.next;
    while (current != &head_node) {
        if (current->data.id == wid) {
            current->prev->next = current->next; // 이전 노드가 다음 노드를 가리킴
            current->next->prev = current->prev; // 다음 노드가 이전 노드를 가리킴
            printf("<취소> %d번 웨이팅이 취소되었습니다.\n", wid);
            free(current);
            return;
        }
        current = current->next;
    }
    printf("<취소> %d번 웨이팅을 찾을 수 없습니다.\n", wid);
}

웨이팅 순서 뒤로 밀기: delay(wid)

• wid 손님을 찾아, 그 다음 손님이 있다면 그 뒤로 이동 (한 칸만 미룸)

void delay_waiting(int wid) {
    DNode* target_node = NULL;
    DNode* current = head_node.next;
    while(current != &head_node) { // target_node 찾기
        if(current->data.id == wid) {
            target_node = current;
            break;
        }
        current = current->next;
    }

    if (target_node == NULL) {
        printf("<연기> %d번 웨이팅을 찾을 수 없습니다.\n", wid);
        return;
    }

    // 이미 맨 뒤거나, 뒤에 노드가 헤드노드(즉, 맨 뒤)면 연기 불가
    if (target_node->next == &head_node) {
        printf("<연기> %d번은 이미 마지막 순서라 연기할 수 없습니다.\n", wid);
        return;
    }

    DNode* node_after_target = target_node->next; // target 바로 다음 노드

    // 1. target_node를 리스트에서 분리
    target_node->prev->next = target_node->next;
    target_node->next->prev = target_node->prev;

    // 2. target_node를 node_after_target 뒤에 삽입
    target_node->next = node_after_target->next;
    target_node->prev = node_after_target;
    node_after_target->next->prev = target_node;
    node_after_target->next = target_node;

    printf("<연기> %d번 웨이팅이 한 칸 연기되었습니다.\n", wid);
}

전체 웨이팅 리스트 출력: print_waitings() & 손님 입장 처리: service()

void print_waitings() {
    printf("[현재 대기 상황]\n");
    DNode* current = head_node.next;
    if (current == &head_node) {
        printf("  (대기 손님 없음)\n");
        return;
    }
    while (current != &head_node) {
        printf("  번호 %d: %d명 (%s)\n", current->data.id, current->data.nperson, current->data.info);
        current = current->next;
    }
}

void service_customer() {
    if (head_node.next == &head_node) { // 비어있음
        printf("<입장> 대기 손님이 없습니다.\n");
        return;
    }
    DNode* first_customer_node = head_node.next; // 첫 번째 손님
    WaitingInfo serviced_customer = first_customer_node->data;

    // 첫 번째 손님 삭제
    head_node.next = first_customer_node->next;
    first_customer_node->next->prev = &head_node;
    free(first_customer_node);

    printf("<입장> %d번 손님 입장 (%d명, %s)\n", serviced_customer.id, serviced_customer.nperson, serviced_customer.info);
}

레퍼런스

“이 글은 『쉽게 배우는 C 자료구조』(최영규 및 천인국, 2024)의 내용을 토대로 재구성된 자료입니다.”​