원형 이중 연결 리스트

• 원형 리스트(Circular list)

선형 리스트의 꼬리 노드가 머리 노드를 가리키는 자료구조

 

• 원형 리스트 상태를 판단하는 방법

빈 원형 리스트 판단:

list->head == NULL

 

노드가 1개인지 판단:

list->head->next == list->head

 

Node* p가 머리 노드인지 판단:

p == list->head

 

Node* p가 꼬리 노드인지 판단:

p->next == list->head

---

• 이중 연결 리스트(Doubly linked list)

선형 리스트에서 각 노드가 다음 노드와 앞쪽 노드에 대한 포인터를 가지고 있는 자료 구조

 

typedef struct __node{
    Member data;
    struct __node* prev;
    struct __node* next;
} Dnode;

 

• Dnode* p가 머리 노드인지 판단

p == list->head
p->prev == NULL

 

• Dnode* p가 꼬리 노드인지 판단

p->next == NULL

---

• 원형 이중 연결 리스트(Circular doubly linked list)

두 가지의 개념을 합한 자료구조

 

typedef struct __node{
    Member data;
    struct __node* prev;
    struct __node* next;
} Dnode;

typedef struct{
    Dnode* head;
    Dnode* crnt;
} Dlist;

 

더미 노드: head

머리 노드: head->next

꼬리 노드: head->prev

 

---

• AllocDNode 함수: 1개 노드를 동적 생성

static Dnode *AllocDNode(void){
    return calloc(1, siaeof(Dnode));
}

 

• SetDNode 함수: 노드 값 설정

static void SetDNode(Dnode* n, const Member* x, const Dnode* prev, const Dnode* next){
    n->data = *x;
    n->prev = prev;
    n->next = next;
}

 

• IsEmpty 함수: 리스트가 비었는지 검사

static int IsEmpty(const Dlist* list){
    return list->head->next == list->head;
}

 

• Initialize 함수: 리스트 초기화

void Initialize (Dlist* list){
    Dnode* dummyNode = AllocDNode();
    list->head = list->crnt = dummyNode;
    dummyNode->prev = dummyNode->next = dummyNode; //포인터가 설정된 더미노드만 있는 상태
}

 

• PrintCurrent 함수: 선택한 노드의 데이터를 출력

void PrintCurrent (const Dlist* list){
    if(IsEmpty(list)) printf("선택한 노드가 없습니다.");
   	else PrintMember(&list->crnt->data);
}

 

• Search 함수: x와 일치하는 노드를 검색

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;
}

 

• Print 함수: 모든 노드의 데이터를 리스트 순으로 출력

void Print(const Dlist* list){
    if(IsEmpty(list)) puts("노드가 없습니다.");
    else{
    	Dnode* ptr = list->head->next;
        puts("[모두 보기]");
        while(ptr != list->head){
        	PrintMember(&ptr->data);
            putchar('\0');
            ptr = ptr->next;
        }
    }
}

 

• PrintReverse 함수: 모든 노드의 데이터를 리스트 역순으로 출력

void PrintReverse(const Dlist* list){
    if(IsEmpty(list)) puts("노드가 없습니다.");
    else{
    	Dnode* ptr = list->head->prev;
        puts("[모두 보기]");
        while(ptr != list->head){
        	PrintMember(&ptr->data);
            putchar('\0');
            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;
}

 

• 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 = Allocate();
    Dnode *nxt = p->next;
    p->next = p->next->prev = ptr;
    SetDNode(ptr, x, p, nxt);
    list->crnt = ptr; //삽입한 노드를 가리킴
}

 

• InsertFront 함수: 머리에 노드 삽입

void InsertFront(Dlist* list, const Member* x){
    InsertAfter(list, list->head, x);
}

 

• InsertRear 함수: 꼬리에 노드를 삽입

void InsertRear(Dlist* list, const Member* x){
    InsertAfter(list, list->head->prev, x);
}

 

• Remove 함수: p가 가리키는 노드 삭제

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);
}

 

• RemoveRear 함수: 꼬리 노드 삭제

void RemoveRear (Dlist* list){
    if(!IsEmpty(list)) Remove(list, list->head->prev);
}

 

• RemoveCurrent 함수: 선택한 노드를 삭제

void RemoveCurrent(Dlist* list){
    if(list->crnt != list->head)
    	Remove(list, list->crnt);
}

 

• Clear 함수: 모든 노드 삭제

void Clear(Dlist* list){
    while(!IsEmpty(list)) RemoveFront(list);
}

 

• Terminate 함수: 원형 연결 리스트 종료

void Terminate(Dlist* list){
    Clear(list);
    free(list->head); //더미 노드를 따로 삭제해줘야 함
}