★ 5. 원형 연결 리스트 구현하기

- 원형 연결 리스트 -

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

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

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

using namespace std;

typedef int element;

struct tagListNode
{
 // # 노드를 구성하는 데이터 필드 #
 element data;

 // # 다음 노드를 가리키는 링크 필드 #
 tagListNode* link;
};

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

// # 연결 리스트를 초기화하는 함수 #
tagListHead* createLinkedListHead()
{
 tagListHead* head;
 // # 헤더의 공간을 확보 #
 head = new tagListHead;
 head->head = NULL;

 return head;
}

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

 if (head->head == NULL) return;

 p = head->head;

 do {
  cout << p->data;
  p = p->link;
 } while (p != head->head);
 cout << endl;
}

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

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

 return newNode;
}

// # 원형 연결 리스트 처음에 노드를 삽입하는 함수 #
void addFrontNode(tagListHead* head, element x)
{
 tagListNode* newNode;
 tagListNode* p;

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

 if (head->head == NULL) // # 첫 번째 추가되는 데이터라면 #
 {
  head->head = newNode;
  newNode->link = newNode;
 }
 else
 {
  p = head->head;
  while (p->link != head->head)
   p = p->link;

  newNode->link = p->link;
  p->link = newNode;
  head->head = newNode;
 }
}

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

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

// # 원형 연결 리스트 중간에 노드를 삽입하는 함수 #
void insertMiddleNode(tagListHead* head, tagListNode* pre, element x)
{
 tagListNode* newNode;
 tagListNode* p;
 // # 새로 추가할 노드를 저장할 메모리 할당 #
 newNode = getNode();
 newNode->data = x;  // # 데이터 필드에 데이터 설정 #
 if (head->head == NULL) // # 첫 번째 추가되는 데이터라면 #
 {
  head->head = newNode;
  newNode->link = newNode;
 }
 else
 {
  newNode->link = pre->link;
  pre->link = newNode;
 }
}

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

 head = createLinkedListHead();

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

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

 cout << "연결 리스트 처음에 노드 한개 추가하기!" << endl;
 addFrontNode(head, 40);
 printList(head);

 cout << "데이터가 30인 노드의 위치를 찾고 50을 30뒤에 삽입!" << endl;
 p = findNode(head, 30);
 insertMiddleNode(head, p, 50);
 printList(head);

 getchar();
}