리스트

순서에 따라 일렬로 나열되어 저장된 데이터 형태를 리스트라고 부른다. 프로그래밍을 하다보면 배열Array라는 자료구조를 마주칠 수 있다. Array 또한 리스트의 일종이다. ADT(Abstract Data Type)를 어떻게 정하느냐에 따라 구현되어야 하는 연산이 달라진다. 기본적으로는 (리스트 자체의)생성, 추가, 삽입, 탐색, 삭제, (리스트 자체의)소멸이 리스트 자료구조의 ADT라고 본다.

링크드 리스트(Linked List)

링크드 리스트란 노드node끼리 연결을 해놓은 리스트라고 할 수 있다. 헤드Head에서 시작되는 개별 노드는 자신 기준 다음번 노드가 어디에 저장되어 있는지에 대한 정보를 가진다. 맨 마지막에 있는 테일Tail 노드는 그에 대한 정보가 비어(NULL)있다.

부모 노드에 저장된 정보만 변경하면 되기 때문에 노드의 순서를 바꾸는 것이 쉽다. 삽입인아 삭제 연산이 쉽다고 볼 수 있다. 하지만 헤드부터 시작하여 탐색을 하므로 탐색 속도에 한계가 있다. 테일 노드를 찾는 데에 걸리는 시간 때문에 노드를 추가하는 연산도 빠른 편이 아니다. 또한 중간의 한 노드가 소실되면 그 뒤의 데이터가 모두 사라져서 안정적인 자료구조라고 하기 어렵다.

이런 장단점으로 인해 배열을 쓰기 좋은 경우와 링크드 리스트를 쓰기 좋은 경우가 나뉜다. 탐색이나 정렬 등은 배열이 링크드 리스트에 비해 효율적이므로 탐색/정렬이 잦은 경우에는 배열을 쓴다. 추가/삽입/삭제 연산이 잦은 경우에는 링크드 리스트를 사용하는 게 좋다.

배열이나 링크드 리스트는 그 자체로 쓰이기도 하지만(이번에 살펴볼 단순 링크드 리스트는 FAT 파일 시스템에 쓰인다) 다른 자료구조의 기반이 되는 경우가 많다.

(LinkedList.c)

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

typedef int Element;

typedef struct _LLNode
{
   Element Data;
   struct _LLNode* NextLLNode;
} LLNode;

// functions

LLNode* CreateLLNode( Element data )
{
    LLNode* Head = (LLNode*)malloc( sizeof( LLNode ) );

    Head->Data = data;
    Head->NextLLNode = NULL;

    return Head;
}

void AppendLLNode( LLNode** Head, LLNode* New )
{
    if ( (*Head) == NULL )
        *Head = New;
    else
    {
        LLNode* Tail = (*Head);
        while ( Tail->NextLLNode != NULL )
            Tail = Tail->NextLLNode;

        Tail->NextLLNode = New;
    }
}

void InsertLLNode( LLNode* Target, LLNode* New )
{
    New->NextLLNode = Target->NextLLNode;
    Target->NextLLNode = New;
}
void InsertLLHead( LLNode** Head, LLNode* New )
{
    if ( (*Head) == NULL )
        *Head = New;
    else
    {
        New->NextLLNode = (*Head);
        *Head = New;
    }
}

void RemoveLLNode( LLNode** Head, LLNode* Target )
{
    if ( (*Head) == Target )
        *Head = Target->NextLLNode;
    else
    {
        LLNode* Candidate = (*Head);
        while ( Candidate != NULL && Candidate->NextLLNode != Target )
            Candidate = Candidate->NextLLNode;

        if( Candidate != NULL )
            Candidate->NextLLNode = Target->NextLLNode;
    }
}

LLNode* SearchLL( LLNode* Head, int idx )
{
    LLNode* Candidate = Head;
    while ( Candidate != NULL && (--idx) >= 0 )
        Candidate = Candidate->NextLLNode;

    return Candidate;
}
int LengthLL( LLNode* Head )
{
    int cnt = 0;

    LLNode* Current = Head;
    while ( Current != NULL )
    {
        Current = Current->NextLLNode;
        cnt++;
    }

    return cnt;
}

