[자료구조] 연결 리스트(Linked List)

연결 리스트

정의

포인터를 이용하여 리스트를 구현한 자료 구조로 각 요소가 다음 요소의 위치를 포인터로 가리킨다. → 즉, 메모리 상에서 연속되지 않지만 순서를 유지할 수 있다.
배열과 차이점: 크기 제한이 없다 → 유동적으로 조절 가능
집합과의 차이점: 연결 리스트는 요소의 순서를 유지하며, 중복된 값도 허용한다.
그래프와의 차이점: 갈림길 없이 일렬로 나열되어 처음과 끝이 각각 하나씩 존재한다.
즉, 동적 메모리에 할당된, 링크에 의해 연결된 유한 개수의 데이터 원소 노드들이다.

연결 리스트의 장단점

장점
- 데이터의 추가와 삭제가 용이하다.(원소의 이동이 필요 없다.)
- 데이터의 삽입과 삭제가 배열보다 빠르다.
- 데이터의 중복이 없다.
- 메모리 할당이 동적이다.(메모리 효율성 좋음)
- 크기 제한이 없다.
- 추상적 자료구조 구현이 가능하다.(스택, 트리, 큐 등), 확장성이 좋다.
단점
- 데이터의 탐색이 느리다.(찾을 때까지 순회해야되기 때문)
- 메모리 공간이 많이 필요하다.
- 데이터의 순서가 중요하다.

연결 리스트의 구조

연결 리스트 명($L$): 연결 리스트의 시작 위치, 즉 첫 노드의 주소
연결 리스트 크기($n$): 연결 리스트 내 노드 수

연결 리스트의 종류

단일 연결 리스트
원형 연결 리스트
이중 연결 리스트
헤더 및 트레일러 연결 리스트
이들의 복합

노드에 대한 메모리 할당

노드는 한 개의 데이터 원소를 저장하기 위해 동적 메모리에 할당된 메모리로, 주로 실제 데이터 값과 다음 원소의 위치를 가리키는 포인터 가지고 있다.
getnode()
- 새로운 노드를 메모리에 생성하는 과정을 나타내는 것으로 노드를 할당하고 그 노드의 주소를 반환한다.(동적 메모리가 고갈된 시점이면 Null 포인터를 반환)
putnode()
- 연결 리스트에서 노드를 삭제하거나, 사용을 마친 경우에는 해당 노드를 메모리에서 해제해줘야 하는데 그 때 사용한다.
- 주소 i의 노드에 할당되었던 메모리의 사용을 해제하고, 이를 메모리 재활용을 위해 동적 메모리에 반환한다.
순차 연결 리스트( ==순차 리스트)
- 배열로 구현한 리스트로서 구현이 쉽고 속도가 빠르다.
- 하지만 배열의 특성 상 동적으로 크기를 줄이기 어렵다는 단점이 있다.
- 배열로 구성되니, 배열의 특성을 다 가져간다.
- 삽입이나 삭제 연산 시, 원소를 직접 옮기는 과정을 거친다. 즉, 삽입 삭제 연산이 많다면, 시간이 많이 걸린다.

단일 연결 리스트

각 노드가 데이터와 다음 노드 정보를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

저장 내용
- 원소: 데이터
- 원소 링크: 다음 노드의 주소(다음 노드가 없는 경우 Null링크 저장)
구성 요소
- Head: 연결 리스트의 시작 노드
- Tail: 연결 리스트의 마지막 노드
- Length: 전체 길이 추적

노드의 구성

  typedef struct Node{
      int data; // 가지고 있는 데이터
      struct Node* next; // 다음 노드 정보
  	} node;

구현 내용
- 더미 머리 / 더미 꼬리 / 리스트 크기 선언
- 리스트 초기화
- 특정 노드의 앞 혹은 뒤에 노드 추가하여 삽입하기
- 특정 노드 삭제
- 특정 노드 찾기
- 모든 노드 제거/출력

원형 연결 리스트

리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트

장점
- 한 노드에서 다른 모든 노드로의 접근이 가능하다. 즉, 노드의 삽입, 삭제가 단순한다.
- 리스트의 끝에 노드를 추가하는 것이 단순 연결 리스트보다 쉽다.
- 큐(원형 큐) 구현이 쉽다.
단점
- 노드의 삽입, 삭제 시 선행 노드의 포인터가 필요함
- 디버깅이 어려울 수 있다.(무한 루프 가능성)

