[CDS] chapter 6 : 연결리스트 ①

1. 리스트의 개념

리스트는 대표적인 선형 자료구조, 즉 연속적으로 데이터가 나열되는 자료구조이다. 이러한 선형 자료구조는 데이터에 순서가 있다는 점이 가장 핵심적인 특징이다 (집합과 구별되는 특징이다). 즉, 선형 자료구조에서는 데이터 간에 '앞'과 '뒤'라는 개념이 존재하며, 이 순서는 데이터가 추가되거나 삭제됨에 따라 바뀔 수 있다.

 

이러한 특징 때문에 선형 자료구조는 데이터를 순차적으로 접근하거나, 데이터 사이에 새로운 데이터를 삽입하거나, 특정 위치의 데이터를 삭제하는 작업을 수행하기에 적합하다.

 

선형자료구조인 리스트를 구현하는 대표적인 두가지 방법은 배열과 연결리스트인데, 이하에서 살펴보자.

2. 배열(array)과 연결리스트(linked list)

(1) 개념

배열은 크기가 정해져 있는 정적(static) 자료구조로, 메모리의 연속된 공간에 데이터를 일렬로 저장하는 자료구조이다. 

연결리스트는 크기가 정해져 있지 않은 동적(dynamic) 자료구조로, 데이터를 감싼 노드를 포인터로 연결하여 공간적인 효율성을 극대화 시킨 자료구조이다. 

https://80000coding.oopy.io/5f1a4f9f-25d1-4a3b-9236-e6d6cc9f8bb8

연결리스트는 노드라는 요소들이 포인터들에 의해 서로연결되어 있는데, 노드는 데이터를 저장하는 데이터필드와 다음 노드를 가리키는 링크필드(포인터)로 구성된다.

 

연결리스트의 첫번째 노드의 주소는 다른 노드들의 주소와 달리 앞 노드에 저장되지 않기 때는다. 이러한 첫번째 노드의 주소는 따로 저장해야 하고 절대 잊어버려서는 안되는데, 첫번째 노드를 가리키는 포인터를 헤드 포인터라고 한다. 

(2) 비교

1) 배열의 장단점

• 장 - 인덱스를 통한 접근이 가능하여 특정 위치의 원소에 대한 접근이 빠름
• 장 - 메모리 공간을 연속적으로 사용하므로 메모리 사용이 효율적임
• 단 - 배열의 크기가 고정되어 있어 크기 변경시 reallocate 필요 : 이때 원본 전체를 복사해야 함
• 단 - 원소의 삽입과 삭제가 비효율적임 : 특정 위치의 원소의 삽입,삭제시 나머지 원소를 이동시켜야 하기 때문

2) 연결리스트의 장단점

• 장 - 원소의 삽입,삭제가 효율적임 : 특정 위치의 원소 삽입,삭제시 해당 위치의 링크만 변경하면 되기 때문
• 장 - 메모리 공간을 동적으로 사용하므로, 필요에 따라 크기를 조절할 수 있음
• 단 - 특정 위치의 원소에 접근하려면 처음부터 순차적으로 탐색해야 하여 접근 속도가 느림
• 단 - 링크를 위한 추가 메모리공간이 필요하여 메모리 사용이 비효율적일 수 있음

3) 시간복잡도 정리

	접근	검색	삽입	삭제
배열	O(1)	O(N)	O(N) (맨뒤는 O(1))	O(N) (맨뒤는 O(1))
연결리스트	O(N)	O(N)	O(1) (이동까지 O(N))	O(1) (이동까지 O(N))

3. 연결리스트 구현

(1) 리스트 ADT

객체 : n개의 element형으로 구성된 순서 있는 모임
연산 :
    insert(list, pos, item) ::= pos위치에 요소를 추가한다.
    insert_last(list, item) ::= 맨 끝에 요소를 추가한다.
    insert_first(list, item) ::= 맨 처음에 요소를 추가한다.
    delete(list, pos) ::= pos위치의 요소를 제거한다.
    clear(list) ::= 리스트의 모든 요소를 제거한다.
    get_entry(list, pos) ::= pos위치의 요소를 반환한다.
    get_length(list) ::= 리스트의 길이를 구한다.
    is_empty(list) ::= 리스트가 비었는지를 검사한다.
    is_full(list) ::= 리스트가 꽉 찼는지를 검사한다.
    print_list(list) ::= 리스트의 모든 요소를 표시한다.

(2) 구현 : 다항식의 덧셈

구현은 연결리스트를 구현한 list.c, list,h와 다항식과 관련된 함수들을 구현한 poly.c, poly.h, 그리고 메인 프로그램 파일인 main.c로 각각 나누어 구현하였다. 직접 구현한 프로그램의 동작 모습과 코드는 다음과 같다.

동작모습 : 랜덤한 다항식을 생성하고 그 합을 계산

 

list.c

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

Node* create_list(){
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    return head;
}

