리스트(List) (C)

리스트는 데이터를 줄지어 늘어놓은 자료구조이다.

선형 리스트

리스트 중에 가장 간단하다. 리스트의 데이터는 노드(또는 요소)라고 한다.
맨 앞 노드 : head node
맨 뒤 노드 : tail node
하나의 노드에 대해 바로 앞에있는 노드 : predecessor node
바로 뒤에있는 노드 : successor node
선형리스트는 1. 쌓이는 데이터의 크기를 미리 알아야 하고 2. 데이터의 삽입, 삭제에 따라 데이터를 모두 다 옮겨야하기 때문에 효율이 좋지 않다.

연결 리스트

연결리스트는 커서 또는 포인터로 만들 수 있다.

포인터

노드의 구조체와 리스트의 구조체는 다음과 같다.

typedef struct __node {
	Member data; //뒤에서 언급
    struct __node* next;
} Node;

//만약 Node* next; 로써 선언하면 오류가 뜬다. (Node는 아래에서 선언되므로)

typedef struct {
	Node* head;
    Node* crnt; //제일 최근에 접근한 포인터를 가리킴
} List;

함수는 다음과 같다.

#include <stdio.h>
#include <stdliv.h>
#include "Member.h"
#include "LinkedList.h"

//노드를 동적으로 생성
static Node* AllocNode() {
	return calloc(1, sizeof(Node));
}

//n이 가리키는 노드의 각 멤버에 값을 설정
static void SetNode(Node* n, const Member* x, const Node* next) {
	n->data = *x;
    n->next = next;
}

//초기화
void Initialize (List* list) {
	list->head = NULL;
    list->crnt = NULL;
}

//검색
Node* search(List* list, const Member* x, int compare(const Member* x, cosnt Member* y)) {
	Node* ptr = lsit->head;
    while(ptr != NULL) {
    	if(compare(&ptr->data) == 0) {
        	list->crnt = ptr;
            return ptr;
        }
        ptr = ptr->next;
    }
    return NULL;
}
// * 여기서 &ptr->data 에서 -> 연산자의 우선순위가 높으므로 &(ptr->data)와 같은 의미이다.

//머리에 노드 삽입
void InsertFront (List* list, const Member* x) {
	Node* ptr = list->head;
    list->head = list->crnt = AllocNode();
    SetNode(list->head, x, ptr);
}

//꼬리에 노드를 삽입
void InsertRear (List* list, const Member* x) {
	if(list->head == NULL)
    	InserFront(list, x);
    else {
    	Node* ptr = list->head;
        while(ptr->next != NULL)
        	ptr = ptr->next;
        ptr->next = list->crnt = AllocNode();
        SetNode(ptr->next, x, NULL);
    }
}

//머리 노드를 삭제
void RemoveFront (List* list) {
	if(list->head != NULL) {
    	Node* ptr = list->head->next;
        free(list->head);
        list->head = list->crnt = ptr;
    }
}

//꼬리 노드를 삭제
void RemoveRear (List* list) {
	if(list->head != NULL) {
    	if((list->head)->next == NULL)
        	RemoveFront(list);
        else {
        	Node* ptr = list->head;
            Node* pre;
            while(ptr->next != NULL) {
            	pre = ptr;
                ptr = ptr->next;
            }
            pre->next = NULL;
            free(ptr);
            list->crnt = pre;
        }
    }
}

