C/C++ 연결 리스트(Linked List)-단순 연결 리스트

개요

연결 리스트의 기본이 되는 단순 연결 리스트에 대해 알아보자. 단순 연결 리스트는 다음 노드에 대한 참조만을 가진 가장 단순한 형태의 연결 리스트이다. 가장 마지막 원소를 찾으려면 리스트 끝까지 찾아가야 하기 때문에(O(n)), 마지막 원소를 가리키는 참조를 따로 가지는 형태의 변형도 있다. 또한, 한 번 연결이 끊기거나, 체인이 잘 못된 경우, 모든 뒤의 데이터가 유실되는 단점이 있다.

Node구성

struct Node
{
    int data;
    Node* next;
} *first = NULL;

Node* last = NULL;

first는 노드의 시작을, last는 노드의 끝을 나타낸다. struct로 생성한 Node는 실제 요소 값을 담는 data와 다음 노드를 향한 주소 값을 담는 포인터로 구성된다.

create함수-연결 리스트 생성

void create(int A[], int  n)
{
    Node* t;
    first = new Node;
    first->data = A[0];
    first->next = NULL;
    last = first;

    for (int i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

first와 last에 대한 노드 할당을 먼저 한다. 하나의 노드이므로 first와 last가 일치하며, last의 next 노드는 없으므로 NULL이다. for루프에서 루프마다 새로운 노드를 힙에 생성하여, data에 요소 값을 넣은 뒤, last의 next 참조로 이어서 연결 리스트의 끝에 추구한다. 새로운 노드마다 끝에 붙으면 last가 되므로, 루프마다 last의 위치를 옮기는 작업이 필요하다.(last = t;)

Count함수-요소의 개수 계산

int Count(Node* t)
{
    //if (t == 0)
    //    return 0;
    //return Count(t->next) + 1;

    int x = 0;

    if (t)
    {
        x = Count(t->next) + 1;
        return x;
    }
    else
    {
        return x;
    }
}

int lCOunt(Node* t)
{
    int l = 0;
    while (t)
    {
        l++;
        t = t->next;
    }
    return l;
}

재귀함수를 사용한 버전과 루프를 활용한 버전이 있다. 둘 다 동일하게, 각 노드를 p->next를 통해 순차적으로 접근(traversing)하며, NULL(연결 리스트의 끝)이 아닐 경우, count를 1씩 늘려 반환한다. 일반적으로, t= t->next;를 통해 다음 노드에 접근한다.

Max함수-요소 들 중 가장 큰 값을 반환

int Max(Node* p)
{
    int x = INT32_MIN;
    while (p)
    {
        if (p->data > x)
            x = p->data;
        p = p->next;
    }
    return x;
}

int RMax(Node* p)
{
    int x = INT_MIN;
    if (p == NULL)
        return x;
    x = RMax(p->next);
    return (p->data > x) ? p->data : x;

}

루프를 이용한 구현은 그저 요소를 traversing하며 큰 값이 있으면 x에 담는 방식이며, 재구 방식을 살펴보면, 주요한 계산인 (p->data > x) ? p->data : x; 전에 재귀함수를 호출하여, 함수의 반환을 노드의 끝으로 미룬 뒤, 노드가 되돌아오며, 그 전의 요소의 값과 현재 노드의 값 중 큰 것을 반환한다.

Display함수-모든 노드의 요소를 출력

void Display(Node* t)
{
    while (t != NULL)
    {
        printf("%d ", t->data);
        t = t->next;
    }
}

while루프로 노드의 끝까지 진행하며, data를 printf한다.

Search함수-해당 값을 가진 노드 반환

// move to head, q를 꼬리 포인터, p를 헤드 포인터로해서 전 후의 노드를 알 수 있다.
Node* Search(Node* p, int key)
{
    Node* q = NULL;

    while (p)
    {
        if (key == p->data)
        {
            q->next = p->next;
            p->next = first;
            first = p;
            return p;
        }
        q=p;
        p = p->next;
    }
}

이 함수부터 특이하게, 두 개의 포인터를 사용한다. 머리 포인터와 꼬리 포인터로, 노드 사이를 옮겨 다니며, 해당 노드와 방금 전에 접근한 노드를 담는다. 일반적인 search는 그냥 하나의 포인터를 이용해 노드를 옮겨 다니며, 해당 노드의 data가 key와 일치하면 그 노드를 반환하면 된다. 하지만, 위에 구현한 것은 해당 key를 search 한 다음, 그 노드를 가장 맨 앞으로 옮겨와 다음 같은 key를 search할 때, 바로 첫 노드에서 반환할 수 있도록 한 "효율적인 search"방식이다.

q->next = p->next;

옮기려는 key와 일치하는 노드가 p이며, 그 전 노드의 next를 p가 아닌 p의 다음 노드로 연결하여, 노드 p를 연결 리스트에서 뺀다.

p->next = first;
p = first;

p의 다음 노드를 first로 하고, first를 p로 설정함으로써 p를 가장 맨 앞의 노드로 설정한다.

이 방식으로 다음 같은 key의 search를 한 번에 끝낼 수 있게 된다.

Insert함수-원하는 위치에 새로운 노드 추가

void Insert(Node* p, int x, int index)
{
    Node* t;
    if (index < 0 || index > Count(p))
        return;

    t = new Node;
    t->data = x;

    if (index == 0)
    {
        t->next = first;
        first = t;
    }
    else
    {
        for (int i = 0 ; i < index - 1; i++)
        {
            p = p->next;
        }
        t->next = p->next;
        p->next = t;
    }
}

노드를 insert하는 경우는 크게 둘로 나뉜다. 맨 앞에 추가하는 경우와 그 외의 원하는 위치에 삽입하는 경우이다. 먼저 맨 앞에 삽입하는 방식은 새로운 노드로의 first의 이동이 필요하하다.

     if (index == 0)
    {
        t->next = first;
        first = t;
    }

원하는 위치에 삽입하는 경우는 해당 index로 노드 이동을 한 뒤,(여기서 index는 맨 처음 노드가 1일 때의 index이다). 그 index의 노드 뒤에 새로운 노드를 추가한다.( 1 2 3의 노드 배열에 index = 3에 추가하면 1 2 3 new node가 된다.)

        for (int i = 0 ; i < index - 1; i++)
        {
            p = p->next;
        }
        t->next = p->next;
        p->next = t;

SortedInsert함수-값의 순서대로 노드를 삽입

이미 오름차순에 따라 배열된 연결 리스트에서 값을 가진 새로운 노드를 적절한 위치에 삽입한다.

void SortedInsert(Node* p, int x)
{
    Node* t, * q = NULL;
    t = new Node;
    t->data = x;
    t->next = NULL;

    if (first == NULL)
        first = t;
    else
    {
        while (p && p->data < x)
        {
            q = p;
            p = p->next;
        }
        if (p == first)
        {
            t->next = first;
            first = t;
        }
        else
        {
            t->next = q->next;
            q->next = t;
        }
    }
}

두 개의 포인터를 이용해 전 후의 노드를 할당하고, p->data가 원하는 값 x보다 큰 경우까지 traversing한다.

        while (p && p->data < x)
        {
            q = p;
            p = p->next;
        }

q에 p의 노드를 할당하고, p는 한 칸 뒤로 이동함으로써 연속적인 노드를 할당 받게 된다.

        if (p == first)
        {
            t->next = first;
            first = t;
        }
        else
        {
            t->next = q->next;
            q->next = t;
        }

p가 first노드 즉, 한 개의 노드밖에 없는 연결 리스트면 새로 생성한 노드를 앞에 추가하고, first를 해당 노드로 바꾼다.

그 외에는 새로운 노드를 p의 앞에 추가하므로, p 앞의 노드, q의 다음 포인터를 t로 설정하고, t의 다음 노드를 p로 설정한다.

Delete함수-원하는 노드 삭제

원하는 index의 노드를 삭제하고, 삭제하는 노드의 data를 반환한다.

int Delete(Node* p, int index)
{
    Node* q = NULL;
    int x = -1;

    if (index < 1 || index > Count(p))
        return -1;
    if (index == 1)
    {
        q = first;
        x = first->data;
        first = first->next;
        delete q;
        return x;
    }
    else
    {
        for (int i = 0; i < index - 1 && p; i++)
        {
            q = p;
            p = p->next;
        }
        q->next = p->next;
        x = p->data;
        delete p;
        return x;
    }
}

이 것도 동일하게, 맨 처음의 노드를 삭제하는가, 중간에 껴있는 노드를 삭제 하는 경우에 따라 나뉜다. 첫 노드를 삭제하는 경우,

    if (index == 1)
    {
        q = first;
        x = first->data;
        first = first->next;
        delete q;
        return x;
    }

첫 노드의 data를 저장하여 반환하며, first를 한 칸 뒤의 노드로 옮긴 후, 해당 노드를 삭제한다.

        for (int i = 0; i < index - 1 && p; i++)
        {
            q = p;
            p = p->next;
        }
        q->next = p->next;
        x = p->data;
        delete p;
        return x;

꼬리, 머리 포인터를 통해 해당 index의 노드로 움직인 뒤, p의 노드를 빼기 위해, 꼬리 포인터(q)의 다음 노드를 p 다음의 노드로 설정하여, p를 향한 연결 고리를 끊는다. 그 후, p의 data를 반환하고, 메모리 해제한다.

Reverse함수-연결 리스트의 순서 반전

연결 리스트의 요소 연결 순서를 뒤집는 함수이다. 방식은 크게 두 가지이다. 포인터의 연결은 그대로 놓고, 요소의 값을 임의의 배열에 저장하고, 값 자체를 뒤집어서 새롭게 저장하는 방식이 있고, 포인터의 연결 순서 자체를 바꾸는 방식(노드의 next가 다음 노드가 아니라, 그 전 노드를 향하도록 하는 방식)이 있다. 아래의 Reverse1은 값을 바꾸고, Reverse2는 포인터를 바꾼다. 일반적으로, pointer 변경 방식이 더 효율적이다.

void Reverse1(Node* p)
{
    int* A, i = 0;
    Node* q = p;
    A = new int[Count(p)];
    while (q!= NULL)
    {
        A[i] = q->data;
        q = q->next;
        i++;
    }
    i--;
    while (q!= NULL)
    {
        q->data = A[i];
        q = q->next;
        i--;
    }
}

A라는 새로운 배열을 생성하여, 임시로 연결 리스트의 요소 값들을 저장한다. 그 후, 거꾸로 루프를 돌며 노드 이동을 하며, 각각의 노드에 배열 값을 넣는다.

void Reverse2(Node* p)
{
    Node* q = NULL, * r = NULL;
    while (p!= NULL)
    {
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    first = q;
}

void Reverse3(Node* q, Node* p)
{
    if (p)
    {
        Reverse3(p, p->next);
        p->next = q;
    }
    else
        first = q;
}

3개의 포인터를 사용하고, 3개의 포인터는 연속적인 노드를 나타낸다. 그리고, 그 3개의 포인터는 p=p->next를 통해 미끄러지듯 순차적으로 뒤의 노드로 이동한다. 이를 sliding기법이라고 한다.

        r = q;
        q = p;
        p = p->next;

이러한 방식으로, sliding한다. r이 첫 노드, q가 그 다음 노드, p가 마지막 노드이며 순차적이다.

각 루프마다 q->next를 그 전의 노드인 r로 향하게 함으로써 노드의 포인터 연결을 뒤집는다. 왜 3개의 포인터가 필요한지 헷갈릴 수 있다. r은 당연하게도 연결을 뒤집을 그 전 노드이므로 필요하다. p는 다음 노드로의 이동을 위해 필요하다. q의 경우에는 루프마다 next가 r로 바뀌므로, q를 통해 다음 노드로 이동하려고 하면, 제대로 된 방향으로 움직이지 못한다. 그렇기에 p를 통해 노드 이동, q,r을 이용해 노드 사이의 연결을 뒤집는다.

Reverse3 함수는 같은 함수의 구현을 재귀 함수로 표현한 것 뿐이다.

Merge함수-연결 리스트의 병합

연결 리스트의 병합은 쉽다. 하지만, 오름차순으로 나열된 두 개의 연결 리스트를 병합하려면 방법이 꽤 복잡하다.

void Merge(Node* p, Node* q)
{
    Node* last;
    Node* third;
    if (p->data < q->data)
    {
        third = last = p;
        p = p->next;
        third->next = NULL;
    }
    else
    {
        third = last = q;
        q = q->next;
        third->next = NULL;
    }
    while (p && q)
    {
        if (p->data < q->data)
        {
            last->next = p;
            last = p;
            p = p->next;
            last->next = NULL;
        }
        else
        {
            last->next = q;
            last = q;
            q = q->next;
            last->next = NULL;
        }
    }
    if (p)
        last->next = p;
    if (q)
        last->next = q;
}

그림에서 보듯이, 두 개의 연결 리스트에 대해 노드 포인터 p와 q를 이용해 p와 q의 노드 값을 비교해 작은 노드에 last->next를 통해 연결을 만들고, 해당 p또는 q 노드를 한 칸 뒤로 옮기는 방식을 사용한다. 마지막에는 하나 남은 노드를 연결하여 마무리한다.

    if (p->data < q->data)
    {
        third = last = p;
        p = p->next;
        third->next = NULL;
    }
    else
    {
        third = last = q;
        q = q->next;
        third->next = NULL;
    }

첫 노드 두 개를 비교하여, 작은 쪽을 third라는 새로운 연결 리스트의 시작을 할당한다.

    while (p && q)
    {
        if (p->data < q->data)
        {
            last->next = p;
            last = p;
            p = p->next;
            last->next = NULL;
        }
        else
        {
            last->next = q;
            last = q;
            q = q->next;
            last->next = NULL;
        }
    }

p와 q의 노드가 끝날 때까지 계속 비교하며, 값이 작은 쪽으로 last->next로 연결을 만들고, 그 노드에 last를 할당한다.

IsLoop함수-연결 리스트가 루프 인지 파악

int isLoop(Node* f)
{
    Node* p, * q;

    p = q = f;
    do
    {
        p = p->next;
        q = q->next;
        q = q ? q->next : q;

    } while (p && q && p != q);

    if (p == q)
        return 1;
    else
        return 0;
}

무언가가 루프인지 끝이 있는지는 이 방법으로 쉽게 알 수 있다. 예를 들어, 원형 트랙에 두 명의 사람이 뛰고 있고, 각 사람이 뛰는 속도가 다른 경우를 보자. 만약 트랙이 일자라면 두 사람이 만날 일은 없다. 하지만, 원형이라면 언젠가 속도가 빠른 사람이 속도가 느린 사람을 다시 만나고 추월하게 된다. 이를 활용하여 루프마다 p는 한 번만 이동, q는 두 번 이동함으로써 언젠가 p와q가 만나는 지를 파악한다.

마무리

이번 글에서는 단순 연결 리스트가 무엇 인지부터 해서, 단순 연결 리스트에 필요한 다양한 함수를 구현해 보았다. 모든 함수에서 알 수 있듯이 루프를 통해 처음 노드에서 필요한 노드 또는 끝까지 매 번 traversing을 해야 했다. 구현이 단순해 지기는 하지만, 탐색이나, 조정에서 시간이 걸리기 때문에 효율적인 연결 리스트라고 하기 어려울 수 있다. 다음 글에서는 C++로 이 함수들을 구현해보고자 한다.