C언어 | 이중 연결 리스트 (Doubly Linked List)

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

단일 연결 리스트(singly linked list) 에서는 한쪽 방향으로 노드를 연결한다.

이중 연결 리스트는 두방향으로 노드를 연결한 다는 점이 다르다.

양방향으로 이동 가능하다는 것은 자료형태에 다양한 가공을 할 수 있다는 것을 의미한다.

이 포스팅에서는 C언어로 기본적인 이중 연결 리스트를 설계해본다.

이중 포인터를 사용하는 경우도 많이 있는데 여기서는 일반 포인터를 사용한다.

확실히 이중 연결 리스트는 하나의 노드에 prev 와 next 두 방향의 포인터가 들어있기 때문에 이중 포인터를 사용하는게 편리한 경우가 있다. 그런데 코드의 가독성은 떨어지게 되므로 사용에 주의할 필요는 있다. 이중 포인터를 사용하지 않아도 양방향으로 이동이 가능하다.

사용하는 사람의 성향에 따라서 이중 포인터를 선호하는 경우도 있고 아닌 경우도 있는데, 코드를 줄이면서 쉬운 추상화를 추구하는 현재의 프로그래밍 흐름과는 확실히 동떨어진 것으로 보인다. 과거에 프로그래밍을 배운다는 것은 C의 포인터를 잘 다룬다는 것을 의미했기에 이중, 삼중 포인터를 능숙하게 다루는 것은 중요한 일이었을 것이다.

일반 링크드 리스트에 대하여는 아래 포스팅을 참고한다.

C언어 | 링크드리스트 기초 총정리 | 삽입, 삭제, 정렬, 검색, 메모리 외

C언어 링크드 리스트는 많은 학생들에게 학업에 대한 스트레스를 줬을 것이라 생각한다. 특히 프로그래밍 학습의 진도가 너무 빨리 나갈 때 배워야 할 것은 많고 시간은 짧아 보인다. 하지만 이

digiconfactory.tistory.com

Double Pointer (Pointer to Pointer) in C - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

* 노드 만들기

단일 연결리스트와의 차이점은 포인터가 두개 연결되는 점이다. *next는 전진하는 방향으로 *prev 은 앞쪽 방향이다.

노드를 처음 생성하는 함수이다. malloc 으로 노드 사이즈만큼 생성한다. 위에서 Node 구조체가 int 형 변수 하나, 포인터 2개를 사용했으므로 12 바이트이다. (int - 4바이트, 32비트 포인터 2개 - 8바이트)

처음 생성하므로 포인터가 NULL일 때만 생성된다.

앞쪽에 값을 추가하는 append first 이다. 양방향으로 포인트가 연결되어 있다. 단일 연결리스트에서는 next만 연결시켰지만 prev 도 연결하고 prev는 그 전의 노드 주소에게 연결한다.

newNode->prev = head

*newNode는 head를 가리키고

head->next = newNode

*head는 newNode를 가리킨다. 서로가 서로를 가리킨다.

원래 head에 노드가 연결되어 있었다면

newNode->next에는 기존 head->next 를 연결시킨다. (else 부분)

head->next->prev를 newNode로 바꾸는 것도 잊지 않는다.

* 이중 연결리스트의 코드가 복잡하게 보인다. 하지만 하나씩 연결을 시키다 보면 정직하게 연결되어 있다는 것을 알 수있다. 추상적 단계가 높은 OOP 코드들을 많이 사용하는 현대에서 이런 과정은 좀 번거롭게 보일 수 있으나 이런 연습들로 컴퓨터 구조에 대한 이해도가 높아지는 것도 사실이다.

append 는 마지막 요소에 추가하는 함수이다.

공책에 그림을 그리면서 해보는 것을 추천한다. 그림을 그리고 순서와 방향을 잡으면 이해가 쉬운데 코드만 봐서는 잘 와닿지 않는다. 그림을 보면서 코드를 작성하면 어렵지 않다.

