[자료구조] 리스트 (연결 리스트 부터 이중 연결 리스트까지)

오늘 알아볼 자료구조는 리스트입니다 :)

 

리스트란?

순서를 가지고 일렬로 나열한 원소들의 모임으로 데이터 목록을 다루는 자료구조로 기본 연산으로는 삽입, 삭제, 탐색이 있습니다. 

 

리스트 구현 방법

1. 배열 이용 (순차적인 메모리 공간 할당)

2. 연결 리스트 이용 (노드에 분산 저장)

 

리스트의 연산

• init(list) - 리스트 초기화

• is_empty(list) - 리스트 공백 유무 검사

• is_full(list) - 리스트 포화상태 유무 검사

• insert(list, pos, item) - pos 위치에 item 추가

• insert_last(list, item) - 리스트 맨 끝에 item 추가

• delete(list, pos) - pos 위치의 요소 제거

• get_entry(list, pos) - pos 위치의 요소 반환

• print_list(list) - 리스트 모든 요소 표시

 

 

배열을 이용한 리스트 구현

---

장점: 특정 인덱스에 접근하기 쉬움, 탐색 및 정렬에 용이

단점: 메모리 관리에 비효율적

 

배열을 이용한 리스트 구현 with C

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

#define MAX_LIST_SIZE 100 // 리스트 최대 크기
typedef int element;

typedef struct {
    element array[MAX_LIST_SIZE]; // 배열 정의
    int size; // 현재 리스트에 저장된 항목들의 개수
} ArrayListType;

// 오류 처리
void error(char *message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// 초기화
void init(ArrayListType *L){
    L -> size = 0;
}

int is_empty(ArrayListType *L){
    return L -> size == 0; // 비어있으면 1, 그렇지 않으면 0 반환
}

int is_full(ArrayListType *L) {
    return L -> size == MAX_LIST_SIZE; // 가득 찼으면 1 그렇지 않으면 0 반환
}

element get_entry(ArrayListType *L, int pos){
    if (pos < 0 || pos >= L -> size){
        error("위치 오류");
    }
    return L -> array[pos];
}

void print_list(ArrayListType *L) {
    int i;
    for (i = 0; i < L -> size; i++){
        printf("%d->", L -> array[i]);
    }
    printf("\n");
}

void insert_last(ArrayListType *L, element item){
    if(L->size >= MAX_LIST_SIZE){
        error("List Overflow");
    }
    L -> array[L->size++] = item;
}

void insert(ArrayListType *L, int pos, element item){
    if(!is_full(L) && (pos>=0) && (pos<= L->size)) {
        for(int i = (L -> size - 1); i >= pos; i--){
            L -> array[i+1] = L -> array[i];
        }
        L -> array[pos] = item;
        L -> size++;
    }
}

element delete(ArrayListType *L, int pos){
    element item;
    
    if (pos < 0 || pos >= L -> size){
        error("위치 오류");
    }
    
    item = L -> array[pos];
    
    for (int i = pos; i<(L->size - 1); i++){
        L -> array[i] = L -> array[i+1];
    }
    L -> size--;
    return item;
}

int main(void){
    ArrayListType list;
    
    init(&list);
    
    insert(&list, 0, 10); // 0번째 위치에 10 추가
    print_list(&list);
    insert(&list, 0, 20); // 0번째 위치에 20 추가
    print_list(&list);
    insert(&list, 0, 30); // 0번째 위치에 30 추가
    print_list(&list);
    insert_last(&list, 40); // 맨 끝에 40 추가
    print_list(&list);
    delete(&list,0); // 0번째 항목 삭제
    print_list(&list);
    return 0;
}

 

연결 리스트 구현

---

 

장점

1. 삽입, 삭제 용이

2. 연속된 메모리 공간이 필요 없음

3. 크기 제한이 없음

단점

1. 구현이 어려움

2. 일반적으로 탐색 속도가 떨어짐

 

연결 리스트 종류

1. 단순 연결 리스트

2. 원형 연결 리스트

3. 이중 연결 리스트 

 

 

단순 연결 리스트 구현 with C

특징: 하나의 링크 필드만을 이용하여 연결, 마지막 노드의 링크 값은 NULL

 

단순 연결 리스트 삽입 연산 

 

단순 연결 리스트 삭제 연산 

 

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

typedef int element;

typedef struct ListNode{
    element data;
    struct ListNode *link;
}ListNode;

// 첫 노드 삽입
ListNode* insert_first(ListNode *head, int value){
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));
    p -> data = value;
    p -> link = head;
    head = p;
    return head;
}

