★ 3. 선형 연결 리스트 구현하기[추가]

기존 선형 연결 리스트에서

좀 더 추가된 소스입니다.

#include <iostream>
#include <stdlib.h>

using namespace std;

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

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

// # 헤드 구조체 #
struct tagListHead
{
 tagListNode* head;
};

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

// # 연결 리스트에 노드를 추가하는 함수 #
void addLastNode(tagListHead* head, int x)
{
 tagListNode* newNode;
 tagListNode* p;

 // # 새로 추가할 노드를 저장할 메모리 할당 #
 newNode = new tagListNode;
 newNode->data = x;  // # 데이터 필드에 데이터 설정 #
 newNode->link = NULL; // # 링크 필드에 NULL값 지정 #

 // # 빈 연결 리스트면 추가되는 데이터를 head가 가리키도록 함. #
 if (head->head == NULL)
 {
  head->head = newNode;
  return;
 }
 
 // # 이미 추가된 노드가 존재한다면? #
 p = head->head;

 // # 마지막 노드가 될 때 까지 반복 수행 #
 while (p->link != NULL)
 {
  // # 링크 p가 자신의 다음 노드를 가리킴 #
  p = p->link;
 }

 // # 맨 마지막 노드가 새로운 노드를 가리키게 연결 #
 p->link = newNode;
}

// # 연결 리스트를 출력하는 함수 #
void printList(tagListHead* head)
{
 tagListNode* p;  // # 노드를 가리키는 변수 #
 p = head->head;

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

// # 연결 리스트 중간에 노드를 삽입하는 함수 #
void insertAfter(tagListHead* head, int x, tagListNode* p)
{
 tagListNode* newNode;

 // # 새로 추가할 노드를 저장할 메모리 할당 #
 newNode = new tagListNode;
 newNode->data = x; // # 데이터 필드에 데이터 설정 #

 if (head->head == NULL)  // # 첫 번째 추가되는 데이터라면 #
 {
  newNode->link = NULL; // # 링크 필드에 NULL값 설정 #
  head->head = newNode;
 }
 else if (head == NULL)  // # head가 NULL이면 첫 번째 노드로 삽입 #
 {
  newNode->link = head->head->link;
  head->head = newNode;
 }
 else      // # p 다음에 삽입 #
 {
  newNode->link = p->link;
  p->link = newNode;
 }
}

// # 연결 리스트에서 데이터 검색하는 함수 #
tagListNode* findNode(tagListHead* head, int x)
{
 tagListNode* p;
 p = head->head;   // # 링크드 리스트의 처음 노드인 head를 p의 초기값으로 지정 #
 while (p != NULL)  // # NULL에 도달하면 반복문을 벗어남 #
 {
  if (p->data == x) // # 데이터를 찾음 #
  {
   break;
  }
  p = p->link;
 }
 return p;
}

// # 마지막 노드 삭제하는 함수 #
void deleteLastNode(tagListHead* head)
{
 tagListNode* previous; // # 삭제하려는 이전 노드 #
 tagListNode* current; // # 삭제하려는 노드 #

 // # head가 NULL이면 삭제할 노드가 없으므로 함수를 종료 #
 if (head->head == NULL) return;

 // # head의 다음 노드가 NULL이면 헤드를 삭제한 후 함수를 종료 #
 if (head->head->link == NULL)
 {
  delete(head->head);
  head->head = NULL;
  return;
 }
 else // # 이미 추가된 노드가 존재하면 previous가 head가 가리키는 곳 #
 {  // # 즉, 첫 번째 노드를 가리키고, current는 두 번째 노드를 가리킨다. #
  previous = head->head;
  current = head->head->link;
  // # previous라는 포인터를 하나 더 만들어 #
  // # current가 마지막 노드를 가리킬 때까지 진행시킨다. #
  while (current->link != NULL)
  {
   previous = current;
   current = current->link;
  }
  // # current가 가리키는 노드를 메모리 해제하고 #
  // # previous가 가리키는 노드의 링크에 NULL을 저장한다. #
  delete(current);
  previous->link = NULL;
 }
}

// # 삭제하고자 하는 데이터가 저장된 노드 삭제하는 함수 #
int deleteNode(tagListHead* head, int x)
{
 tagListNode* previous;
 tagListNode* current;

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

 previous = head->head;
 current = previous->link;
 while (previous != NULL)
 {
  if (current->data == x)
   break;
  previous = previous->link;
  current = previous->link;
 }

 // # current가 NULL이 아니면 연결 리스트에 #
 // # 삭제하고자 하는 데이터가 존재하는 것임 #
 if (current != NULL)
 {
  // # previous의 다음 노드는 current의 다음 노드가 됨 #
  previous->link = current->link;
  delete(current);  // # current가 가리키는 노드를 메모리 해제 #
  return 1;    // # 삭제에 성공했으면 1을 되돌림 #
 }

 // # current가 NULL이면 연결 리스트에 삭제하고자 하는 데이터가 존재하지 않음 #
 else
  return 0;    // # 삭제에 실패했으면 0을 되돌림 #
}

// # 역순으로 순회하는 함수 #
void reverse(tagListHead* head)
{
 // # 순회 포인터로 p, q, r을 사용 #
 tagListNode* p;
 tagListNode* q;
 tagListNode* r;

 p = head->head;  // # p는 역순으로 만들 리스트 #
 q = NULL;   // # q는 역순으로 만들 노드 #
 r = NULL;

 while (p != NULL)
 {
  // # r은 역순으로 된 리스트. r은 q, q는 p를 차례로 따라간다 #
  r = q;
  q = p;
  p = p->link;
  q->link = r;  // # q의 링크 방향을 바꾼다 #
 }
 head->head = q;   // # 역순으로 된 리스트의 헤드 포인터 #
}

// # 모든 노드 삭제하는 함수 #
void deleteLinkedListHead(tagListHead* head)
{
 tagListNode* p;
 while (head->head != NULL)
 {
  p = head->head;
  head->head = head->head->link;
  delete(p);
  p = NULL;
 }
}

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

 head = createLinkedHeadList();

 cout << "리스트에 노드 추가하기!" << endl;
 addLastNode(head, 10);
 addLastNode(head, 20);
 addLastNode(head, 30);
 addLastNode(head, 40);
 addLastNode(head, 50);
 addLastNode(head, 60);
 printList(head);

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

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

 cout << "마지막 노드 삭제하기!" << endl;
 deleteLastNode(head);
 printList(head);

 cout << "리스트 원소를 역순으로 변환하기!" << endl;
 reverse(head);
 printList(head);

 cout << "리스트 해제하기!" << endl;
 deleteLinkedListHead(head);
 printList(head);

 getchar();
}