[C] 자료구조::연결 리스트 (LINKED LIST) _ 1

C하면 자료구조.

 

자료구조하면 리스트가 아니겠는가

 

사실상 큐나 스택 트리 그래프 모두 리스트가 베이스라고 생각된다.

 

고로 리스트를 구현해보자

---

우선 구조체를 만들어보자

typedef struct NODE{
    char* data;
    struct NODE* link;
}node;

typedef struct LIST{
    int count;
    struct NODE* body;
}list;

이름들은 아주 직관적으로 짓겠다.

 

NODE (body)	data	실제 데이터가 저장되는 변수
	link	다음 리스트를 가르키는 포인터
LIST (head)	count	리스트의 전체 크기
	body	실제 리스트를 가르키는 포인터

구조체를 두개로 구현하여 멋을 가미시켜주자

 

 

 

리스트에 저장될 데이터는 숫자일수도 있고 문자일수도 있고 모르는 일이나

일단은 문자열을 주로 하겠다.

( 추후에 아주 요긴하게 사용할 것이다. )

 

void LIST_Init(list* head) {
    head->count = 0;
    head->head = NULL;
}

* 초기화 함수

 

---

#define true 1
#define false 0

int LIST_Add(list* head, char* data) {
    return false;
}

리스트에 데이터 추가함수다

성공/실패 여부를 반환해 주도록 하자

 

파라미터로 2차원 포인터를 넘겨주어 메모리가 지역에서 할당되지 않도록 해주자

 

    node* temp = head->body;

    while (1) {
        // 헤더가 비었을 때
        if (temp == NULL) {
            temp = (node*)malloc(sizeof(node));
            temp->link = NULL;
            head->body = temp;
            break;
        }
        // 헤더(현재 노드)가 마지막 일때
        else if (temp->link == NULL) {
            temp->link = (node*)malloc(sizeof(node));
            temp->link->link = NULL;
            break;
        }
        // 다음 노드가 존재할 때
        else {
            temp = temp->link;
        }
    }
    head->count++;
    return true;

리스트를 구현할 때 다음과 같이

헤더가 비었을 때,  마지막 노드일 때, 중간 노드일 때 

세가지 경우에 맞춰서 구현하면 되겠다

 

data만 적절하게 연결시켜주면 된다.

 

int LIST_Add(list* head, char* data) {
    node* temp = head->body;

    while (1) {
        // 헤더가 비었을 때
        if (temp == NULL) {
            temp = (node*)malloc(sizeof(node));
            temp->data = data;
            temp->link = NULL;
            head->body = temp;
            break;
        }

        // 헤더(현재 노드)가 마지막 일때
        else if (temp->link == NULL) {
            temp->link = (node*)malloc(sizeof(node));
            temp->link->data = data;
            temp->link->link = NULL;
            break;
        }

        // 다음 노드가 존재할 때
        else {
            temp = temp->link;
        }
    }
    head->count++;
    return true;
}

막상 구현해보니 반환이 false 경우가 존재하나 싶다.

 

 

void main() {
    list datalist;
    LIST_Init(&datalist);

    LIST_Add(&datalist, "one");
    LIST_Add(&datalist, "two");
    LIST_Add(&datalist, "three");
    LIST_Add(&datalist, "four");

}

함수는 다음과 같이 쓰면 되겠다.

 

동적할당을 한 메모리를 반환하는 것과 

리스트를 출력하는 함수는 다음에 만들도록 하자