★ 7. 이중 연결 리스트 구현하기

- 이중 연결 리스트 -

             (이중 원형 연결리스트)

각 기능별로 함수로 구현이 된 이중 연결 리스트 예제 소스입니다.

"한번에 이해되는 C 자료구조" 책을 참조하였습니다.

// # 이중 원형 연결 리스트에 원소 추가, 삽입하기 #
#include <iostream>
#include <stdlib.h>

using namespace std;

typedef int element;

struct tagListNode
{
 tagListNode* leftLink; // # 왼쪽 노드를 가리키는 링크 필드 #
 element data;   // # 노드를 구성하는 데이터 필드 #
 tagListNode* rightLink; // # 오른쪽 노드를 가리키는 링크 필드 #
};

// # 헤더의 정보를 저장할 구조체 선언 #
struct tagListHead
{
 tagListNode* head;
};

// # 노드를 동적으로 생성하는 함수 #
tagListNode* getNode()
{
 tagListNode* newNode;
 newNode = new tagListNode;

 if (newNode == NULL)
 {
  fprintf(stderr, "메모리 할당 에러\n");
  exit(1);
 }
 return newNode;
}

// # 연결 리스트를 초기화하는 함수 #
tagListHead* createLinkedListHead()
{
 tagListHead* head;

 // # 헤더의 공간을 확보 #
 head = new tagListHead;

 tagListNode* newNode = getNode();

 head->head = newNode;
 head->head->leftLink = head->head;
 head->head->rightLink = head->head;
 return head;
}

// # 연결 리스트를 출력하는 함수 #
void printList(tagListHead* head)
{
 tagListNode* p;

 p = head->head->rightLink;

 if (p == head->head)
 {
  cout << "공백 리스트";
  return;
 }
 do {
  printf("%5d", p->data);
  p = p->rightLink;
 } while (p != head->head);
 cout << endl;
}

// # 노드값을 검색하는 함수 #
tagListNode* findNode(tagListHead* head, element x)
{
 tagListNode* p;

 p = head->head->rightLink;

 while (p != head->head) // # NULL에 도달하면 반복문을 벗어남 #
 {
  if (p->data == x) // # 데이터를 찾음 #
   break;
  p = p->rightLink;
 }
 return p;
}

// # 새로운 노드를 pre의 오른쪽에 삽입 #
void dinsert(tagListHead* head, tagListNode* pre, element x)
{
 // # 새로 추가하라 노드를 저장할 메모리 할당 #
 tagListNode* newNode = getNode();

 newNode->data = x;   // # 데이터 필드에 데이터 설정 #

 newNode->leftLink = pre;
 newNode->rightLink = pre->rightLink;
 pre->rightLink->leftLink = newNode;
 pre->rightLink = newNode;
}

// # 노드를 삭제하는 함수 #
void ddelete(tagListHead* head, tagListNode* deleted)
{
 deleted->leftLink->rightLink = deleted->rightLink;
 deleted->rightLink->leftLink = deleted->leftLink;

 delete(deleted);
}

void main()
{
 tagListHead* head;
 tagListNode* p;

 head = createLinkedListHead();

 cout << "연결 리스트 생성하기!" << endl;
 printList(head);

 cout << "연결 리스트에 3개의 노드 추가하기!" << endl;
 dinsert(head, head->head, 10);
 dinsert(head, head->head, 20);
 dinsert(head, head->head, 30);
 printList(head);

 cout << "데이터가 20인 노드의 위치를 찾음 40을 20뒤에 삽입한다." << endl;
 p = findNode(head, 20);
 dinsert(head, p, 40);
 printList(head);

 cout << "데이터가 20인 노드 삭제하기!" << endl;
 ddelete(head, p);
 printList(head);

 getchar();

}