C언어로 링크드 리스트 이해하기: 기본 개념과 구조

링크드 리스트는 C언어의 주요 자료 구조로, 메모리를 동적으로 관리하며 데이터 삽입과 삭제를 효율적으로 처리할 수 있는 구조입니다. 배열과 달리 고정 크기가 없어 유연하며, 노드라는 개별 요소를 연결해 데이터를 저장합니다. 본 기사에서는 링크드 리스트의 기본 개념과 구조, 다양한 형태 및 구현 방법을 체계적으로 살펴보겠습니다.

링크드 리스트의 개념

링크드 리스트(linked list)는 데이터를 저장하는 노드들이 체인 형태로 연결된 동적 자료 구조입니다. 각 노드는 데이터를 저장하는 데이터 필드와 다음 노드를 가리키는 포인터 필드로 구성됩니다.

링크드 리스트의 특징

동적 메모리 사용: 필요할 때마다 메모리를 할당하므로 메모리 사용이 유연합니다.
크기 제한 없음: 배열처럼 초기 크기를 정의하지 않아도 됩니다.
빠른 삽입과 삭제: 노드 추가나 제거가 인덱스 이동 없이 가능해 효율적입니다.

링크드 리스트와 배열의 비교

특징	링크드 리스트	배열
메모리 할당 방식	동적 할당	고정 크기
데이터 접근	순차적 접근	임의 접근 가능
삽입/삭제	O(1) (노드 참조 시)	O(n) (이동 필요)

링크드 리스트는 데이터가 동적으로 변하는 환경에서 배열보다 유리하지만, 순차 접근만 가능하다는 점이 단점으로 작용할 수 있습니다.

노드의 구조

링크드 리스트의 핵심 구성 요소는 노드입니다. 노드는 데이터를 저장하고 다른 노드와 연결되는 역할을 합니다.

노드의 기본 구성

노드는 두 가지 주요 필드로 이루어집니다.

데이터 필드: 저장할 데이터를 포함합니다.
포인터 필드: 다음 노드를 가리키는 포인터를 저장합니다.

노드 구조의 C언어 구현

노드는 일반적으로 struct를 사용하여 정의됩니다.

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

struct Node {
    int data;              // 데이터 필드
    struct Node* next;     // 포인터 필드
};

메모리 할당

노드는 동적으로 메모리를 할당받아야 합니다. 이는 링크드 리스트가 유연성을 가지게 하는 중요한 특징입니다.

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 10;
newNode->next = NULL;  // 다음 노드를 가리키지 않음 (현재는 마지막 노드)

노드 간의 연결

각 노드의 next 포인터를 이용해 다른 노드와 연결하여 링크드 리스트를 구성합니다.

struct Node* head = newNode; // 첫 번째 노드
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
second->data = 20;
second->next = NULL;

head->next = second; // 첫 번째 노드가 두 번째 노드를 가리킴

노드의 유연성

이 구조는 다양한 크기의 데이터 구조를 만들 수 있는 유연성을 제공합니다. 단일 노드뿐만 아니라, 다른 구조체를 포함하거나 복잡한 데이터도 저장할 수 있습니다.

struct ComplexNode {
    int id;
    char name[50];
    struct ComplexNode* next;
};

노드는 링크드 리스트의 기본 구성 요소로, 이들 간의 연결을 통해 전체 데이터 구조가 형성됩니다.

단일 링크드 리스트

단일 링크드 리스트(Singly Linked List)는 각 노드가 다음 노드의 주소를 저장하며 한 방향으로만 연결된 형태의 자료 구조입니다.

단일 링크드 리스트의 구조

단일 링크드 리스트의 첫 번째 노드는 헤드(Head)라 불리며, 리스트의 시작점을 나타냅니다. 마지막 노드의 포인터는 NULL을 가리켜 리스트의 끝을 표시합니다.

단일 링크드 리스트의 구현

1. 리스트 초기화
빈 리스트는 NULL 값을 가진 헤드 포인터로 초기화됩니다.

struct Node* head = NULL;

2. 노드 추가
노드를 리스트의 맨 앞이나 맨 뒤에 추가할 수 있습니다.

맨 앞에 추가

void insertAtHead(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = *head; // 기존 헤드를 다음 노드로 설정
    *head = newNode;       // 헤드를 새로운 노드로 변경
}

맨 뒤에 추가

void insertAtEnd(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode; // 리스트가 비어 있으면 새로운 노드를 헤드로 설정
        return;
    }

    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

3. 리스트 출력
리스트를 순차적으로 순회하며 데이터를 출력합니다.

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

단일 링크드 리스트의 장점

