[Data Structure] #1-6 연결 리스트 ADT (Linked List ADT)

연결 리스트 ADT

#5 에서는 일반적인 연결리스트를 이용하여 다항식을 표현해보았다. 이번에는 Linked List ADT를 작성해보자.

먼저 코드부터 보자. 

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

#define FALSE 0
#define TRUE 1

typedef int element;
typedef struct {
    element data;
    struct ListNode* link;
}ListNode;

typedef struct {
    ListNode* head;
    int length;
}LinkedListType;

void init(LinkedListType *list){
    if (list == NULL)
        return;

    list->length = 0;
    list->head = NULL;
}

void error(char *message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

int is_empty(LinkedListType *list){
    return list->length == 0;
}

int get_length(LinkedListType *list){
    return list->length;
}

void insert_node(ListNode** phead, ListNode* p, ListNode* new_node){
    if (*phead == NULL) {
        *phead = new_node;
        (*phead)->link = NULL;
    } else if (p == NULL){
        new_node->link = *phead;
        *phead = new_node;
    } else {
        new_node->link = p->link;
        p->link = new_node;
    }
}

void remove_node(ListNode** phead, ListNode* p, ListNode* removed){
    if (*phead == NULL) return;
    if (p == NULL){
        *phead = (ListNode*)(*phead)->link;
    }else{
        p->link = removed->link;
    }
    free(removed); //null이어도 에러가 안난다
}

ListNode* get_node_at(LinkedListType *list, int pos){
    if (list->head == NULL) return NULL;
    else if (pos < 0 || pos > list->length) return NULL;
    
    ListNode *p = list->head;
    int i;
    for (i=0; i<pos; i++)
        p = (ListNode*) p->link;
    return p;
}

void add(LinkedListType *list, int pos, element data){
    if (pos < 0 || pos > list->length) return;
    
    ListNode *new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->data = data;
    new_node->link = NULL;
    
    ListNode *p;
    p = get_node_at(list, pos-1);
    insert_node(&(list->head), p, new_node);
    list->length++;
}

void add_last(LinkedListType* list, element data){
    add(list, get_length(list), data);
}

void add_first(LinkedListType* list, element data){
    add(list, 0, data);
}

void delete(LinkedListType *list, int pos){
    if (is_empty(list) || pos > list->length) return;
    if (list->head == NULL) return;
    
    ListNode *p = get_node_at(list, pos-1);
    remove_node(&(list->head), p, p != NULL ? (ListNode*)p->link : NULL);
    list->length--;
}

element get_entry(LinkedListType *list, int pos){
    if (list->head == NULL)
        return NULL;
    if (is_empty(list) || pos > list->length)
        return NULL;

    ListNode *p = get_node_at(list, pos);
    return p->data;
}

void clear(LinkedListType *list){
    int i;
    for (i=0; i<get_length(list); i++)
        delete(list, i);
}

void display(LinkedListType *list){
    int i;
    ListNode *p = list->head;
    printf("(");
    for (i=0; i<get_length(list); i++) {
        printf("%d ",p->data);
        p = (ListNode*) p->link;
    }
    printf(")\n");
}

int is_in_list(LinkedListType *list, element item){
    ListNode *p = list->head;
    while (p) {
        if (p->data == item)
            return TRUE;
        p = (ListNode*)p->link;
    }
    return FALSE;
}

int main() {
    LinkedListType list;
    init(&list);
    add(&list, 0, 20);
    add_last(&list, 30);
    add_first(&list, 10);
    add_last(&list, 40);
    
    display(&list);
    
    delete(&list, 3);
    display(&list);
    
    delete(&list, 0);
    display(&list);
    
    printf("%s\n",is_in_list(&list, 20) == TRUE ? "성공" : "실패");
    printf("%d\n",get_entry(&list, 0));
    return 0;
}

구조를 잘 살펴보면 insert_node() 와 remove_node()는 인자로 LinkedList **phead를 받는다. 더블포인터다. 저번에도 말했다시피 더블포인터는 매개변수 그 자체의 값을 바꿔주기 위해서 존재한다. 모르시면 이전의 블로그를 참조합시다.

 그 외에는 어려운게 없으므로 여기까지.