[자료구조] 양뱡향 연결리스트(Doubly Linked List) - C

양방향 연결리스트(Doubly Linked List)

• 연결 리스트에서 데이터의 삽입을 할 때, head 의 위치에 따라 마지막 노드의 위치를 찾아야하는 경우가 발생한다.
• 기존의 연결 리스트는 이전 노드로 돌아가지 못한다.

 

양방향 연결리스트는 노드의 링크가 두 개씩 달려있다.

typedef struct _doubNode
{
    struct _doubNode *prev;
    int data;
    struct _doubNode *next;
} DNode;

 

 

다음으로 각 기능별 함수에 대해 설명하겠다.

 

1. 앞 부분에서 데이터를 삽입하는 함수

 

양쪽 다 link가 있으므로 모두 수정해줘야 한다.

void AddFront(DNode **head, int val)
{
    DNode *temp = *head;
    DNode *newnode = (DNode *)malloc(sizeof(DNode));
    newnode->data = val;
    if (*head == NULL)
    {
        newnode->prev = NULL;
        newnode->next = NULL;
        *head = newnode;
        return;
    }
    temp->prev = newnode;
    newnode->prev = NULL;
    newnode->next = temp;
    *head = newnode;
}

 

 

2. 중간부분에서 데이터를 삽입하는 함수

 

newnode에 데이터를 넣고, 마지막 노드를 찾아 temp에 저장한 하여 마지막 노드와 newnode를 연결한다.

void AddMid(DNode **head, int val, int index) // 뒤에서부터의 인덱스 값
{
    DNode *temp = *head;
    DNode *newnode = (DNode *)malloc(sizeof(DNode));
    newnode->data = val;
    if (*head == NULL)
    {
        newnode->prev = NULL;
        newnode->next = NULL;
        *head = newnode;
        return;
    }

    for (int i = 0; i < index; i++)
    {
        temp = temp->next;
    }
    newnode->next = temp->next;
    newnode->next->prev = newnode;
    newnode->prev = temp;
    temp->next = newnode;
}

 

 

3. 삭제하는 함수

 

값에 해당하는 노드를 찾아 cur를 정한다. 그리고 bef는 cur의 바로 전 노드로 설정한다.

cur 노드 전과 후를 연결하고, cur 노드는 할당해제한다.

int DelNode(DNode **head, int val)
{
    DNode *bef = *head;
    DNode *cur = *head;
    int tmp = 0;
    if (*head == NULL)
    {
        printf("삭제할 값이 없습니다.\n");
        return -1;
    }

    while (cur->data != val)
    {
        bef = cur;
        cur = cur->next;
    }
    bef->next = cur->next;
    cur->next->prev = bef;
    tmp = cur->data;
    free(cur);
    return tmp;
}

 

 

 

 

전체 코드와 실행결과이다.

 

전체 코드

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

typedef struct _doubNode
{
    struct _doubNode *prev;
    int data;
    struct _doubNode *next;
} DNode;

void AddFront(DNode **head, int val)
{
    DNode *temp = *head;
    DNode *newnode = (DNode *)malloc(sizeof(DNode));
    newnode->data = val;
    if (*head == NULL)
    {
        newnode->prev = NULL;
        newnode->next = NULL;
        *head = newnode;
        return;
    }
    temp->prev = newnode;
    newnode->prev = NULL;
    newnode->next = temp;
    *head = newnode;
}

void AddMid(DNode **head, int val, int index) // 뒤에서부터의 인덱스 값
{
    DNode *temp = *head;
    DNode *newnode = (DNode *)malloc(sizeof(DNode));
    newnode->data = val;
    if (*head == NULL)
    {
        newnode->prev = NULL;
        newnode->next = NULL;
        *head = newnode;
        return;
    }

    for (int i = 0; i < index; i++)
    {
        temp = temp->next;
    }
    newnode->next = temp->next;
    newnode->next->prev = newnode;
    newnode->prev = temp;
    temp->next = newnode;
}

void PrintNode(DNode *head)
{
    DNode *temp = head;
    do
    {
        printf("%d-> ", temp->data);
        temp = temp->next;
    } while (temp->next != NULL);
    printf("\n");
}

int DelNode(DNode **head, int val)
{
    DNode *bef = *head;
    DNode *cur = *head;
    int tmp = 0;
    if (*head == NULL)
    {
        printf("삭제할 값이 없습니다.\n");
        return -1;
    }

    while (cur->data != val)
    {
        bef = cur;
        cur = cur->next;
    }
    bef->next = cur->next;
    cur->next->prev = bef;
    tmp = cur->data;
    free(cur);
    return tmp;
}

int main(void)
{
    DNode *head = (DNode *)malloc(sizeof(DNode));
    AddFront(&head, 2);
    AddFront(&head, 6);
    AddFront(&head, 4);
    AddFront(&head, 8);
    PrintNode(head);
    AddMid(&head, 9, 2);
    PrintNode(head);
    printf("Deleted : %d\n", DelNode(&head, 6));
    printf("Deleted : %d\n", DelNode(&head, 4));
    PrintNode(head);

    return 0;
}

 

 

실행 결과