[C언어와 함께 자료구조를] 연결리스트 (Linked List) - 개념과 구현

지난 시간에는 스택과 큐의 개념과 배열로 각각 구현을 해봤습니다. 이번에 살펴 볼 연결리스트(Linked List)는 정적인 배열과 달리 동적인 자료구조로 필요한 경우 할당하여 사용하고 필요가 없어지면 해제하는 식으로 메모리 관리가 가능하기 때문에 메모리를 절약할 수 있다는 장점이 있습니다.

단순연렬리스트 기본구조

 

연결리스트(링크드리스트 : Linked List)의 개념

연결리스트는 노드(Node)와 링크(Link)로 구성되며, 노드는 실제 정보를 담고 있는 하나의 단위이고, 링크는 노드간의 위치정보를 저장하고 있어 연결리스트의 순서를 유지할 수 있도록 하는 연결고리로 이해 하시면 됩니다.

연결리스트는 각 노드별 링크의 개수와 연결 상태에 따라 다양한 형태로 구성 될 수 있는데요. 단순 연결리스트, 환형 연결리스트, 이중 연결리스트, 이중 환형 연결리스트 등으로 나눌 수 있습니다.

단순 연결리스트 (Simple Linked List)

단순 연결리스트는 위 그림과 같이 선형적으로 한방향인 리스트의 형태로서 가장 많이 쓰이는 형태입니다. 여기서 리스트의 시작과 끝을 가리키는 노드가 필요한데요, 각각 머리(Head)와 꼬리(Tail)이라는 이름의 노드로 항상 존재하게 됩니다.

앞서 본 선형 구조의 자료구조인 스택과 큐에서처럼 연결리스트에도 노드의 추가, 삭제, 탐색 등의 연산이 있습니다. 여기서는 각각을 insert, delete, find라고 부르겠습니다.

0. 노드 정의

연결리스트의 노드는 단순히 정수형 데이터 하나만 가진다고 가정하고, 다음과 같이 정의 할 수 있습니다.

typedef struct _node{
    int key;
    struct _node *next;
}node; 

초보자들은 구조체 정의에 _node의 포인터에 당황하실지도 모르겠습니다만, 구조체에서 이런 재귀 정의는 가능하며, 이 의미는 _node라는 구조체 타입을 가리키는 포인터 즉, 다음 노드를 가리킨다는 사실을 아셔야 합니다.

1. 연결리스트 초기화

연결리스트의 초기상태는 머리(이하 Head)와 꼬리(이하 Tail)가 연결된 형태로 다음과 같은 모양을 가지고 있습니다.

위와 같이 연결리스트가 비어 있을 경우는 Head가 Tail을 Tail은 그 자신을 가리키는 형태가 되어 있어야 합니다.

node *head, *tail; 

void init_list (void) 
{    
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    head->next = tail;
    tail->next = tail;
} 

2. 연결리스트의 노드추가 - 삽입 : insert_next

연결리스트의 삽입(이하 insert)은 다음과 같은 순서로 진행됩니다.

(가) 초기모양

(나) L node를 생성

 

(다) L node가 t의 다음 node를 가리킴 (s->next = t->next)

(라) t의 다음 node를 L node로 변경 (t->next = s)

위와 같은 과정을 구현하면 다음과 같습니다.

node *insert_next (int key, node *t) 
{
    node *s;
    s = (node *)malloc(sizeof(node));
    
    s->key = key;
    s->next = t->next;
    t->next = s;
    
    return s;
} 

3. 연결리스트의 노드삭제 - delete_next

연결리스트의 삭제(이하 delete)는 다음과 같은 순서로 진행됩니다.

(가) 초기상태 (삭제전 node를 t가 가리킴)

 

(나) 삭제 대상 node 포인터 (s=t->next)

(다) 삭제전 node의 다음 포인터 (t->next = t->next->next)

(라) 삭제 대상 노드 메모리 해제 (free(s))

코드로 구현하면,,,

int delete_next (node *t) 
{
    node *s;
    if (t->next == tail)
        return 0;    
    s = t->next;                    // (나)    
    t->next = t->next->next;        // (다)    

    free(s);                        // (라)    

return 1;} 

4. 연결리스트 Node 검색 : find

위와 같이 특정한 key의 다음 Node에 연산을 위해서는 Node를 찾는 연산이 필요한데요. 이는 Head에서 Tail까지 주어진 key가 맞는지 확인 후 return해 주면 됩니다. 바로 코드를 볼께요.

node *find_node (int key)
{
    node *s;
    s = head->next;                     // head->next가 연결리스트의 첫 node    
    
    while (s->key != key && s != tail)  // 찾는 key가 맞거나 tail이면 끝
    	s = s->next;                    // 다음 node로    

    return s;
} 

find_node함수의 return값을 보고 tail이면 검색에 실패, 아니면 성공입니다. 쉽죠?

연결리스트의 개념을 이해할 때, Node를 그려가면서 연산(insert, delete)을 직접 손으로 해보는게 좋습니다. 주의할 점은 링크의 연결과 제거 그리고 Node의 메모리 해제의 순서가 달라지면 링크가 끊어져 버리는 오류가 발생할 수 있습니다.

예를 들어 다음과 같은 경우를 보죠.

(가) insert하려는 node를 다음 node에 먼저 연결하지 않는 경우

(나) 삭제하려는 Node s의 메모리를 먼저 해제한 경우

이와 같은 실수를 하지 않도록 주의 하시길 바라면서 연결리스트(단순연결리스트)에 대한 설명을 마치겠습니다.

다음시간에는 환형연결리스트와 이중연결리스트에 대해서 알아보겠습니다.