★ 2. 선형 연결 리스트 구현하기

선형 연결 리스트 구현

기능별로 함수로 나누어서 구현하였습니다.

출처는 대학 교재로 사용하던 "한번에 이해되는 C 자료구조" 책을 보면서..

#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 main()
{
 tagListHead* _head;
 _head = createLinkedHeadList();
 cout << "[1] 연결 리스트 생성하기!" << endl;
 printList(_head);

 cout << "[2] 연결 리스트에 3개의 노드 추가하기!" << endl;
 addLastNode(_head, 50);
 addLastNode(_head, 20);
 addLastNode(_head, 30);
 printList(_head);

 cout << "[3] 연결 리스트 마지막에 노드 한 개 추가하기!" << endl;
 addLastNode(_head, 50);
 printList(_head);

 getchar();
}