이중 연결 리스트의 기본 뼈대를 만들어놓은 다음 여러가지 기능을 추가할 수 있다. 리스트를 원형으로 만든다던지 (이중 원형 연결리스트 - Doubly Circular Linked List) 양방향 검색에 최적화하는 형태를 만들 수도 있다. 이중 연결 리스트를 활용한 스택 처럼 하나의 자료 구조에 다른 자료 구조를 혼합하여 사용할 수도 있다. 이 포스팅에서는 기본적인 내용을 다루고 다음에 내용을 더 추가하도록 하겠다.

숙련된 프로그래머들이 하는 이야기에 공통점이 있다. 컴퓨터 공부에 왕도는 없다고 한다. 또 컴퓨터 언어를 마스터(master) 하는 것은 불가능하다고 한다. 쉽게 말해 모든 컴퓨터 언어를 다 꿰뚫고 있는 도사같은 사람은 없다는 말이다.

기술은 매일같이 새로 나오고 컴퓨터 언어는 이해하는게 목적이 아니라 실행되기 위해 존재한다. 소스코드의 명령어가 CPU에게 전기신호로 전달되어 실행되도록 하는 것이다. 인터넷의 컴퓨터 서버는 24시간 작동한다. 밤새도록 인터넷을 할 수 있는 게 당연해진 것은 불과 몇십년도 지나지 않았다. 핸드폰으로 인터넷을 보는게 익숙해진 것은 극히 최근의 일이다. 자료구조를 공부하는 것은 시간이 걸리는 일이지만 컴퓨터의 밑바탕이 되는 것이기에 오래토록 도움이 될 거라고 생각한다.

우리가 사용하는 컴퓨터 알고리즘이란 학문은 상대적으로 최근에 발명된 것이라고 한다. 80년대의 알고리즘 저서들에 보면 당시 대부분의 알고리즘은 60년대부터 30년동안 발명된 것이라고 한다. 그 내용은 2020년 지금 배우는 알고리즘들과 큰 차이가 없다.

기술의 발달이 우리 생활의 변화를 가속화시키는데 이 기술의 최초 아이디어가 100년 전에 이미 나왔던 것들은 꽤 많다. 최근 각광 받는 인공지능의 토대가 된 퍼셉트론도 20세기에 나온 개념이다. 그 때는 하드웨어 발달이 안되서 많은 아이디어들이 실현되지 못했다. 지금은 상당수가 가능하고 빅데이터가 모이기 시작해서 기계에게 무언가 학습을 시킬 수 있는 단계에 접어들었다.

이런 시기일 수록 기본으로 돌아가서 볼 필요가 있다. 어쩌면 이전보다 알고리즘과 자료구조 학습이 더 실제적으로 도움이 될 거라는 생각이다.

프로그래밍을 배워야 하는 이유는? - YouTube

*예제 소스코드

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

typedef struct __node
{
    int value;
    struct __node *next;
    struct __node *prev;
}Node;

void insertNode(Node* head, int value); // 미구현

Node* getNode(Node* ptr);
void showList(Node* ptr);
int getRandomInt(int from, int to);
void appendFirst(Node* ptr, int data);
void append(Node* ptr, int data);
void deleteList(Node* ptr);
Node* getLastNode(Node* ptr);

int main(int argc, char const *argv[])
{

    srand(time(NULL));

    Node* head = NULL;
    head = getNode(head);

    for (int i = 0; i < 5; i++)
    {
        appendFirst(head, getRandomInt(1, 100));
    }

    showList(head);

    append(head, 999);
    append(head, 777);
    append(head, 222);

    showList(head);

    printf("Last Node Value: %d\n", getLastNode(head)->value);


    showList(head);

    deleteList(head);

    return 0;
}


/* ---------- 함수영역 ---------- */


Node* getLastNode(Node* ptr)
{
    if (ptr == NULL){
        return ptr;
    } else{    
        Node *cur = ptr;
        while(cur->next != NULL)
        {
            cur = cur->next;
        }
        return cur;
    }
}

