[Do it 알고리즘] 09. 리스트(2)
09. 리스트
09-3. 커서로 연결 리스트 만들기
커서로 연결 리스트 만들기
연결리스트 : 노드의 삽입, 삭제를 데이터 이동 없이 수행, 삽입과 삭제를 수행할 때마다 노드용 객체를 위한 메모리 영역을 만들고 해제하는 과정 필요
프로그램 실행 중에 데이터의 개수가 크게 바뀌지 않고 데이터 개수의 최댓값을 미리 알 수 있다고 가정하면, 아래 그림과 같은 배열을 사용해 효율적으로 연결 리스트 운용 가능
배열의 커서 : 다음 노드가 들어 있는 요소의 인덱스에 대한 값
/* 커서에 의한 선형 리스트(헤더부) */
#ifndef ___ArrayLinkedList
#define ___ArrayLinkedList
#include "Member.h"
#define Null –1 /* 빈 커서 */
typedef int Index; /* 커서 형 */
/*--- 노드 ---*/
typedef struct {
Member data; /* 데이터 */
Index next; /* 뒤쪽노드 */
Index Dnext; /* 프리 리스트의 뒤쪽노드 */
} Node;
/*--- 선형 리스트 ---*/
typedef struct {
Node *n; /* 리스트 본체(배열) */
Index head; /* 머리노드 */
Index max; /* 사용 중인 꼬리 레코드 */
Index deleted; /* 프리 리스트의 머리노드 */
Index crnt; /* 주목노드 */
} List;
/*--- 선형 리스트를 초기화(가장 큰 요솟수는 size) ---*/
void Initialize(List *list, int size);
/*--- 함수 compare에 의해 x와 같은 것으로 판단되는 노드를 검색 ---*/
Index search(List *list, const Member *x,
int compare(const Member *x, const Member *y));
/*--- 머리에 노드를 삽입 ---*/
void InsertFront(List *list, const Member *x);
/*--- 꼬리에 노드를 삽입 ---*/
void InsertRear(List *list, const Member *x);
/*--- 머리노드를 삭제 ---*/
void RemoveFront(List *list);
/*--- 꼬리노드를 삭제 ---*/
void RemoveRear(List *list);
/*--- 주목노드를 삭제 ---*/
void RemoveCurrent(List *list);
/*--- 모든 노드를 삭제 ---*/
void Clear(List *list);
/*--- 주목노드의 데이터를 나타냄 ---*/
void PrintCurrent(const List *list);
/*--- 주목노드의 데이터를 나타냄(줄바꿈 문자 붙임) ---*/
void PrintLnCurrent(const List *list);
/*--- 모든 노드의 데이터를 나타냄 ---*/
void Print(const List *list);
/*--- 선형 리스트의 뒤처리 ---*/
void Terminate(List *list);
#endif
/* 커서에 의한 선형 리스트(소스부) */
#include <stdio.h>
#include <stdlib.h>
#include "Member.h"
#include "ArrayLinkedList.h"
/*--- 삽입할 레코드의 인덱스를 구한다. ---*/
static Index GetIndex(List *list)
{
if (list->deleted == NULL) /* 삭제할 레코드가 없는 경우 */
return ++(list->max);
else {
Index rec = list->deleted;
list->deleted = list->n[rec].Dnext;
return rec;
}
}
/*--- 지정된 레코드를 삭제 리스트에 등록한다. ---*/
static void DeleteIndex(List *list, Index idx)
{
if (list->deleted == NULL) { /* 삭제할 레코드가 없는 경우 */
list->deleted = idx;
list->n[idx].Dnext = NULL;
}
else {
Index ptr = list->deleted;
list->deleted = idx;
list->n[idx].Dnext = ptr;
}
}
/*--- n이 가리키는 노드의 각 멤버에 값을 설정 ----*/
static void SetNode(Node *n, const Member *x, Index next)
{
n->data = *x; /* 데이터 */
n->next = next; /* 뒤쪽노드에 대한 포인터 */
}
/*--- 선형 리스트를 초기화(가장 큰 요소수는 size) ---*/
void Initialize(List *list, int size)
{
list->n = calloc(size, sizeof(Node));
list->head = NULL; /* 머리노드 */
list->crnt = NULL; /* 주목노드 */
list->max = NULL;
list->deleted = NULL;
}
/*--- 함수 compare 의해 x와 같은 노드를 검색 ---*/
Index search(List *list, const Member *x, int compare(const Member *x, const Member *y))
{
Index ptr = list->head;
while (ptr != NULL) {
if (compare(&list->n[ptr].data, x) == 0) {
list->crnt = ptr;
return ptr; /* 검색 성공 */
}
ptr = list->n[ptr].next;
}
return NULL; /* 검색 실패 */
}
/*--- 머리에 노드를 삽입 ---*/
void InsertFront(List *list, const Member *x)
{
Index ptr = list->head;
list->head = list->crnt = GetIndex(list);
SetNode(&list->n[list->head], x, ptr);
}
/*--- 꼬리에 노드를 삽입 ---*/
void InsertRear(List *list, const Member *x)
{
if (list->head == NULL) /* 비어있는 경우 */
InsertFront(list, x); /* 머리에 삽입 */
else {
Index ptr = list->head;
while (list->n[ptr].next != NULL)
ptr = list->n[ptr].next;
list->n[ptr].next = list->crnt = GetIndex(list);
SetNode(&list->n[list->n[ptr].next], x, NULL);
}
}
/*--- 머리노드를 삭제 ---*/
void RemoveFront(List *list)
{
if (list->head != NULL) {
Index ptr = list->n[list->head].next;
DeleteIndex(list, list->head);
list->head = list->crnt = ptr;
}
}
/*--- 꼬리노드를 삭제 ---*/
void RemoveRear(List *list)
{
if (list->head != NULL) {
if (list->n[list->head].next == NULL) /* 노드가 하나만 있으면 */
RemoveFront(list); /* 머리노드를 삭제 */
else {
Index ptr = list->head;
Index pre;
while (list->n[ptr].next != NULL) {
pre = ptr;
ptr = list->n[ptr].next;
}
list->n[pre].next = NULL;
DeleteIndex(list, ptr);
list->crnt = pre;
}
}
}
/*--- 주목노드를 삭제 ---*/
void RemoveCurrent(List *list)
{
if (list->head != NULL) {
if (list->crnt == list->head) /* 머리노드를 주목하고 있으면 */
RemoveFront(list); /* 머리노드를 삭제 */
else {
Index ptr = list->head;
while (list->n[ptr].next != list->crnt)
ptr = list->n[ptr].next;
list->n[ptr].next = list->n[list->crnt].next;
DeleteIndex(list, list->crnt);
list->crnt = ptr;
}
}
}
/*--- 모든 노드를 삭제 ---*/
void Clear(List *list)
{
while (list->head != NULL) /* 텅 빌 때까지 */
RemoveFront(list); /* 머리노드를 삭제 */
list->crnt = NULL;
}
/*--- 주목노드의 데이터를 출력 ---*/
void PrintCurrent(const List *list)
{
if (list->crnt == NULL)
printf("주목노드가 없습니다.");
else
PrintMember(&list->n[list->crnt].data);
}
/*--- 주목노드의 데이터를 출력(줄바꿈 문자 붙임) ---*/
void PrintLnCurrent(const List *list)
{
PrintCurrent(list);
putchar('\n');
}
/*--- 모든 노드의 데이터를 출력 ---*/
void Print(const List *list)
{
if (list->head == NULL)
puts("노드가 없습니다.");
else {
Index ptr = list->head;
puts("【 모두 보기 】");
while (ptr != NULL) {
PrintLnMember(&list->n[ptr].data);
ptr = list->n[ptr].next; /* 뒤쪽노드 */
}
}
}
/*--- 선형 리스트의 뒤처리 ---*/
void Terminate(List *list)
{
Clear(list); /* 모든 노드를 삭제 */
free(list->n);
}
커서의 자료형 Index
커서의 자료형
단순한 정수 값을 가지기 때문에 int형과 동일하게 정의함
노드의 자료형 Node
연결 리스트의 노드를 의미하는 구조체
커서 next의 자료형은 커서의 자료형인 Index
연결 리스트를 관리하는 구조체 List
연결 리스트를 관리하는 구조체
배열의 비어 있는 요소 처리하기
[a] 연결 리스트에 A->B->C->D가 나열된 상태
이때, 배열에 데이터가 들어 있는 순서는 C->A->D->B
[b] 연결 리스트의 머리에 노드 E를 삽입한 다음의 상태
배열에 저장한 데이터의 물리적인 위치는 연결 리스트에 저장된 데이터의 논리적인 순서와 다름
[c] 3번째 노드 B를 삭제한 다음의 상태
노드를 삭제하면 3번째 레코드(배열의 3번째 인덱스에 들어 있는 노드)가 비어 있는 상태.
이때 노드 B를 삭제하면 노드 A의 다음 노드는 C로 바뀌므로, 노드 A의 커서 값도 3에서 0으로 업데이트됨
프리 리스트
'사용하지 않는 빈 배열', 즉, 삭제한 여러 레코드를 관리하기 위해 사용하는 자료구조
'커서로 연결 리스트 만들기'와 삭제한 레코드를 관리하기 위한 프리 리스트를 결합해 구현
노드용 구조체 Node와 연결 리스트를 관리하는 구조체 List에 포인터 버전에 없는 멤버 추가
- Dnext : 프리 리스트의 다음 노드를 가리키는 커서
- deleted : 프리 리스트의 머리 노드를 가리키는 커서
- max : 배열의 가장 꼬리 쪽에 들어 있는 노드의 레코드 번호를 의미
[a] 연결 리스트에 5개의 노드 A->B->C->D->E 저장, 프리리스트는 3->1->5
연결 리스트 구조체 List의 멤버 deleted의 값은 프리 리스트의 머리 노드의 인덱스 값
[b] 연결 리스트 꼬리에 노드 F를 삽입한 이후의 상태
노드를 삽입하는 위치는 프리 리스트 3, 1 ,5 가운데 머리 노드의 값 사용,
따라서 노드 F를 3번째 레코드에 저장하고 프리 리스트에서 3을 삭제해 1->5로 만듦
이때 max값은 여전히 7 유지
[c] 노드 D를 삭제한 다음의 상태. 7번째 레코드에 넣어둔 데이터를 삭제했기 때문에 7을 프리 리스트의 머리 노드로 추가, 프리 리스트는 7->1->5
09-4. 원형 이중 연결 리스트
원형 리스트
꼬리 노드가 머리 노드를 가리키는 선형 리스트
꼬리 노드의 다음 노드를 가리키는 포인터가 NULL이 아니라 머리 노드의 포인터 값임
list : 리스트를 관리하는 구조체 포인터
빈 원형 리스트를 판단하는 방법
list->head == NULL /* 선형 리스트가 비어 있는지 확인합니다. */
노드가 1개인 원형 리스트를 판단하는 방법
list->head->next == list->head /* 노드가 1개인지 확인합니다. */
머리 노드인지 판단하는 방법
p == list->head /* p가 가리키는 노드가 머리 노드인지 확인합니다. */
꼬리 노드인지 판단하는 방법
p->next == list->head /* p가 가리키는 노드가 꼬리 노드인지 확인합니다. */
이중 연결 리스트
다음 노드는 찾기 쉽지만 앞쪽의 노드는 찾을 수 없다는 선형 리스트의 단점 보완.
각 노드에는 다음 노드에 대한 포인터와 앞쪽의 노드에 대한 포인터가 주어짐
typedef struct __node {
Member data; /* 데이터 */
struct __node *prev; /* 앞쪽 노드에 대한 포인터 */
struct __node *next; /* 다음 노드에 대한 포인터 */
} Dnode;
머리 노드인지 판단하는 방법
p == list->head /* p가 가리키는 노드가 머리 노드인지 확인합니다. */
p->prev == NULL /* p가 가리키는 노드가 머리 노드인지 확인합니다. */
꼬리 노드인지 판단하는 방법
p->next == NULL /* p가 가리키는 노드가 꼬리 노드인지 확인합니다. */
원형 이중 연결 리스트
/* 원형 이중연결 리스트(헤더부) */
#ifndef ___CircDblLinkedList
#define ___CircDblLinkedList
#include "Member.h"
/*--- 노드 ---*/
typedef struct __node {
Member data; /* 데이터 */
struct __node *prev; /* 앞쪽노드에 대한 포인터 */
struct __node *next; /* 뒤쪽노드에 대한 포인터 */
} Dnode;
/*--- 원형 이중연결 리스트 ---*/
typedef struct {
Dnode *head; /* 머리 dummy 노드에 대한 포인터 */
Dnode *crnt; /* 주목노드에 대한 포인터 */
} Dlist;
/*--- 리스트를 초기화 ---*/
void Initialize(Dlist *list);
/*--- 주목노드의 데이터를 나타냄 ---*/
void PrintCurrent(const Dlist *list);
/*--- 주목노드의 데이터를 나타냄(줄바꿈 문자 붙임) ---*/
void PrintLnCurrent(const Dlist *list);
/*--- 함수 compare로 x와 같은 노드를 검색 ---*/
Dnode *search(Dlist *list, const Member *x,
int compare(const Member *x, const Member *y));
/*--- 모든 노드의 데이터를 리스트 순서로 나타냄 ---*/
void Print(const Dlist *list);
/*--- 모든 노드의 데이터를 리스트 순서 거꾸로 나타냄 ---*/
void PrintReverse(const Dlist *list);
/*--- 주목노드를 하나 뒤쪽으로 나아가도록 ---*/
int Next(Dlist *list);
/*--- 주목노드를 하나 앞쪽으로 되돌아가도록 ---*/
int Prev(Dlist *list);
/*--- p가 가리키는 노드 바로 뒤에 노드를 삽입 ---*/
void InsertAfter(Dlist *list, Dnode *p, const Member *x);
/*--- 머리에 노드를 삽입 ---*/
void InsertFront(Dlist *list, const Member *x);
/*--- 꼬리에 노드를 삽입 ---*/
void InsertRear(Dlist *list, const Member *x);
/*--- p가 가리키는 노드를 삭제 ---*/
void Remove(Dlist *list, Dnode *p);
/*--- 머리노드를 삭제 ---*/
void RemoveFront(Dlist *list);
/*--- 꼬리노드를 삭제 ---*/
void RemoveRear(Dlist *list);
/*--- 주목노드를 삭제 ---*/
void RemoveCurrent(Dlist *list);
/*--- 모든 노드를 삭제 ---*/
void Clear(Dlist *list);
/*--- 원형 이중연결 리스트의 뒤처리 ---*/
void Terminate(Dlist *list);
#endif
노드를 나타내는 구조체 Dnode
- data : 데이터
- prev : 앞쪽 노드에 대한 포인터
- next : 다음 노드에 대한 포인터
원형 이중 연결 리스트를관리하는 구조체 Dlist
선형 리스트의 List와 마찬가지로 머리 노드에 대한 포인터와 선택한 노드에 대한 포인터 존재
노드를 생성하는 AllocDnode 함수
Dnode형 객체를 생성하고 해당 객체의 포인터를 반환하는 함수
static Dnode *AllocDNode(void)
{
return calloc(1, sizeof(Dnode));
}
노드의 멤버 값을 설정하는 SetDnode 함수
Dnode형 객체의 멤버 값을 설정
첫 번째 매개변수 n에 전달받은 Dnode형 객체 포인터를 통해 멤버 값을 설정
객체 멤버인 data, prev, next에 두 번째 매개변수가 가리키는 객체의 값, 세 번째 매개변수와 네 번째 매개변수의 포인터 값 대입
static void SetDNode(Dnode *n, const Member *x, const Dnode *prev,
const Dnode *next)
{
n->data = *x; /* 데이터 */
n->prev = prev; /* 앞쪽노드에 대한 포인터 */
n->next = next; /* 뒤쪽노드에 대한 포인터 */
}
원형 이중 연결 리스트를 초기화하는 Initialize 함수
텅 비어 있는 상태의 원형 이중 연결 리스트를 만드는 함수
비어 있는 상태의 노드 1개를 만들어 리스트를 초기화
더미 노드 : 초기화를 통해 만들어낸 노드. 노드의 삽입, 삭제를 수행하기 위해 리스트의 머리에 위치함
더미 노드를 만든 다음 더미 노드의 앞쪽 포인터 prev와 뒤쪽 포인터 next 모두 자기 자신(더미 노드)을 가리키도록 설정하면 초기화 완료
void Initialize(Dlist *list)
{
Dnode *dummyNode = AllocDNode(); /* 더미 노드를 만듦 */
list->head = list->crnt = dummyNode;
dummyNode->prev = dummyNode->next = dummyNode;
}
리스트가 비어 있는지 검사하는 IsEmpty 함수
리스트가 비어 있는지를 검사하는 함수
더미 노드의 뒤쪽 포인터 list->head->next
가 더미 노드인 list->head
를 가리키면 비어 있는 상태라고 판단함
비어 있는 상태의 리스트는 list->head
, 더미 노드의 앞쪽 포인터인 list->head->prev
, 더미 노드의 뒤쪽 포인터인 list->head->next
의 3개 모두 더미 노드를 가리킴
함수의 반값은 리스트가 비어 있는 경우 1, 아닌 경우 0
static int IsEmpty(const Dlist *list)
{
return list->head->next == list->head;
}
선택한 노드의 데이터를 출력하는 PrintCurrent / PrintLnCurrent 함수
선택한 노드의 데이터를 출력하는 함수
즉,list->crnt
가 가리키는 노드의 데이터를 PrintMember 함수를 이용해 출력
리스트가 비어 있는 경우 '선택한 노드가 없습니다.'라는 메시지 출력
/*--- 주목노드의 데이터를 출력 ---*/
void PrintCurrent(const Dlist *list)
{
if (IsEmpty(list))
printf("주목노드가 없습니다.");
else
PrintMember(&list->crnt->data);
}
/*--- 주목노드의 데이터를 출력(줄바꿈 문자 붙임) ---*/
void PrintLnCurrent(const Dlist *list)
{
PrintCurrent(list);
putchar('\n');
}
노드를 검색하는 Search 함수
리스트에서 노드를 선형 검색하는 함수
머리 노드부터 뒤쪽 포인터를 이용해 순서대로 스캔,
이때 머리 노드는 더미 노드가 아니라 더미 노드의 다음 노드
검색을 시작하는 노드의 위치는 list->head
가 가리키는 노드가 아닌
list->head->next
가 가리키는 노드
Dnode *search(Dlist *list, const Member *x, int compare(const Member *x, const Member *y))
{
Dnode *ptr = list->head->next;
while (ptr != list->head) {
if (compare(&ptr->data, x) == 0) {
list->crnt = ptr;
return ptr; /* 검색 성공 */
}
ptr = ptr->next;
}
return NULL; /* 검색 실패 */
}
compare 함수로 비교한 결과가 0이면 검색 성공, 찾은 노드에 대한 포인터인 ptr 반환
이때, crnt는 찾은 노드(ptr)를 가리키도록 설정함
원형 이중 연결 리스트에서 p가 가리키는 노드의 위치를 판단하는 방법
p->prev == list->head /* p가 가리키는 노드가 머리 노드인지 확인합니다. */
p->prev->prev == list->head /* p가 가리키는 노드가 2번째 노드인지 확인합니다. */
p->next == list->head /* p가 가리키는 노드가 꼬리 노드인지 확인합니다. */
p->next->next == list->head /* p가 가리키는 노드가 2번째 노드인지 확인합니다. */
모든 노드를 순서대로 출력하는 Print 함수
리스트의 모든 노드를 머리부터 순서대로 출력하는 함수
list->head->next
부터 뒤쪽 포인터를 찾아가며 각 노드의 데이터 출력,
다시 head로 돌아오면 스캔 종료
void Print(const Dlist *list)
{
if (IsEmpty(list))
puts("노드가 없습니다.");
else {
Dnode *ptr = list->head->next;
puts("【 모두 보기 】");
while (ptr != list->head) {
PrintLnMember(&ptr->data);
ptr = ptr->next; /* 뒤쪽노드에 주목 */
}
}
}
모든 노드를 거꾸로 출력하는 PrintReverse 함수
리스트의 모든 노드를 꼬리부터 거꾸로 출력하는 함수
void PrintReverse(const Dlist *list)
{
if (IsEmpty(list))
puts("노드가 없습니다.");
else {
Dnode *ptr = list->head->prev;
puts("【 모두 보기 】");
while (ptr != list->head) {
PrintLnMember(&ptr->data);
ptr = ptr->prev; /* 앞쪽노드에 주목 */
}
}
}
선택한 노드의 다음으로 진행시키는 Next 함수
선택한 노드의 다음 노드로 진행시키는 함수
int Next(Dlist *list)
{
if (IsEmpty(list) || list->crnt->next == list->head)
return 0; /* 나아갈 수 없음 */
list->crnt = list->crnt->next;
return 1;
}
리스트가 비어 있지 않고 선택한 노드의 다음 노드가 있는 경우에만 동작함
선액한 노드가 다음 노드로 진행하는데 성공하면 1, 실패하면 0을 반환
선택한 노드의 앞쪽으로 진행시키는 Prev 함수
선택한 노드의 바로 앞쪽 노드로 되돌아가게 하는 함수
int Prev(Dlist *list)
{
if (IsEmpty(list) || list->crnt->prev == list->head)
return 0; /* 되돌아갈 수 없음 */
list->crnt = list->crnt->prev;
return 1;
}
바로 다음에 노드를 삽입하는 InsertAfter 함수
포인터 p가 가리키는 노드의 바로 다음에 노드를 삽입
void InsertAfter(Dlist *list, Dnode *p, const Member *x)
{
Dnode *ptr = AllocDNode();
Dnode *nxt = p->next;
p->next = p->next->prev = ptr;
SetDNode(ptr, x, p, nxt);
list->crnt = ptr; /* 삽입한 노드에 주목 */
}
1. 새로 삽입할 노드를 만들고 만든 노드의 앞쪽 포인터가 가리키는 노드는 B, 뒤쪽 포인터가 가리키는 노드는 C로 설정
2. 노드 B의 뒤쪽 포인터 p->next와 노드 C의 앞쪽 포인터 p->next->prev 모두 새로 삽입한 노드 ptr(노드 D)을 가리키도록 업데이트
3. 선택한 노드 list->crnt가 삽입한 노드를 가리키도록 업데이트
1. 만든 노드의 앞쪽 포인터와 뒤쪽 포인터는 더미 노드를 가리킴
2. 더미 노드의 뒤쪽 포인터와 앞쪽 포인터가 가리키는 노드는 A
3. 선택한 노드가 가리키는 노드는 A
머리에 노드를 삽입하는 InsertFront 함수
리스트의 머리에 노드를 삽입하는 함수, 더미 노드의 바로 뒤에 삽입
void InsertFront(Dlist *list, const Member *x)
{
InsertAfter(list, list->head, x);
}
즉, InsertAfter 함수를 사용해 list->head
가 가리키는 더미 노드 뒤에 노드를 삽입
꼬리에 노드를 삽입하는 InsertRear 함수
리스트의 꼬리에 노드를 삽입하는 함수
void InsertRear(Dlist *list, const Member *x)
{
InsertAfter(list, list->head->prev, x);
}
노드를 삭제하는 Remove 함수
p가 가리키는 노드를 삭제하는 함수
1. 노드 A의 뒤쪽 포인터 p->prev->next가 가리키는 노드가 C(p->next)가 되도록 업데이트
2. 노드 C의 앞쪽 포인터 p->next->prev가 가리키는 노드가 A(p->prev)가 되도록 업데이트, 이후 p가 가리키는 메모리 영역 해제
3. 선택한 노드가 삭제한 노드의 앞쪽 노드 A를 가리킬 수 있도록 crnt 업데이트
void Remove(Dlist *list, Dnode *p)
{
p->prev->next = p->next;
p->next->prev = p->prev;
list->crnt = p->prev; /* 삭제한 노드의 앞쪽노드에 주목 */
free(p);
if (list->crnt == list->head)
list->crnt = list->head->next;
}
머리 노드를 삭제하는 RemoveFront 함수
머리 노드를 삭제하는 함수
void RemoveFront(Dlist *list)
{
if (!IsEmpty(list))
Remove(list, list->head->next);
}
Remove 함수를 사용해 포인터 list->head->next
가 가리키는 머리 노드를 삭제
이때 더미 노드는 삭제하지 않으므로 list->head
가 가리키는 더미 노드가 아닌
list->head->next
를 삭제
꼬리 노드를 삭제하는 RemoveRear 함수
꼬리 노드를 삭제하는 함수
void RemoveRear(Dlist *list)
{
if (!IsEmpty(list))
Remove(list, list->head->prev);
}
list->head->prev
가 가리키는 꼬리 노드 삭제
선택한 노드를 삭제하는 RemoveCurrent 함수
선택한 노드를 삭제하는 함수
void RemoveCurrent(Dlist *list)
{
if (list->crnt != list->head)
Remove(list, list->crnt);
}
포인터 list->crnt
가 가리키는 노드 삭제
모든 노드를 삭제하는 Clear 함수
더미 노드를 제외하고 모든 노드를 삭제하는 함수
void Clear(Dlist *list)
{
while (!IsEmpty(list)) /* 텅 빌 때까지 */
RemoveFront(list); /* 머리노드를 삭제 */
}
리스트가 텅 빌 때까지 RemoveFront 함수를 사용해 머리 노드의 삭제 반복
삭제가 끝나면 선택한 노드에 대한 포인터 list->crnt
가 가리키는 노드는
더미노드 list->head
로 업데이트
원형 이중 연결 리스트를 종료하는 Terminate 함수
원형 이중 연결 리스트를 종료하는 함수
void Terminate(Dlist *list)
{
Clear(list); /* 모든 노드를 삭제 */
free(list->head); /* 더미 노드를 삭제 */
}
Clear 함수를 호출해 모든 노드를 삭제하고 더미 노드의 메모리 영역을 해제
Author And Source
이 문제에 관하여([Do it 알고리즘] 09. 리스트(2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dkswlgus00/Do-it-알고리즘-09.-리스트2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)