동적 메모리 활용으로 유연성 제공
삽입과 삭제가 O(1)의 시간 복잡도로 효율적 (헤드에서 수행 시)

단일 링크드 리스트의 단점

역방향 순회가 불가능
삽입/삭제 시 특정 위치를 찾으려면 O(n)의 시간 소요

단일 링크드 리스트는 기본적이고 간단하지만, 방향성이 고정되어 있다는 제한이 있습니다. 이 구조는 삽입과 삭제가 빈번한 애플리케이션에 적합합니다.

이중 링크드 리스트

이중 링크드 리스트(Doubly Linked List)는 각 노드가 두 개의 포인터를 가지며, 하나는 이전 노드를 가리키고 다른 하나는 다음 노드를 가리키는 자료 구조입니다. 이를 통해 양방향 탐색이 가능해집니다.

이중 링크드 리스트의 구조

각 노드는 세 가지 요소로 구성됩니다.

데이터 필드: 저장할 데이터를 포함합니다.
이전 포인터(prev): 이전 노드를 가리킵니다.
다음 포인터(next): 다음 노드를 가리킵니다.

이중 링크드 리스트의 구현

1. 노드 정의

struct Node {
    int data;
    struct Node* prev; // 이전 노드를 가리키는 포인터
    struct Node* next; // 다음 노드를 가리키는 포인터
};

2. 노드 삽입

맨 앞에 삽입

void insertAtHead(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->prev = NULL;
    newNode->next = *head;

    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    *head = newNode;
}

맨 뒤에 삽입