void insert(Node* head, int pos, elem data){
    Node* prevNode = head;
    while (pos-- > 0){
        prevNode = prevNode->next;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->term = data;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

void insert_last(Node* head, elem data){
    Node* prevNode = head;
    while (prevNode->next != NULL){
        prevNode = prevNode->next;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->term = data;
    newNode->next = NULL;
    prevNode->next = newNode;
}

void insert_first(Node* head, elem data){
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->term = data;
    newNode->next = head->next;
    head->next = newNode;
}

void del(Node* head, int pos){
    Node* prevNode = head;
    while (pos-- > 0){
        prevNode = prevNode->next;
    }
    Node* targetNode = prevNode->next;
    prevNode->next = targetNode->next;
    free(targetNode);
}

void clear(Node* head){
    Node* node = head->next;
    Node* nextNode;
    while (node != NULL){
        nextNode = node->next;
        free(node);
        node = nextNode;
    }
    free(head);
}

elem get_entry(Node* head, int pos){
    Node* node = head->next;
    while (pos-- > -1){
        node = node->next;
    }
    return node->term;
}

int get_length(Node* head){
    int length = 0;
    Node* node = head;
    while (node->next != NULL){
        node = node->next;
        length++;
    }
    return length;
}

bool is_empty(Node* head){
    return head->next == NULL;
}

void print_list(Node* head){
    Node* node = head;
    while (node->next != NULL){
        node = node->next;
        printf("%dx^%d -> ", node->term.coef, node->term.expo);
    }
    printf("NULL\n");
}

 

poly.c

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

Node* create_poly(){
    Node* poly = create_list();

    int maxExpo = rand() % (10 - 5 + 1) + 5;

    int coef = rand() % 10 + 1;
    coef *= (rand() % 2) * 2 - 1;

    elem currTerm = {coef, maxExpo};
    insert_last(poly, currTerm);

    // 최고항 밑으로는 50%확률로 항을 추가했음
    for (int i = maxExpo - 1; i >= 0; i--){
        if (rand() % 2 == 1){
            int coef = rand() % 10 + 1;
            coef *= (rand() % 2) * 2 - 1;
            elem currTerm = {coef, i};
            insert_last(poly, currTerm);
        } 
    }
    return poly;
}

Node* add_poly(Node* poly1, Node* poly2){
    Node* poly3 = (Node*)malloc(sizeof(Node));
    poly3->next = NULL;

    Node* node1 = poly1->next;
    Node* node2 = poly2->next;

    while (node1 != NULL && node2 != NULL){
        if (node1->term.expo > node2->term.expo){
            insert_last(poly3, node1->term);
            node1 = node1->next;
        }
        else if (node1->term.expo < node2->term.expo){
            insert_last(poly3, node2->term);
            node2 = node2->next;
        }
        else {
            int expo = node1->term.expo;
            int coef = node1->term.coef + node2->term.coef;

            if (coef != 0){
                elem data = {coef, expo};
                insert_last(poly3, data);
            }
            node1 = node1->next;
            node2 = node2->next;
        }
    }
    
    if (node1 != NULL){
        while (node1 != NULL){
            insert_last(poly3, node1->term);
            node1 = node1->next;
        }
    }

    if (node2 != NULL){
        while (node2 != NULL){
            insert_last(poly3, node2->term);
            node2 = node2->next;
        }
    }

    return poly3;
}

void print_poly(Node* poly){
    Node* node = poly;
    if (node->next != NULL){
        node = node->next;
        printf("%dx^%d ", node->term.coef, node->term.expo);
    }
    while (node->next != NULL){
        node = node->next;
        if (node->term.expo > 1){
            if (node->term.coef > 0){
                printf("+ %dx^%d ", node->term.coef, node->term.expo);
            }
            else {
                printf("- %dx^%d ", - (node->term.coef), node->term.expo);
            }
        }
        else if (node->term.expo == 1){
            if (node->term.coef > 0){
                printf("+ %dx ", node->term.coef);
            }
            else {
                printf("- %dx ", - (node->term.coef));
            }
        }
        else {
            if (node->term.coef > 0){
                printf("+ %d", node->term.coef);
            }
            else {
                printf("- %d", - (node->term.coef));
            }
        }
    }
    printf("\n");
}

 

main.c

#include <time.h>
#include "./include/list.h"
#include "./include/poly.h"

int main(){
    srand(time(NULL));
    
    Node* poly1 = create_poly();
    Node* poly2 = create_poly();
    printf("poly1 : ");
    print_poly(poly1);
    printf("poly2 : ");
    print_poly(poly2);

    Node* poly3 = add_poly(poly1, poly2);

    printf("poly1 + poly2 = ");
    print_poly(poly3);

    clear(poly1);
    clear(poly2);
    clear(poly3);
    return 0;
}

(3) 구현 후기

• 아직 KNK에서 동적 메모리 할당 파트를 정독하지 않아 이와 관련된 부분에서 실수가 많다. 특히 NULL포인터 관련 부분과 메모리 해제를 종종 잘 잊어버리는데 이는 KNK 정독과 함께 코드를 많이 짜다보면 자연스럽게 해결되지 않을까 싶다.
• 다항식의 덧셈과 관련해서, 계수가 0, 1인 경우, 차수가 0, 1인 경우, 계수가 양수 또는 음수인 경우 등에서 출력부분을 의외로 세세하게 나누어 주어야 했다. 이중 계수가 1인 경우는 코드가 너무 길어질 것 같아 그냥 숫자 1이 출력되도록 내버려 두었다. (1x^3 이런식으로 출력된다는 의미이다)