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

이중 연결 리스트 Double Linked List

이중 연결 리스트입니다.

일반 연결 리스트와 다르게 한 노드를 기준으로 그 전 노드를 가리키는 before, 그 다음 노드를 가리키는 next 포인터가 존재합니다.

첫 번째 데이터가 tail에 삽입된 모습입니다.

노드가 하나뿐이라 head=tail=뉴노드 입니다.

뉴노드를 삽입하는 모습입니다.

뉴노드의 next은 (헌)노드,

(헌)노드의 before는 뉴노드 입니다.

이후 뉴노드는 tail이 됩니다.

head는 그대로인 모습입니다.

노드를 삭제하는 모습입니다.

더미노드를 만들어 삭제할 부분인 tail를 가리키게 합니다.

tail는 tail->before을 가리킵니다.

삭제될 노드를 가리키는 tail->next는 NULL이 됩니다

더미노드의 메모리를 해제합니다.

코드입니다.

포스팅하려고 스스로 몇 번 해본 것이 이해에 도움이 되는 것 같습니다. ..

0 구조체 정의와 초기화

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

1 tail에 데이터 삽입

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

2 tail의 데이터 삭제

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

3 데이터 조회

void PrintHead(List *list){ list->current = list->head; int num = list->NumOfData; cout << "-------*(Print from Head)*-------" << endl; while (num>0){ cout << list->current->data<<" "; list->current = list->current->next; num--; } cout << endl; cout << endl; } void PrintTail(List *list){ list->current = list->tail; int num = list->NumOfData; cout << "-------*(Print from Tail)*-------" << endl; while (num>0){ cout << list->current->data << " "; list->current = list->current->before; num--; } cout << endl; cout << endl; }

4 테스트용 메인 함수와 결과값

int main(){ List *LList = (List*)malloc(sizeof(List)); Initialize(LList); InsertTail(LList, 1); InsertTail(LList, 2); InsertTail(LList, 3); InsertTail(LList, 4); InsertTail(LList, 5); PrintHead(LList); PrintTail(LList); DeleteTail(LList); DeleteTail(LList); PrintHead(LList); PrintTail(LList); return 0; }

이중 원형 연결 리스트 Doubly Circular Linked List

이중 연결 리스트에서 head와 tail을 이어준 모습이 이중 원형 연결 리스트입니다.

코드입니다.

0 구조체 정의와 초기화

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

1 tail에 데이터 삽입

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

2 tail의 데이터 삭제

void DeleteTail(List *list){ if (list->NumOfData == 0){ cout << "EEERRRRRRRROOOOORRRRRRRR :: 삭제할 노드가 없습니다" << endl; return; } Node *Dummy = (Node*)malloc(sizeof(Node)); Dummy = list->tail; list->tail = list->tail->before; list->tail->next = list->head; list->head->before = list->tail; free(Dummy); (list->NumOfData)--; }

3 데이터 조회

void Print(List *list){ if (list->NumOfData == 0){ cout << "데이터가 없어 출력할 수 없습니다"<<endl; return; } list->current = list->head; int num = list->NumOfData*3; cout << "-------*(Print from Head)*-------" << endl; while (num>0){ cout << list->current->data<<" "; list->current = list->current->next; num--; } cout << endl; cout << endl; } void Print2(List *list){ if (list->NumOfData == 0){ cout << "데이터가 없어 출력할 수 없습니다"<<endl; return; } list->current = list->tail; int num = list->NumOfData * 3; cout << "-------*(Print from Tail)*-------" << endl; while (num>0){ cout << list->current->data << " "; list->current = list->current->before; num--; } cout << endl; cout << endl; }

4 테스트용 메인 함수와 결과값

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

원형 확인을 위해 데이터를 앞뒤로 3회 출력한 모습입니다

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

부족한 부분이 있으면 고쳐주시면 감사드리겠습니다