양방향 연결 리스트 예제

이번 예제문제는 앞서 구현한 양방향 연결 리스트에서 head와 tail에 더미노드를 추가하고 더미노드를 기반으로 양방향 연결 리스트를 구현하는 것이다.

이또한 더미를 추가하는 것 말고는 크게 다른 점이 없기 때문에 큰 어려움은 없이 구현했다.

문제

• 양방향 연결 리스트
• 더미 노드가 리스트의 앞과 뒤에 각각 존재
• 포인터 변수 head와 tail이 있어서 리스트의 앞과 뒤를 각각 가르킨다.
• 노드는 꼬리에서 추가
• 데이터를 삭제하는 LRemove 함수를 구현

---

헤더파일

#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
   Data data;
   struct _node *next;
   struct _node *prev;
} Node;

typedef struct _dbDLinkedList
{
   Node *head;
   Node *tail;
   Node *cur;
   int numOfData;
} DBDLinkedList;

typedef DBDLinkedList List;

void ListInit(List *plist);
void LInsert(List *plist, Data data);

int LFirst(List *plist, Data *pdata);
int LNext(List *plist, Data *pdata);

Data LRemove(List *plist);
int LCount(List *plist);

#endif

소스파일

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

void ListInit(List *plist)
{
   plist->head = (Node *)malloc(sizeof(Node));
   plist->tail = (Node *)malloc(sizeof(Node));

   plist->head->next = plist->tail;
   plist->head->prev = NULL;
   plist->tail->prev = plist->head;
   plist->tail->next = NULL;

   plist->numOfData = 0;
}

void LInsert(List *plist, Data data)
{
   Node *newNode = (Node *)malloc(sizeof(Node));
   newNode->data = data;

   // next 설정
   plist->tail->prev->next = newNode;
   newNode->next = plist->tail;

   // prev 설정
   newNode->prev = plist->tail->prev;
   plist->tail->prev = newNode;

   (plist->numOfData)++;
}

int LFirst(List *plist, Data *pdata)
{
   if (plist->head->next == plist->tail)
   {
      return FALSE;
   }

   plist->cur = plist->head->next;

   *pdata = plist->cur->data;
   return TRUE;
}

int LNext(List *plist, Data *pdata)
{
   if (plist->cur->next == plist->tail)
   {
      return FALSE;
   }

   plist->cur = plist->cur->next;

   *pdata = plist->cur->data;

   return TRUE;
}

Data LRemove(List *plist)
{
   Node *rpos = plist->cur;
   Data rdata = rpos->data;

   plist->cur->prev->next = plist->cur->next;
   plist->cur->next->prev = plist->cur->prev;

   plist->cur = plist->cur->prev;

   free(rpos);
   (plist->numOfData)--;

   return rdata;
}

int LCount(List *plist)
{
   return plist->numOfData;
}

메인파일

#include <stdio.h>
#include "DBLinkedList.h"

int main()
{
   // 초기화
   List list;
   int data;
   ListInit(&list);

   // 데이터 저장
   LInsert(&list, 1);
   LInsert(&list, 2);
   LInsert(&list, 3);
   LInsert(&list, 4);
   LInsert(&list, 5);
   LInsert(&list, 6);
   LInsert(&list, 7);
   LInsert(&list, 8);

   // 저장된 데이터 조회
   if (LFirst(&list, &data))
   {
      printf("%d ", data);

      // 오른쪽 노드로 이동하며 데이터 조회
      while (LNext(&list, &data))
      {
         printf("%d ", data);
      }
      printf("\n");
      // 왼쪽 노드로 이동하며 데이터 조회
      while (LPrevious(&list, &data))
      {
         printf("%d ", data);
      }

      printf("\n\n");
   }

   return 0;
}

결과

전체 데이터의 개수 : 8 
8 7 6 5 4 3 2 1 

DELETE

전체 데이터의 개수 : 4
7 5 3 1