헤드노드를 이용하지않는 이중연결리스트의 구현

저번에 살펴본 헤드노드를 이용한 이중연결리스트의 구현 프로그램은 헤드노드(더미노드)를 이용하여 편리하게 구현할 수 있었으나

구현의 로직이 지금껏 단순연결리스트, 원형리스트의 구현의 로직과는 조금 다르고 헤드포인터를 사용하지않고 헤드노드를 사용한다는점에서  

구현 시 오류의 발생확률과 삽입 시 정렬되는 노드가 역순이되므로 이를 정방향으로 정렬시켜줄 연산의 수정이 필요합니다.

(0,1,2,3,4 삽입 시 4->3->2->1->0)

따라서 지금껏 해온 표현방법대로 이중연결리스트를 구현하는게 더 편할 수 있기 때문에 이를 구현해봤습니다.

헤드노드를 이용한 방법과의 차이점은 일단 헤드노드 대신 헤드포인터를 사용하고, 삽입 되는 맨 첫 노드와 맨 끝 노드의 링크가 헤드노드를 

가리키지않고 NULL을 가리킨다는 점입니다.

*visual studio 2019의 경우 "월","수" 등의 데이터를 함수에서 char형 포인터로 받을 때 char*x로 선언하면 에러가 뜹니다.

(고정된 값 이므로 수정할 수 없기 때문에 (상수처리되기때문) const char*x로 선언해야합니다.)

어려운점은 딱히 없고 노드의 링크를 주고받는 연산만 잘 이해하면 될 것 같습니다.

이번 코드 역시 head의 변경이 생길 수 있는 함수(insert,delete함수)는 2차원포인터를 이용했습니다.

코드

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
typedef struct listNode
{
    char data[4];
    struct listNode* left;
    struct listNode* right;
}listNode;
void printList(listNode* head)
{
    listNode* temp;
    printf("DL=(");
    temp = head;
    while (temp != NULL)
    {
        printf("%s", temp->data);
        temp = temp->right;
        if (temp != NULL)printf(",");
    }
    printf(")\n");
}
void insertNode(listNode** head, listNode* pre, const char* x)
{
    listNode* newNode = (listNode*)malloc(sizeof(listNode));
    strcpy(newNode->data, x);
    if (*head == NULL)
    {
        newNode->left = NULL;
        newNode->right = NULL;
        *head = newNode;
    }
    else
    {
        newNode->right = pre->right;
        pre->right = newNode;
        newNode->left = pre;
        //삽입한 노드의 right에 노드가 있다면 newNode의 오른쪽 노드가 newNode를 가리킴
        if (newNode->right != NULL)
            newNode->right->left = newNode;
        //else의 경우 그대로 놔둠(newNode의 오른쪽링크로 통하는 노드가 없기때문)
    }
}
listNode* searchNode(listNode* head, const char* x)
{
    listNode* temp;
    temp = head;
    while(temp != NULL)
    {
        if (strcmp(temp->data, x) == 0)return temp;
        else temp = temp->right;
    }
    //이 경우 NULL반환(없으므로)
    return temp;
}
void deleteNode(listNode** head, listNode* removed)
{
    if (head == NULL)return;
    else
    {
        removed->left->right = removed->right;
        removed->right->left = removed->left;
        free(removed);
    }
}
int main()
{
    listNode* head = NULL;
    listNode* p;
    printf("이중연결리스트 생성하기\n");
    printList(head);
    printf("이중연결리스트에 [월]노드 삽입하기\n");
    insertNode(&head, NULL, "월");
    printList(head);
    printf("이중 연결리스트의 [월]노드 뒤에 [수]노드 삽입하기.\n");
    p = searchNode(head, "월"); 
    if(p!=NULL)
        insertNode(&head, p, "수");
    printList(head);
    printf("이중 연결리스트의 [수] 노드 뒤에 [금]노드 삽입하기.\n");
    p = searchNode(head, "수");
    if (p != NULL)
        insertNode(&head, p,"금");
    printList(head);
    printf("이중 연결리스트에서 [수]노드 삭제하기\n");
    if(p!=NULL)
    p = searchNode(head, "수"); deleteNode(&head, p);
    printList(head);
    return 0;
 
}

결과