void DestroyLLNode( LLNode* Node )
{
    free( Node );
}

왜 AppendLLNode의 매개변수로 더블 포인터double pointer LLNode** Head가 쓰여야 하는지 알고 넘어가는 것이 중요하다. 뒤에서도 더블 포인터가 계속 등장하기 때문이다.

우리가 위의 코드를 활용해 함수를 만들 때 주로 아래와 같은 코드를 활용한다.

LLNode* List = NULL;

LLNode* NewNode = NULL;
NewNode = CreateLLNode( data );

AppendLLNode( &List, NewNode );

만일 여기서 AppendLLNode를 아래와 같이 정의하고 사용했다고 쳐보자.

// declarations
void AppendLLNode( LLNode* Head, LLNode* New );

// code
LLNode* List = NULL;

LLNode* NewNode = NULL;
NewNode = CreateLLNode( data );
AppendLLNode( List, NewNode );

List라는 변수와 NewNode라는 변수는 스택stack에 저장되어 각각의 값이 저장되어 있는 주소값을 저장하는 변수가 되게 된다. 그리고 이 두 변수가 함수에 매개변수로 전달되면, 각각의 변수가 함수 안에서 변화를 겪는 것이 아니다. 두 변수가 가지고 있던 값을 전달할 뿐이다. 따라서 매개변수 Head는 List가 가리키던 주소값을 가진 채 스택에 새로 정의되고, 변수 New 역시 NewNode가 가리키는 곳의 주소값을 가진채 스택에 새로 저장된다.

이 상황에서 함수 내에서 벌어지는 일은 Head라는 변수가 가진 주소값을 New가 가진 주소값으로 바꾸어주는 일이다. 어차피 New, 그리고 New에게 주소값을 전달해주었던 NewNode에 담긴 값이 바뀔 필요는 없다. 하지만 궁극적으로 우리가 원하는 것은 함수의 호출이 종료되면 사라지는 Head라는 변수가 가리키는 주소값을 변경하는 것이 아니라, 함수가 끝나고도 살아있는 변수 List가 가진 주소값을 NewNode가 가진 주소값으로 바꿔주고 싶은 것이다.

따라서 우리는 Head가 List를 조종할 수 있게 해주어야 한다. 그러기 위해서는 Head에게 List의 주소값을 줘야한다. 그 주소값을 통해 List가 가지고 있는 주소값에 접근해 그 값을 New라는 매개변수에 전달된 주소값으로 변화시켜줄 수 있기 때문이다. 그러므로 우리는 AppendLLNode 함수에서 더블 포인터를 사용해야 한다.

이러한 차이는 InsertLLNode와 InsertLLHead의 차이를 보면 더 명확하다. InsertLLNode는 링크드 리스트의 첫 노드를 가리키는 변수 List의 주소값을 바꿀 일이 없다. 서로 연결되어 있는 링크드 리스트 노드들 사이에 다른 노드를 끼워넣기 위해서 다른 노드들을 가리키는 변수(존재한다면)의 주소값을 변경시킬 필요도 없다. 각 노드가 가지는 포인터형 데이터(NextLLNode)만 바꾸어주면 된다.

반면 InsertLLHead는 헤드 노드로 지정된 노드 자체를 바꾸는 일이다. 즉, 헤드 노드를 가리키는 어떤 변수(위의 예시에서의 List)가 가진 주소값을 새로 헤드 노드가 될 노드의 주소값으로 변경해주어야 한다. 그렇기 때문에 매개변수로 더블 포인터 LLNode** Head가 필요하다.

더블 링크드 리스트(Double Linked List)

조금 더 개선된 버전의 링크드 리스트다. 링크드 리스트는 헤드 노드에서부터 탐색을 시작할 수밖에 없었다. 하지만 더블 링크드 리스트Double Linked List는 자식 노드에도 부모 노드의 정보를 저장한다. 따라서 뒤에서 앞으로의 탐색이 가능하다. 헤드 노드와 테일 노드에 대한 정보가 살아있다면, 노드가 소실되는 경우에도 어느 정도 복구가 가능하다.

그 외의 차이점은 없다.

따라서 추가, 삽입, 삭제 연산은 쉽지만 탐색 속도 및 추가 연산에는 단점을 보인다.