void deleteList(Node *ptr){
    Node *cur = ptr;
    Node *next;
    while(cur != NULL)
    {
        next = cur->next;
        free(cur);
        cur = next;
    }
    printf("-> List deleted...\n");  
}


void append(Node* ptr, int data)
{
    // 새로운 노드
    Node* newNode = malloc(sizeof(Node));
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->value = data;

    if (ptr->next == NULL)
    {
        printf("This is the first node after head\n");
        // 첫번째 노드 연결
        newNode->prev = ptr;
        newNode->next = NULL;

        // 맨앞쪽에 추가, head 의 바로 다음 노드
        ptr->next = newNode;
        // head는 사용안함(명시)
        ptr->value = 0;
        ptr->prev = NULL;
        printf("-> value added(last)... (%d)\n", newNode->value);
    }
    // 노드에 요소가 있는 경우 
    else
    {
        Node* cur = ptr;
        while(cur->next != NULL)
        {
            cur = cur->next;
        }
        cur->next = newNode;
        newNode->prev = cur;
        printf("-> value added(last)... (%d)\n", newNode->value);
    }
    
}

void showList(Node* head)
{
    printf("[Showing Doubly List]\n");

    if(head == NULL){
        printf("no element found..\n");
    }
    else
    {
        printf("[");
        Node* cur = head;
        while(cur->next != NULL)
        {
            cur = cur->next;
            if(cur->next == NULL){
                printf("%2d ", cur->value);
            }else{
                printf("%2d, ", cur->value);
            }
        }
        printf("]\n");
    }
}

void appendFirst(Node* head, int data)
{
    //새로운 노드 생성
    Node* newNode = malloc(sizeof(Node));
    newNode->value = data;
    newNode->prev = NULL;
    newNode->next = NULL;

    if (head->next == NULL)
    {
        printf("This is the first node after head\n");
        // 첫번째 노드 연결
        newNode->prev = head;
        newNode->next = NULL;

        // 맨앞쪽에 추가, head 의 바로 다음 노드
        head->next = newNode;
        // head는 사용안함(명시)
        head->value = 0;
        head->prev = NULL;
        printf("-> value added(first)... (%d)\n", newNode->value);
    }
    // 노드에 요소가 있는 경우
    else 
    {
        newNode->prev = head;
        newNode->next = head->next;
        head->next->prev = newNode;
        head->next = newNode;
        printf("-> value added(first)... (%d)\n", newNode->value);
    }
}

Node* getNode(Node* ptr)
{
    if(ptr == NULL)
    {
        ptr = malloc(sizeof(Node));
        ptr->value = 0;
        ptr->next = NULL;
        ptr->prev = NULL;
        printf("node created..\n");
        return ptr;
    }
    printf("node creation failed..");
}

int getRandomInt(int from, int to)
{
    int random = rand() % (to-from+1) + from;
    return random;
}

C언어 7 - 2 | 링크드 리스트 기초 (Linked List)

링크드 리스트는 자료구조의 한 형태로 알고리즘에서 다루어야 할 주제이지만 대부분의 C교재는 기본적인 사항을 다룬다. 이것도 좋은 자료를 많이 확보해야 하는데 영문 자료에 좋은 자료가

digiconfactory.tistory.com

C언어 7 - 3 | 링크드 리스트 기초 (Linked List) 요소 추가 및 삭제 함수, 잡설

이 포스팅의 예제는 함수를 사용하여 요소를 추가하고 삭제하는 링크드 리스트이다. 링크드 리스트의 개념에 대해서는 이고잉님의 생활코딩의 영상 강의가 매우 좋다. Linked list - Data Structure (자

digiconfactory.tistory.com

C언어 | 이진 탐색 트리( Binary Search Tree) 만들기 | 추가, 삭제, 검색

이진 탐색 트리 C언어 *이진검색트리 (Binary Search Tree)의 조건 - 이진 트리는 루트를 중심으로 노드가 왼쪽에 하나 오른쪽에 하나씩 연결된다. - 노드 N(어느 한 노드)을 기준으로 왼쪽 트리의 키값

digiconfactory.tistory.com