[자료구조] 단순 연결 리스트

단순 연결리스트의 기본 구조는

typedef struct _node{


int key;


struct _node *next;


}Node;

위와 같은 형식을 가진다.

단순연결이기때문에 검색을 할려면 앞에서부터 순차적으로 들어간다.

뒤로 가는건 안됀다 오로지 앞으로만 갈 수 있다. 뒤로갈려면 이중연결리스트를 써야한다.

연결리스트의 단점은 배열보다 용량을 더 잡아먹고, 주소를 잘못 지정하면 전에 있던거나

앞에 있던게 메모리 상에서 떠돌아다니게 된다. 뭔말인고 하니 메모리 누수가 생긴다는거다. 물론 C일 경우에만

Java나 C# 같은 GC(garbage collector)가  있는 랭귀지는 관계 없다.

Head -> A - >  B - > C - > D -> NULL

C를 찾기 위해서는 Head 에서부터 C까지 들어가는거다.


단순 연결리스트의 삽입과 삭제

void Add(int key)
{
    Node*  new_Node;
   while(1)
   {
        if( head->next == NULL)
        {
            new_Node = (Node*) malloc(sizeof(Node));
            new_Node-> key = key;
            new_Node-> next = NULL;
            head-> next = new_Node;
            return;
        }else{
            head = head -> next;
        }
    }
}

void Delete(int key)
{
    Node *p = head->next;   
    Node *prev;                //p의 이전 노드

    while( p !=NULL)
    {
        if ( p->key == key)
        {
            prev->next = p->next;
            free(p);
            p = 0;
        }
        else
        {
            prev = p;
            p = p->next;
        }
    }
}

단순 연결리스트는 이걸로 끝~

프로그래밍을 할때는 손에 공책을 가지고 있어라.. 왜냐 그리면서 하면 더 이해하기 쉽기때문이다.

특히 연결리스트 같은 경우에는 말이지.