이중 연결 리스트

단방향 흐름을 2개의 링크 필드를 이용하여 양방향으로 움직일 수 있도록 만든 연결 리스트
장점
- 양방향으로 움직일 수 있어 데이터 접근이 단순하다.
- 원형 연결 리스트 보다 쉽고 삽입, 삭제 연산 시 선행 노드에 대한 정보가 필요 없다.
- 역순 탐색(tail부터)도 가능
단점
- 변수 추가에 따라 메모리를 더 많이 사용하고, 구현이 복잡하다.
헤더(Header node) & 트레일러(Trailer node)
- 작업의 편의를 위해 추가하는 특별 노드(모조 노드 혹은 더미 노드)
- 아무 원소(실제 데이터 원소)도 저장하지 않는다.
- 헤드노드와 헤더노드, 테일 노드와 트레일러 노드는 각각 다른 것이다.
- 헤드노드와 테일 노드는 각 값들이 원소를 저장하고 있다. 하지만 헤더와 트레일러는 원소들을 저장하고 있지않다.
- 즉, 헤드 노드는 값을 가진 것들 중 맨 앞에 있는 것이고 이 헤드를 가리키는 노드가 헤더 노드이고, 테일 노드는 값을 가진 것들 중 맨 뒤에 있는 노드이고, 이 테일 노드가 가리키는 것이 트레일러 노드이다.
- 헤더 노드: 헤드 노드 바로 앞에 추가하여 사용
- 트레일러 노드: 테일 노드 바로 뒤에 추가하여 사용

배열, 단일 연결 리스트, 이중 연결 리스트 성능 비교

응용 문제

이중 연결 리스트의 삽입, 삭제, 순회 등 구현

 #include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 #pragma warning(disable:4996)
    
 typedef struct node {
     char elem;
     struct node* prev;
     struct node* next;
 } node;
    
 void add(node* h, int r, char e) {
     node* new = (node*)malloc(sizeof(node));
     node* cur = h;
    
     new->elem = e;
    
     if (r < 1) {
         printf("invalid position\n");
         return;
     }
    
     for (int i = 0; i < r; i++) {
         if (cur->next == NULL) {  
             printf("invalid position\n");
             return;
         }
         cur = cur->next;
     }
    
     new->prev = cur->prev;
     new->next = cur;
     if (cur->prev != NULL){
         cur->prev->next = new;
     }
     cur->prev = new;
 }
    
 void delete(node* h, int r) {
     node* cur = h;
     for (int i = 0; i < r; i++) {
         if (cur->next == 0) {
             printf("invalid position\n");
             return;
         }
         cur = cur->next;
     }
     if (cur->next == NULL || r < 1) {
         printf("invalid position\n");
         return;
     }
     (cur->next)->prev = cur->prev;
     (cur->prev)->next = cur->next;
     free(cur);
 }
    
 char get(node* h, int r) {
     node* cur = h;
     for (int i = 0; i < r; i++) {
         if (cur->next == NULL) {
             printf("invalid position\n");
             return;
         }
         cur = cur->next;
     }
     if (cur->next == NULL || r == 0) {
         printf("invalid position\n");
         return;
     }
     printf("%c\n", cur->elem);
 }
    
 void print(node* h) {
     node* cur = h->next;
     while (cur->next != NULL) {
         printf("%c", cur->elem);
         cur = cur->next;
     }
     printf("\n");
 }
    
 int main() {
     node* h = (node*)malloc(sizeof(node));
     node* t = (node*)malloc(sizeof(node));  
    
     h->next = t;
     t->prev = h;
     h->prev = NULL;
     t->next = NULL;
    
     int n, r;
     char func, e;
     scanf("%d", &n);
     getchar();
     for (int i = 0; i < n; i++) {
         scanf("%c", &func);
         getchar();
         if (func == 'A') {
             scanf("%d", &r);
             getchar();
             scanf("%c", &e);
             getchar();
             add(h, r, e);
         }
         else if (func == 'D') {
             scanf("%d", &r);
             getchar();
             delete(h, r);
         }
         else if (func == 'G') {
             scanf("%d", &r);
             getchar();
             get(h, r);  
         }
         else if (func == 'P') {
             print(h);  
         }
     }
    
     return 0;
 }

PREVIOUS[자료구조] 스택(Stack)과 큐(Queue)