(DoubleLinkedList.c)

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

typedef int Element;

typedef struct _DLLNode
{
    Element Data;
    struct _DLLNode* PrevDLLNode;
    struct _DLLNode* NextDLLNode;
} DLLNode;

DLLNode* CreateDLLNode( Element data )
{
    DLLNode* Head = (DLLNode*)malloc( sizeof( DLLNode ) );

    Head->Data = data;
    Head->PrevDLLNode = NULL;
    Head->NextDLLNode = NULL;

    return Head;
}

void AppendDLLNode( DLLNode** Head, DLLNode* New )
{
    if ( (*Head) == NULL )
        *Head = New;
    else
    {
        DLLNode* Tail = (*Head);
        while ( Tail->NextDLLNode != NULL )
            Tail = Tail->NextDLLNode;

        Tail->NextDLLNode = New;
    }
}

void InsertDLLNode( DLLNode* Target, DLLNode* New )
{
    New->NextDLLNode = Target->NextDLLNode;
    New->PrevDLLNode = Target;

    if ( Target->NextDLLNode != NULL )
    {
        Target->NextDLLNode->PrevDLLNode = New;
        Target->NextDLLNode = New;
    }
}
void InsertDLLHead( DLLNode** Head, DLLNode* New )
{
    if ( (*Head) == NULL )
        *Head = New;
    else
    {
        New->NextDLLNode = (*Head);
        *Head = New;
    }
}

void RemoveDLLNode( DLLNode** Head, DLLNode* Target )
{
    if ( (*Head) == Target )
    {
        *Head = Target->NextDLLNode;
        if ( (*Head) != NULL )
            (*Head)->PrevDLLNode = NULL;
    }
    else
    {
        DLLNode* Tmp = Target;
        if ( Target->PrevDLLNode != NULL )
            Target->PrevDLLNode->NextDLLNode = Target->NextDLLNode;

        if ( Target->NextDLLNode != NULL )
            Target->NextDLLNode->PrevDLLNode = Target->PrevDLLNode;
    }

    Target->PrevDLLNode = NULL;
    Target->NextDLLNode = NULL;
}

DLLNode* SearchDLL( DLLNode* Head, int idx )
{
    DLLNode* Candidate = Head;
    while ( Candidate != NULL && (--idx) >= 0 )
        Candidate = Candidate->NextDLLNode;

    return Candidate;
}
int LengthDLL( DLLNode* Head )
{
    int cnt = 0;

    DLLNode* Current = Head;
    while ( Current != NULL )
    {
        Current = Current->NextDLLNode;
        cnt++;
    }

    return cnt;
}

void DestroyDLLNode( DLLNode* Node )
{
    free( Node );
}

탐색 속도나 추가 연산 속도를 빠르게 하기 위해서 Head, Tail, Cursor 포인터를 사용해 자료구조를 개선할 수 있다.

DLLNode* Head, * Tail, * Cursor;

// initialization
Head = (DLLNode*)malloc( sizeof( DLLNode ) );
Tail = (DLLNode*)malloc( sizeof( DLLNode ) );

Head->PrevDLLNode = Head;
Head->NextDLLNode = Tail;
Tail->PrevDLLNode = Head;
Tail->NextDLLNode = Tail;
Cursor = Head;

// move Cursor
if ( Cursor != Head )
    Cursor = Cursor->PrevDLLNode;
if ( Cursor != Tail->PrevDLLNode )
    Cursor = Cursor->NextDLLNode;

// delete Node
DLLNode* Tmp = Cursor;
Cursor = Cursor->PrevDLLNode;
Cursor->NextDLLNode = Tmp->NextDLLNode;
Cursor->NextDLLNode->PrevDLLNode = Cursor;
free( Tmp );

// append Node
DLLNode* NewNode = (DLLNode*)malloc( sizeof( DLLNode ) );
NewNode->Data = str;

NewNode->NextDLLNode = Cursor->NextDLLNode;
Cursor->NextDLLNode->PrevDLLNode = NewNode;
Cursor->NextDLLNode = NewNode;
NewNode->PrevDLLNode = Cursor;

Cursor = Cursor->NextDLLNode;