// 특정 노드 뒤 새로운 노드 삽입
ListNode* insert(ListNode *head, ListNode *pre, element value){
    ListNode *p = (ListNode*)malloc(sizeof(ListNode));
    
    p -> data = value;
    p -> link = pre -> link;
    pre -> link = p;
    return head;
}

// 첫번째 노드 삭제
ListNode* delete_first(ListNode *head){
    ListNode *removed;
    
    if (head == NULL){
        return NULL;
    }
    
    removed = head;
    head = removed -> link;
    free(removed);
    return head;
}

// pre가 가리키는 노드의 다음 노드 삭제
ListNode* delete(ListNode *head, ListNode *pre){
    ListNode *removed;
    removed = pre -> link;
    pre -> link = removed -> link;
    free(removed);
    return head;
}

void print_list(ListNode *head){
    for(ListNode *p = head; p != NULL; p = p -> link){
        printf("%d ->", p -> data);
    }
    printf("NULL \n");
}

int main(void){
    ListNode *head = NULL;
    
    for (int i = 0; i <5; i++){
        head = insert_first(head, i);
        print_list(head);
    }
    
    for (int i = 0; i < 5; i++){
        head = delete_first(head);
        print_list(head);
    }
    
    return 0;
}

 

 

원형 연결 리스트 구현 with C

특징: 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트, 한 노드에서 다른 모든 노드로 접근 가능

* 헤드포인터를 마지막 노드를 가리키게 구성하면, 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결 리스트에 비해 용이하다.

 

원형 연결 리스트 처음에 삽입

 

원형 연결 리스트 끝에 삽입

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

typedef int element;

typedef struct ListNode{
    element data;
    struct ListNode *link;
}ListNode;

// 원형 연결 리스트의 처음에 삽입
ListNode* insert_first(ListNode *head, element data){
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node -> data = data;
    if (head == NULL){
        head = node;
        node -> link = head;
    }else{
        node -> link = head -> link;
        head -> link = node;
    }
    return head;
}

// 원형 연결 리스트 끝에 삽입
ListNode* insert_last(ListNode *head, element data){
    ListNode *node = (ListNode*)malloc(sizeof(ListNode));
    
    node -> data = data;
    
    if (head == NULL){
        head = node;
        node -> link = head;
    }else{
        node -> link = head -> link;
        head -> link = node;
        head = node;
    }
    return head;
}


void print_list(ListNode *head){
    ListNode *p;
    
    if(head == NULL){
        return;
    }
    
    p = head -> link;
    do{
        printf("%d->", p->data);
        p = p ->link;
    } while(p != head);
    printf("%d->", p -> data);
}

int main(void){
    ListNode *head = NULL;
    
    head = insert_last(head, 20);
    head = insert_last(head, 30);
    head = insert_last(head, 40);
    head = insert_first(head, 10);
    print_list(head);
    printf("\n");
    
    return 0;
}

 

이중 연결 리스트 구현 with C

특징: 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트, 단점은 공간을 다소 많이 차지하고 코드가 복잡함

* 헤드노드: 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드로 공백상태시 헤드 노드만 존재 (헤드 포인터와 구분 필요)

 

이중 연결 리스트 삽입 연산

 

이중 연결 리스트 삭제 연산

 

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

typedef int element;

typedef struct DListNode {
    element data;
    struct DListNode *llink;
    struct DListNode *rlink;
}DListNode;

// 이중 연결 리스트 초기화
void init(DListNode *phead){
    phead -> llink = phead;
    phead -> rlink = phead;
}

// 새로운 데이터 before노드 오른쪽에 삽입
void insert(DListNode *before, element data){
    DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));
    newnode -> data = data;
    newnode -> llink = before;
    newnode -> rlink = before -> rlink;
    before -> rlink -> llink = newnode;
    before -> rlink = newnode;
}

// 노드 삭제
void delete(DListNode *head, DListNode *removed){
    if (removed == head){
        return;
    }
    
    removed -> llink -> rlink = removed -> rlink;
    removed -> rlink -> llink = removed -> llink;
    free(removed);
}

void print_dlist(DListNode *phead){
    DListNode *p;
    for(p = phead ->rlink; p!= phead; p = p ->rlink){
        printf("<-| |%d| | ->", p -> data);
    }
    printf("\n");
}

int main(void){
    DListNode *head = (DListNode *)malloc(sizeof(DListNode));
    init(head);
    
    printf("삽입 \n");
    for(int i =0; i <5; i++){
        // 헤드 노드 오른쪽에 새로운 노드 삽입
        insert(head,i);
        print_dlist(head);
    }
    
    printf("삭제 \n");
    for(int i = 0; i < 5; i++){
        print_dlist(head);
        delete(head, head -> rlink);
    }
    free(head);
    return 0;
}