선형 리스트(연결 리스트, linked list)

• 선형 리스트: 데이터를 순서대로 나열한 자료 구조

리스트의 데이터는 노드(node) 또는 요소(element)라고 함

각각의 노드는 다음 노드를 가리키는 포인터를 가지고 있으며,

처음과 끝에 있는 노드는 각각 머리 노드(head node), 꼬리 노드(tail node)

한 노드의 바로 앞에 있는 노드는 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드는 다음 노드(successor node)

 

 

• 배열로 선형 리스트 만들기의 문제
  1. 쌓이는 데이터의 크기를 미리 알아야 함
  2. 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 함

---

• 포인터로 연결 리스트 만들기

노드를 구현한 구조체 Node

typedef struct __node {
    Member data;
    struct __node *next;
} Node;

1. data: 데이터를 저장 (저장할 데이터의 자료형을 따라감)

2. next: 자기 자신과 같은 구조체를 가리키는 포인터 = 뒤쪽 포인터

 

연결 리스트를 관리하는 구조체 List

typedef struct {
    Node *head;
    Node *crnt;
} List;

1. head: 머리 노드에 대한 포인터 

2. crnt: 선택한 노드에 대한 포인터

 

• 연결리스트 노드 개수 판단 방법

0개: list->head == NULL

1개: list->head->next == NULL

2개: list->head->next->next == NULL

 

• 머리 노드 판단 방법

Node* p에 대하여 p가 머리 노드인지 판단하는 방법

p == list -> head

 

• 꼬리 노드 판단 방법

p->next == NULL

---

• AllocNode 함수: 노드 생성

static Node *AllocNode(void){
    return calloc(1, sizeof(Node));
}

 

• SetNode 함수: 노드 데이터 값 설정

static void SetNode(Node* n, const Member* x, const Node* next){
    n->data = *x;
    n->next = next;
}

 

• Initialize 함수: 연결 리스트 초기화

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

 

• Search 함수: 검색하여 찾은 노드에 대한 포인터 반환

Node* Search(List* list, const Member* x, int compare(const Member* x, const Member* y)){
    Node* ptr = list->head;
    while(ptr != NULL){
        if(compare(&ptr->data, x) == 0) {
            list->crnt = ptr; //찾은 노드를 가리키도록 함
            return ptr;
        }
        ptr = ptr->next;
    }
    return NULL;
}

 

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

void InsertFront(List *list, const Member* x){
    Node* ptr = list -> head;
    list->head = list->crnt = AllocNode();
    SetNode(list->head, x, ptr); //새로 생긴 노드가 기존의 head를 가리키도록 설정
}

 

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

void InsertRear(List* list, const Member* x){
    if(list->head == NULL) InsertFront(list, x);
    else{
        Node* ptr = list->head;
        while(ptr->next != NULL) ptr = ptr->next; //꼬리노드까지 이동
        ptr->next = ptr->crnt = AllocNode();
        SetNode(ptr->next, x, NULL);
    }
}

 

• RemoveFront 함수: 머리 노드를 삭제

void RemoveFront(List* list){
    if(list->head != NULL){
    	Node* ptr = list->head->next;
        free(list->head);
        list->head = list->crnt = ptr;
    }
}

 

• RemoveRear 함수: 꼬리 노드를 삭제

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; //ptr은 꼬리노드, pre는 꼬리노드 바로 전 노드
            }
            pre->next = NULL;
            free(ptr);
            list->crnt = pre;
        }
    }
}

 

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

void RemoveCurrent (List *list){
    if(list->head != NULL){
    	if(list->crnt == list->head) RemoveFront(list);
        else[
        	Node* ptr = list->head;
            while(ptr->next != list->crnt) ptr = ptr->next; //ptr은 cnrt의 바로 전 노드
            ptr->next = list->crnt->next;
            free(list->crnt);
            list->crnt = ptr; //crnt는 삭제한 노드 전 노드를 가리키게 됨
        }
    }
}

 

• Clear 함수: 모든 노드를 삭제

void Clear(List* list){
     while(list->head != NULL) RemoveFront(list);
     list->crnt = NULL;
}

 

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

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

 

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

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

 

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

void Terminate(List* list){
    Clear(list);
}