void insertAtEnd(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = NULL;

    if (*head == NULL) {
        newNode->prev = NULL;
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

3. 리스트 출력
양방향으로 탐색 및 출력이 가능합니다.

정방향 출력

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

역방향 출력

void printReverse(struct Node* head) {
    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

이중 링크드 리스트의 장점

양방향 탐색 가능
노드 삭제 시 이전 노드 정보를 빠르게 접근 가능

이중 링크드 리스트의 단점

단일 링크드 리스트에 비해 더 많은 메모리 사용 (추가 포인터 필요)
구현 및 관리 복잡성 증가

이중 링크드 리스트는 양방향 탐색이 필요한 애플리케이션에서 유용하며, 삽입 및 삭제가 효율적으로 수행됩니다.

원형 링크드 리스트

원형 링크드 리스트(Circular Linked List)는 마지막 노드가 첫 번째 노드를 가리키도록 설계된 자료 구조입니다. 이로 인해 리스트는 논리적으로 끝이 없는 원형 형태를 이루게 됩니다.

원형 링크드 리스트의 구조

원형 링크드 리스트는 단일 또는 이중 링크드 리스트와 유사하지만, 마지막 노드의 포인터가 NULL이 아닌 첫 번째 노드를 가리킨다는 점이 다릅니다.

단일 원형 링크드 리스트: 각 노드가 다음 노드만 가리킵니다.
이중 원형 링크드 리스트: 각 노드가 이전 및 다음 노드를 가리킵니다.

단일 원형 링크드 리스트의 구현

1. 노드 정의

struct Node {
    int data;
    struct Node* next; // 다음 노드를 가리키는 포인터
};

2. 노드 삽입

맨 뒤에 삽입

void insertAtEnd(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;

    if (*head == NULL) {
        newNode->next = newNode; // 자기 자신을 가리킴
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head; // 마지막 노드가 첫 번째 노드를 가리킴
}

3. 리스트 출력
원형 리스트는 끝이 없으므로, 다시 헤드에 도달하면 순회를 멈춥니다.

void printList(struct Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }

    struct Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("HEAD\n");
}

원형 링크드 리스트의 장점

반복적 순회: 리스트의 끝에서 다시 시작점으로 쉽게 이동 가능.
효율적 메모리 사용: 리스트 전체를 순회하기 쉬움.
항상 연결된 구조: 동적으로 크기를 조정하면서도 논리적 연결이 유지됨.

원형 링크드 리스트의 단점

구현이 비교적 복잡함.
무한 루프에 빠질 가능성 있음 (순회 조건 실수 시).

원형 링크드 리스트의 활용 사례

라운드로빈 스케줄링: 프로세스나 작업을 순차적으로 반복할 때 사용.
버퍼 관리: 순환 버퍼에서 데이터를 처리할 때 유용.

원형 링크드 리스트는 끝이 없는 데이터 흐름을 처리하거나 반복적인 작업을 수행하는 애플리케이션에서 매우 적합한 자료 구조입니다.

링크드 리스트의 삽입과 삭제

링크드 리스트에서 데이터를 삽입하거나 삭제하는 작업은 동적 메모리를 활용하는 자료 구조의 핵심입니다. 이 과정은 단일, 이중, 원형 링크드 리스트 모두에 적용되며, 위치에 따라 구현 방식이 달라집니다.

삽입 작업

1. 맨 앞에 삽입
리스트의 헤드 포인터를 새 노드로 변경하고, 기존 헤드를 새 노드의 next에 연결합니다.

void insertAtHead(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = *head;
    *head = newNode;
}

2. 특정 위치에 삽입
특정 위치에 삽입하려면 해당 위치 이전 노드를 찾아야 합니다.

void insertAtPosition(struct Node** head, int position, int newData) {
    if (position == 0) {
        insertAtHead(head, newData);
        return;
    }

    struct Node* temp = *head;
    for (int i = 0; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL) return; // 잘못된 위치

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = temp->next;
    temp->next = newNode;
}

3. 맨 뒤에 삽입
마지막 노드의 next를 새 노드로 설정하고, 새 노드의 next를 NULL로 설정합니다.

void insertAtEnd(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

삭제 작업

1. 맨 앞에서 삭제
헤드 포인터를 다음 노드로 변경하고, 기존 헤드를 메모리에서 해제합니다.

void deleteAtHead(struct Node** head) {
    if (*head == NULL) return;

    struct Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

2. 특정 위치에서 삭제
삭제하려는 노드 이전 노드의 next를 삭제할 노드의 next로 설정합니다.

void deleteAtPosition(struct Node** head, int position) {
    if (*head == NULL) return;

    struct Node* temp = *head;

    if (position == 0) {
        *head = temp->next;
        free(temp);
        return;
    }

    for (int i = 0; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL) return;

    struct Node* nextNode = temp->next->next;
    free(temp->next);
    temp->next = nextNode;
}

3. 맨 뒤에서 삭제
마지막 노드를 찾고, 이전 노드의 next를 NULL로 설정한 후 메모리에서 해제합니다.

void deleteAtEnd(struct Node** head) {
    if (*head == NULL) return;

    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }

    struct Node* temp = *head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}

삽입과 삭제의 효율성

삽입과 삭제는 링크드 리스트의 장점 중 하나로, 특정 위치에서 O(1)의 시간 복잡도를 가집니다(노드를 미리 참조한 경우).
그러나 삽입/삭제할 위치를 찾는 작업은 O(n)의 시간 복잡도를 가질 수 있습니다.

효율적인 삽입과 삭제는 링크드 리스트를 활용한 프로그램 성능 향상에 필수적입니다. 이를 통해 동적 데이터를 효과적으로 관리할 수 있습니다.

링크드 리스트의 활용 예시

링크드 리스트는 유연성과 효율성을 기반으로 다양한 실제 문제 해결에 사용됩니다. 여기서는 링크드 리스트의 응용 사례를 살펴보겠습니다.

1. 메모리 효율적인 동적 데이터 관리

링크드 리스트는 동적 메모리 할당을 통해 데이터 크기를 유연하게 조정할 수 있습니다.

응용 분야: 운영 체제의 메모리 관리, 동적 배열 구현
예시 코드:

  struct Node {
      int data;
      struct Node* next;
  };

  void addProcess(struct Node** processList, int processID) {
      struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
      newNode->data = processID;
      newNode->next = *processList;
      *processList = newNode;
  }

2. 큐 및 스택 구현

링크드 리스트는 큐와 스택 같은 선형 자료 구조를 구현하는 데 자주 사용됩니다.

큐: FIFO(First In First Out) 방식 구현
스택: LIFO(Last In First Out) 방식 구현
예시 코드 (스택):

  struct Stack {
      struct Node* top;
  };

  void push(struct Stack* stack, int value) {
      struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
      newNode->data = value;
      newNode->next = stack->top;
      stack->top = newNode;
  }

  int pop(struct Stack* stack) {
      if (stack->top == NULL) return -1;
      struct Node* temp = stack->top;
      int data = temp->data;
      stack->top = temp->next;
      free(temp);
      return data;
  }

3. 그래프 구현

그래프의 인접 리스트 표현에 링크드 리스트가 활용됩니다.

특징: 공간 효율적인 그래프 표현
응용 분야: 네트워크 라우팅, 소셜 네트워크 분석
예시 코드:

  struct GraphNode {
      int vertex;
      struct GraphNode* next;
  };

  struct Graph {
      int numVertices;
      struct GraphNode** adjLists;
  };

4. 해시 테이블의 체이닝

링크드 리스트는 해시 충돌을 해결하기 위한 체이닝 방식으로 활용됩니다.

특징: 충돌이 발생해도 데이터를 효율적으로 관리
예시 코드:

  struct HashNode {
      int key;
      int value;
      struct HashNode* next;
  };

  struct HashNode* hashTable[SIZE];

5. 멀티미디어 애플리케이션

플레이리스트 관리와 같은 작업에 원형 링크드 리스트가 사용됩니다.

특징: 반복적인 순환 가능
예시: 음악 플레이어의 곡 순환 기능

6. 라운드로빈 스케줄링

운영 체제에서 링크드 리스트는 프로세스 스케줄링을 위한 라운드로빈 큐를 구현하는 데 사용됩니다.

특징: 효율적인 프로세스 스위칭
예시 코드:

  struct Process {
      int id;
      struct Process* next;
  };

  void roundRobin(struct Process* head) {
      struct Process* temp = head;
      do {
          printf("Process ID: %d\n", temp->id);
          temp = temp->next;
      } while (temp != head);
  }

링크드 리스트는 단순 데이터 저장을 넘어 다양한 문제를 해결하는 데 활용되는 강력한 도구입니다. 각 활용 사례를 통해 링크드 리스트의 장점을 극대화할 수 있습니다.

연습 문제

링크드 리스트의 개념과 구현을 이해하고 활용 능력을 키우기 위해 다음 연습 문제를 제안합니다.

1. 단일 링크드 리스트 구현

목표: 다음 작업을 수행하는 단일 링크드 리스트 프로그램을 작성하세요.

노드 삽입: 맨 앞, 특정 위치, 맨 뒤
노드 삭제: 맨 앞, 특정 위치, 맨 뒤
리스트 출력

힌트 코드:

삽입과 삭제 함수는 위의 예제 코드를 참고하세요.

2. 이중 링크드 리스트로 이중 방향 순회 구현

목표:

이중 링크드 리스트를 구현하고 정방향 및 역방향으로 데이터를 출력하세요.
노드 삽입과 삭제 작업도 포함하세요.

추가 도전: 특정 값으로 리스트를 정렬하는 기능을 추가하세요.

3. 원형 링크드 리스트로 라운드로빈 스케줄링 시뮬레이션

목표:

원형 링크드 리스트를 사용하여 간단한 라운드로빈 스케줄링을 시뮬레이션하세요.
프로세스 ID를 저장하는 노드들을 만들고, 각 프로세스를 순환하며 작업을 수행합니다.

추가 도전:

작업 시간이 부족한 경우 해당 프로세스를 다시 리스트에 추가하는 기능을 구현하세요.

4. 해시 테이블 체이닝 구현

목표:

해시 테이블의 체이닝 방식을 구현하세요.
링크드 리스트를 사용하여 충돌이 발생한 데이터를 관리합니다.

힌트 코드:

struct HashNode {
    int key;
    int value;
    struct HashNode* next;
};

5. 그래프의 인접 리스트 표현

목표:

링크드 리스트를 사용하여 그래프의 인접 리스트를 구현하세요.
그래프 탐색 알고리즘(DFS 또는 BFS)을 추가하세요.

추가 도전:

가중치가 있는 그래프를 표현하고 최단 경로를 계산하세요.

6. 정렬된 링크드 리스트 병합

목표:

정렬된 두 개의 단일 링크드 리스트를 병합하여 새로운 정렬된 링크드 리스트를 만드세요.

추가 도전:

병합 작업을 재귀적으로 구현하세요.

7. 중복 제거

목표:

단일 링크드 리스트에서 중복된 값을 제거하는 프로그램을 작성하세요.
정렬된 리스트와 비정렬된 리스트 모두에서 작동하도록 설계하세요.

추가 도전:

공간 복잡도를 최소화하여 중복을 제거하세요(해시 테이블 미사용).

위 문제들을 해결하며 링크드 리스트의 구조와 활용 방식을 깊이 이해할 수 있습니다. 각 문제에 대한 코드 구현과 실행 결과를 확인하며 학습하세요.

요약

본 기사에서는 C언어에서 링크드 리스트의 기본 개념, 구조, 구현 및 활용 사례를 다뤘습니다. 링크드 리스트는 동적 메모리 관리를 통해 유연성과 효율성을 제공하며, 단일, 이중, 원형 링크드 리스트 형태로 다양하게 응용됩니다. 삽입, 삭제, 탐색 방법을 통해 효율적인 데이터 처리가 가능하며, 큐, 스택, 그래프, 해시 테이블 등 다양한 실용적인 응용 예시를 확인했습니다. 이를 통해 링크드 리스트의 이론과 실무적 활용 능력을 배양할 수 있습니다.