위와 같이 자료구조를 개선하는 경우 탐색 및 추가연산이 극적으로 빨라진다. 처음에 제안되었던 코드와 비교해보면 Cursor 덕분에 탐색이나 추가 시에 필요했던 while문이 없어도 된다.

방금의 코드와 같이 Head와 Tail을 사용하면 두 변수가 앞뒤에서 경계선 역할을 해주므로, 코드의 복잡도도 훨씬 낮아진다. 처음 제안된 코드에서는 해당 노드가 Head인지 아닌지를 계속 확인했다.

환형 링크드 리스트(Circular Linked List)

환형 링크드 리스트는 더블 링크드 리스트에서 미약하게나마 한 발자국 더 나아갔다. 더블 링크드 리스트와의 유일한 차이점은 헤드 노드와 테일 노드를 연결했다는 것뿐이다. 덕분에 테일 노드에 접근하는 속도가 빠르다는 장점을 갖는다. 추가 연산이 (데이터가 큰 경우) 앞의 두 링크드 리스트에 비해 훨씬 빨라진다.

환형 링크드 리스트의 특징을 요약하자면 추가, 삽입, 삭제 연산은 빠르지만 탐색 속도에는 여전히 한계가 있다고 말할 수 있다. 스트림 버퍼Stream buffer를 구현할 때 많이 쓰인다.

(CircularLinkedList.c)

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

typedef int Element;

typedef struct _CLLNode
{
    Element Data;
    struct _CLLNode* PrevCLLNode;
    struct _CLLNode* NextCLLNode;
} CLLNode;

CLLNode* CreateCLLNode( Element data )
{
    CLLNode* Head = (CLLNode*)malloc( sizeof( CLLNode ) );

    Head->Data = data;
    Head->PrevCLLNode = NULL;
    Head->NextCLLNode = NULL;

    return Head;
}

void AppendCLLNode( CLLNode** Head, CLLNode* New )
{
    if ( (*Head) == NULL )
    {
        *Head = New;
        (*Head)->PrevCLLNode = *Head;
        (*Head)->NextCLLNode = *Head;
    }
    else
    {
        CLLNode* Tail = (*Head)->PrevCLLNode;

        Tail->NextCLLNode->PrevCLLNode = New;
        Tail->NextCLLNode = New;

        New->NextCLLNode = (*Head);
        New->PrevCLLNode = Tail;
    }
}

void InsertCLLNode( CLLNode* Target, CLLNode* New )
{
    New->NextCLLNode = Target->NextCLLNode;
    New->PrevCLLNode = Target;

    if ( Target->NextCLLNode != NULL )
    {
        Target->NextCLLNode->PrevCLLNode = New;
        Target->NextCLLNode = New;
    }
}

void RemoveCLLNode( CLLNode** Head, CLLNode* Target )
{
    if ( (*Head) == Target )
    {
        (*Head)->PrevCLLNode->NextCLLNode = Target->NextCLLNode;
        (*Head)->NextCLLNode->PrevCLLNode = Target->PrevCLLNode;

        *Head = Target->NextCLLNode;
    }
    else
    {
        Target->PrevCLLNode->NextCLLNode = Target->NextCLLNode;
        Target->NextCLLNode->PrevCLLNode = Target->PrevCLLNode;
    }

    Target->PrevCLLNode = NULL;
    Target->NextCLLNode = NULL;
}

CLLNode* SearchCLL( CLLNode* Head, int idx )
{
    CLLNode* Candidate = Head;
    while ( Candidate != NULL && (--idx) >= 0 )
        Candidate = Candidate->NextCLLNode;

    return Candidate;
}
int LengthCLL( CLLNode* Head )
{
    int cnt = 0;

    CLLNode* Current = Head;
    while ( Current != NULL && Current != Head )
    {
        Current = Current->NextCLLNode;
        cnt++;
    }

    return cnt;
}

void DestroyCLLNode( CLLNode* Node )
{
    free( Node );
}

참고 서적:
박상현, 2022, 한빛미디어, 『이것이 자료구조+알고리즘이다』

참고 사이트:
나무위키: 연결 리스트
프로그래밍 서요: 백준 C언어 5397. 키로거