[자료구조]단순 연결 리스트(Simple Linked List)

연결 리스트는 노드(node)와 링크(link)로 구성이 된다.

노드 : 실제의 정보를 담고 있는 하나의 단위

링크 : 인접 노드의 위치를 저장하고 있어 연결 리스트의 순서를 유지할 수 있게 하는 연결고리

연결 리스트는 정적인 자료 구조인 배열과는 달리 동적인 자료 구조이다. 연결 리스트는 필요하면 할당하고, 필요없으면 해제하는 식의 메모리 관리가 가능하기 때문에 배열처럼 여분의 공간을 마련할 필요가 없어 메모리를 절약할 수 있는 이점이 있다. 연결 리스트는 동적으로 메모리를 사용하기 때문에 프로그램의 실행중에도 얼마든지 규모를 크게 하든지, 작게 할 수 있다. 

또 연결 리스트가 배열과 다른점은 배열은 메모리의 연속된 공간을 차지하는데 비해서 연결 리스트는 동적으로 수시로 할당 해제되기 때문에 메모리의 연속된 공간을 차지하지 못한다. 그래서 연결 리스트의 각 요소들은 흩어져 있고 순서도 제대로 되어 있지 않다. 이러한 연결 리스트의 순서를 유지시켜 주는 것은 링크(link)에 의해서 가능해진다. 

연결 리스트는 각 노드별로 링크의 배수와 링크의 연결 상태에 따라 단순, 환형, 이중 이중 환형 등으로 분류 된다. 그중 단순 연결 리스트에대해서 소스를 공유한다. 

간단하게 단순 연결 리스트에 대해서 말하자면 이름에서도 알 수 있듯이 가장 단순한 형태이면서 가장 많이 쓰이기도 하는 형태이다. 단순연결 리스트는 정보를 저장하는 노드와 바로 다음의 노드를 가리키는 링크 하나로 구성되어 있다. 

연결 리스트의 최대의 장접은 재배열이 손쉽다는 것이다. 자료의 순서를 마구 바꾸어야 할 경우 배열의 경우에는 당기고 미는 등의 메모리 복사가 필요하지만, 연결 리스트의 경우에는 링크가 가리키는 방향만 바꾸어주면 된다. 

단순 연결 리스트는 각각이 다음의 노드를 정확히 가르키고 있지만 제일 처음의 노드는 누가 가르켜줄 것인가라는 문제 때문에 사용자에게 알려진 연결 리스트의 입구인 머리(head)가 필요하게 된다. 이 머리는 일반적으로 전역 변수로 선언이 되어 모듈 내의 어떤 부분에서도 접근 가능하도록 개방되어 있고, 소멸되지 않는다. 

그리고 연결 리스트의 제일 마지막 노드는 항상 무엇인가를 가리켜야 하는데 특별히 마지막을 나타내는 꼬리(tail) 노드를 만들어서 마지막 노드임을 표시하게 한다. 

이 방법이 머리와 꼬리 노드를 모두 정의하여서 낭비가 있을 것 같지만 일관성을 유지할 수 있고, 코딩이 쉽다는 점에서 몇 바이트 정도의 낭비는 무시할 수 있다. 

 
#include <stdio.h>
 
 
typedef struct _node{
    int key;
    struct _node *next;
} node;
 
node *head;
node *tail;
 
void init_list(void){
    head = (node*)malloc(sizeof(node));
    tail = (node*)malloc(sizeof(node));
    head->next = tail;
    tail->next = tail;
}
 
int delete_next(node* target){
    node* next_node;
    if (target->next == tail){
        return 0; // 오류
    }
 
    next_node = target->next;
    target->next = (target->next)->next;
 
    free(next_node);
 
    return 1; // 성공
}
 
node* insert_after(int k, node* target){
    node* new_node;
    new_node = (node*)malloc(sizeof(node));
 
    new_node->key = k;
    new_node->next = target->next;
    target->next = new_node;
 
    return new_node;
}
 
node* find_node(int key){
    node* next_node;
    next_node = head->next;
 
    while (next_node != tail && next_node->key != key){
        next_node = next_node->next;
    }
 
    return next_node;
}
 
int delete_node(int k){
    node* s;
    node* p;
 
    p = head;
    s = p->next;
 
    while (s->key != k && s != tail){
        p = p->next;
        s = p->next;
    }
 
    if (s != tail){
        p->next = s->next;
        free(s);
        return 1;
    }
    else
        return 0;
}
 
node* insert_node(int t, int k){
    node* s;
    node* p;
    node* r;
    p = head;
    s = p->next;
 
    while (s->key != k && s != tail){
        p = p->next;
        s = p->next;
    }
 
    if (s != tail){
        r = (node*)malloc(sizeof(node));
        r->key = t;
        p->next = r;
        r->next = s;
    }
 
    return p->next;
}
 
node* ordered_insert(int k){
    node* s;
    node* p;
    node* r = NULL;
    p = head;
    s = p->next;
 
    while (s->key != k && s != tail){
        p = p->next;
        s = p->next;
    }
 
    
    r = (node*)malloc(sizeof(node));
    r->key = k;
    p->next = r;
    r->next = s;
 
    return r;
}
 
void print_list(node* t){
    printf("\n");
    while (t != tail){
        printf("%-8d", t->key);
        t = t->next;
    }
}
 
node* delete_all(void){
    node* s;
    node *t;
    t = head->next;
 
    while (t != tail)
    {
        s = t;
        t = t->next;
        free(s);
    }
    head->next = tail;
    return head;
}
 
 
void main(void){
    node* t = NULL;
 
    init_list();
    ordered_insert(10);
    ordered_insert(5);
    ordered_insert(8);
    ordered_insert(3);
    ordered_insert(1);
    ordered_insert(7);
    ordered_insert(8);
 
    printf("\nInitial Linked list is ");
    print_list(head->next);
}

순서대로 출력 되는 것을 볼 수 있을 것이다. 

혹시 몰라 나머지 기능들은 넣어 두었다. 과제 같은거 할때 쓰면 좋을 듯 한다.