[C/C++] 이중 LinkedList 구현 예제

사용자로부터 정수 값을 입력받아 이중연결 리스트로 생성한다. 리스트 노드는 입력받은 순서대로 연결한다. 이중연결 리스트 삽입 함수/삭제 함수를 사용한다.(교재 참고) (1) 입력받은 후 display() 함수에 의해 각 노드의 내용을 출력한다. (display() 교재 참고) (2) 마지막 데이터를 삭제 후 (삭제 함수 이용), 다시 display() 함수로 각 노드 내용을 출력한다. - 입력을 끝내기 위해 마지막에 -1을 입력한다. - DlistNode 타입을 정의하여 사용한다. - 동적 메모리 할당을 사용한다. <입출력 예1> 15 25 70 5 10 -1 15 25 70 5 10 15 25 70 5  <입출력 예2> 7 20 12 -1 7 20 12 7 20

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

typedef struct DlistNode {
    int data;
    struct DlistNode *llink;
    struct DlistNode *rlink;
} DlistNode;

void display(DlistNode *head)
{
    DlistNode   *p;
    for (p = head->rlink; p != head; p = p->rlink){
        printf("%d ", p->data);
    }
    printf("\n");
}

void dinsert_node(DlistNode *before, DlistNode *new_node)
{
    new_node->llink = before;
    new_node->rlink = before->rlink;
    before->rlink->llink = new_node;
    before->rlink = new_node;
}

void dremove_node(DlistNode *head, DlistNode *removed)
{
    if ( removed == head ) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

int main()
{
    DlistNode    header;
    DlistNode    *before, *new_node;
    int          data;

    // header node 구성 
    header.llink = &header;
    header.rlink = &header;

    before = &header;
    // 사용자 입력, 노드 생성, 리스트 삽입
    do {
        scanf("%d", &data);
        if (data == -1) break;
        // 노드를 위한 동적 메모리 할당
        new_node = (DlistNode *) malloc(sizeof(DlistNode));
        // 노드에 데이터 저장
        new_node->data = data;
        // 노드를 리스트에 삽입
        dinsert_node(before, new_node);
        before = new_node;

    } while (1);

    // 출력 : display(리스트시작주소)
    display(&header);
    // 마지막 노드 삭제: dremove_node()
    dremove_node(&header, header.llink /*befor*/ /*new_node*/);
    // 출력 : display(리스트 시작주소)
    display(&header);
 
}