연결 리스트 (Linked List) - 원형 연결 리스트

* 열혈강의 자료구조 책 + 인터넷 + a

원형 연결 리스트 Circular Linked List

원형 연결 리스트입니다.

그림처럼 하나로 쭉 이어지며, tail이 별도로, 반드시 필요하지는 않습니다.

head와 tail을 구분지어서 tail과 tail->next(head)로 사용하는 경우도 있습니다.

저는 구분짓지 않고 head만을 사용하였습니다. (따라서 마치 tail과도 같은 역할을 수행하게 되었습니다..)

리스트가 텅 빈 상태에서 뉴노드를 넣게 되면 보여지는 모습입니다

노드가 하나 이상일 때 노드를 추가하면 나타나는 모습입니다.

이러한 구조 때문에 head부터 리스트의 데이터들을 출력하면 생각하던 결과와 다소 다른 값이 출력됩니다.

출력값은 아래 스크린샷에 있습니다. (1에서 5.. 순서대로 출력하려면 head->next부터 출력해야 합니다)

head노드를 삭제하는 모습입니다. 일반 연결 리스트와 마찬가지로 더미노드를 이용하였습니다.

head의 전에 있던 노드와 head->next 노드를 연결해야 하기 때문에 before노드가 추가적으로 필요합니다.

저는 연결 리스트의 데이터 갯수를 구하여 before 노드를 head 앞까지 이동시키는 방법을 사용하였습니다.

head를 before위치로 옮긴 후 Dummy노드를 삭제하는, 메모리가 해제되는 모습입니다

코드입니다.

0 구조체 선언과 초기화

#include<iostream> using namespace std; typedef struct _Node{ int data; struct _Node *next; } Node; typedef struct _List{ Node *head; // Node *tail; Node *current; Node *before; int NumOfData; } List; void Initialize(List *list){ list->head = NULL; // list->tail = NULL; list->current = NULL; list->before = NULL; list->NumOfData = 0; }

1 데이터 삽입 (head에 삽입됨)

void InsertHead(List *list, int data){ Node *newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; newnode->next = NULL; if (list->NumOfData == 0){ list->head = newnode; list->head->next = newnode; } else{ newnode->next = list->head->next; list->head->next = newnode; } (list->NumOfData)++; }

2 데이터 삭제 (head에 있던 데이터가 삭제됨)

void DeleteHead(List *list){ if (list->NumOfData == 0){ cout << "EEERRRRRRRROOOOORRRRRRRR :: 삭제할 노드가 없습니다" << endl; return; } else if (list->NumOfData == 1){ list->head = NULL; (list->NumOfData)--; return; } int num = list->NumOfData; list->current = list->head->next; while (num > 2){ list->current = list->current->next; num--; } list->before = list->current; Node *Dummy = (Node*)malloc(sizeof(Node)); Dummy = list->head; list->before->next = list->head->next; list->head = list->before; free(Dummy); (list->NumOfData)--; }

3 데이터 출력

void Print(List *list){ list->current = list->head; int num = list->NumOfData*3; cout << "-------*리스트를 출력합니다*-------" << endl; while (num>0){ cout << list->current->data << " "; list->current = list->current->next; num--; } cout << endl; cout << endl; } void Print2(List *list){ list->current = list->head->next; int num = list->NumOfData * 3; cout << "-------*리스트2를 출력합니다*-------" << endl; while (num>0){ cout << list->current->data << " "; list->current = list->current->next; num--; } cout << endl; cout << endl; }  

4 테스트용 메인 함수+결과

int main(){ List *LList = (List*)malloc(sizeof(List)); Initialize(LList); InsertHead(LList, 1); InsertHead(LList, 2); InsertHead(LList, 3); InsertHead(LList, 4); InsertHead(LList, 5); Print(LList); Print2(LList); DeleteHead(LList); DeleteHead(LList); Print(LList); Print2(LList); return 0; }

출력방법 1은 head부터 출력, 방법2는 head->next부터 출력한 모습입니다

(원형의 확인을 위해 리스트를 3번 출력했습니다.)

-----------------------------------------------------------------------------------------------------------------------------------------

개인적으로 작성해본 내용이라 틀린 부분이 있으면 지적해주세요..