//선택한 노드를 삭제
void RemoveCurrent (List* list) {
	if(list->head != NULL) {
    	if(list->crnt == list ->head)
        	RemoveFront(list);
        else {
        	Node* ptr = lsit->head;
            while(ptr->next != list->crnt)
            	ptr = ptr->next;
            ptr->next = list->crnt->next;
            free(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("-1");
    else
    	PrintMember(&list->crent->data);
}

//모든 노드의 데이터를 리스트 순으로 출력
void Print (const List* list) {
	if(list->head == NULL)
    	puts("-1");
    else {
    	Node* ptr = list->head;
        while(ptr != NULL) {
        	PrintMember(&ptr->data);
            ptr = ptr->next;
        }
    }
}

//종료
void Terminate(List* list) {
Clear(list);
}

커서

커서방식이 포인터와 다른 점은 next가 다음 노드의 위치 대신 인덱스를 가리키는 것이다. 즉, 연결리스트를 배열에 저장한 것이라고 생각하면 된다. (꼬리 노드의 커서는 -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;

커서 방식에서는 배열에 저장하기때문에 만약 중간에 있는 노드를 삭제시에 빈칸이 생긴다. 그럼 이 빈칸의 자리를 기록해야 배열을 효율적으로 사용할 수 있다. 따라서 삭제된 빈칸의 자리들의 배열인 프리 리스트를 사용한다.

함수는 다음과 같다.

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

//초기화
void Initialize(List* list, int size) {
	list->n = calloc(size, sizeof(Node));
    list->head = NULL;
    list->crnt = NULL;
    list->max = NULL;
    list->deleted = NULL;
}

//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[pte].next != list->crnt)
            	ptr = lsit->n[ptr].next;
            list->n[ptr].next = 
        }
    }
}

//모든 노드를 삭제
void Clear(List* list) {
	while(list->head != NULL)
    	RemoveFront(list);
    list->crnt = NULL;
}

//선택한 노드의 데이터를 출력
void PrintCurrent(const List* list) {
	if(list->crnt = NULL)
    	printf("-1");
    else
    	PrintMember(&list->n[list.crnt].data);
}
// *data에 & 를 넣어준 이유는 member 구조체에서 봐야할 것 같다. data자체가 포인터형식이라서 겟지?

//모든 노드의 데이터를 출력
void Print(const List* list) {
	if(list->head == NULL)
    	puts("-1");
    else {
    	Index ptr = list->head;
        while(ptr != NULL) {
        	PrintMember(&list->n[ptr].data);
            ptr = list->n[ptr].next;
        }
    }
}

//종료
void Terminate(List* list) {
	Clear(list);
    free(list->n);
}

원형 이중 연결 리스트

원형 리스트

원형리스트는 원형 큐와 비슷하게 꼬리가 머리를 가리키는 형태이다.
빈 원형 리스트를 판단하는 방법은

list->head == NULL

이다.
노드가 1개인 원형 리스트를 판단하는 방법은

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

이다.
다음과 같은 맥락으로 p가 list->head와 같으면 머리 노드이고, p->next가 list->head와 같으면 꼬리 노드이다.

이중 연결 리스트

선형 리스트의 단점은 단방향이라는 것이다. 이중 연결리스트는 이를 보완한 것이다. 따라서 각 노드에 다음 노드에 대한 포인터와 앞쪽의 노드에 대한 포인터 모두 포함되어 있다.

구조체는 다음과 같다.

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

p가 list->head 이거나 p->prev가 NULL이면 머리노드이다.
p->next가 NULL이면 꼬리 노드이다.

원형 이중 연결 리스트

이는 위의 둘의 특징을 모두 합친 것이다.
구조체는 다음과 같다.

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

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

선언은 생략하겠다.

함수는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include "CircDblLinkedList.h"

//생성
static Dnode* AllocDNode(){
	return calloc(1, sizeof(Dnode));
}

//노드 멤버 설정
static void SetDNode (Dnode* n, const Member* x, const Dnode* prev, const Dnode* next) {
	n->data = *x;
    n->prev = prev;
    n->next = next;
}

//리스트가 비어있는지 검사
static int IsEmpty (const Dlist* list) {
	return list->head->next == list->head;
}

//초기화
void Initialize (Dlist* list) {
	Dnode* dummyNode = AllocDNode();
    list->head = list->crnt = dummyNode;
    dummyNode->prev = dummyNode->next = dummyNode;
}
// *더미 노드는 리스트의 맨 앞에 있는 노드이며 처음에는 prev, next포인터 모두 자기 자신을 가리킨다.

//선택한 노드의 데이터를 출력
void PrintCurrent (const Dlist* list) {
	if(IsEmpty(list))
    	printf("-1");
    else
    	PrintMember(&list->crnt->data);
}

//검색
Dnode* Search (Dlist* list, cosnt 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;
}

//모든 노드를 순서대로 출력
void Print (const Dlist* list) {
	if(IsEmpty(list))
    	puts("-1");
    else {
    	Dnode* ptr = list->head->next;
        while(ptr != list->head) {
        	PrintMember(&ptr->data);
            ptr = ptr->next;
        }
    }
}

//역순으로 출력
void Print (const Dlist* list) {
	if(IsEmpty(list))
    	puts("-1");
    else {
    	Dnode* ptr = list->head->prev;
        while(ptr != list->head) {
        	PrintMember(&ptr->data);
            ptr = ptr->prev;
        }
    }
}

//선택한 노드를 다음으로 진행
int Next(Dlist* list) {
	if(IsEmpty(list) || list->crnt->next == list->head)
    	return 0;
    list->crnt = list->crnt->next;
    return 1;
}

//선택한 노드를 앞쪽으로 진행
int Next(Dlist* list) {
	if(IsEmpty(list) || list->crnt->prev == list->head)
    	return 0;
    list->crnt = list->crnt->prev;
    return 1;
}

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

//머리에 삽입
void InsertFront(Dlist* list, const Member* x) {
	InsertAfter(list, list->head, x);
}

//꼬리에 삽입
void InsertRear(Dlist* list, const Member* x) {
	InsertAfter(list, list->head->prev, x);
}

// * 비어있어도 더미노드가 있기때문에 비어있는지의 여부의 필요성 없음

//삭제
void Remove (Dlist* list, Dnode* p) {
	p->prev->next = p->next;
    p->next->prev = p->prev;
    list->vrnt = p->prev;
    free(p);
    if(list->crnt == list->head)
    	list->crnt = list->head->next;
}

//머리 삭제
void RemoveFront (Dlist* list) {
	if(!IsEmpty(list))
    	Remove(list, list->head->next);
}

//꼬리 삭제
void RemoveRear (Dlist* list) {
	if(!IsEmpty(list))
    	Remove(list, list->head->prev);
}

//선택한 노드를 삭제
void RemoveCurrent (Dlist* list) {
	if(list->crnt != list->head)
    	Remove(list, list->crnt);
}

//모든 노드 삭제
void Clear (Dlist* list) {
	while(!IsEmpty(list))
    	RemoveFront(list);
}

//종료
void Terminate (Dlist* list) {
	Clear(list);
    free(list->head); // 더미 노드를 삭제
}