학부 CS/자료구조

자료구조(5) : 연결 리스트(1) - 연결 리스트, 반복자(Iterators), 자유 공간 리스트

Kstone 2025. 2. 27. 21:55

연결 리스트(Linked List)란?

연결 리스트 또한 자료구조의 일종으로, 배열과 달리 포인터를 사용해 다음 인덱스를 가리키는 형태의 자료구조이다.

배열은 순차적인 메모리 구조를 가지고 있어 다음 인덱스가 메모리주소가 1차이가 나는 반면,

연결 리스트로 자료구조를 채택하면 메모리 주소가 큰 폭으로 차이나게 된다. 연결 리스트는 각 요소가

어디에나 위치할 수 있기 때문이다. 단순히 포인터로 연결만 하면 되기 때문에, 위치 자체는 중요하지 않다.

더불어 배열 기반인 자료구조에 비해 데이터의 삽입/삭제 비용이 비교적 작다는 장점이 있기도 하다.

 

연결 리스트의 각 데이터 저장 단위를 노드라고 부르며, 노드에는 실제 데이터와 다음 데이터로 가는 포인터가 담겨있다.

그리고 한 가지 중요한 사실은, 항상 마지막 노드의 포인터가 가리키는 주소 값은 null 이라는 것이다.

노드 삽입(Node Insertion)

만약 리스트에 "GOAT" 라는 문자열이 저장된 노드를 삽입하고 싶다고 해보자. 노드 삽입은 크게 네 단계를 거친다.

  1. 현재 사용되지 않고 있는 노드 하나를 가져온다.
  2. 해당 노드의 데이터 필드를 문자열 "GOAT" 로 설정한다.
  3. 만약 기존 순서가 node : JOAT -> node : LEGEND 였고, 그 사이에 삽입할 예정이라면,
    먼저 GOAT 노드의 포인터가 LEGEND를 가리키게 한다. (JOAT의 포인터 값 그대로 가져오면 됨)
  4. 이후 JOAT의 포인터에 담긴 주소 값을 GOAT로 바꾸어주면 연결이 되고, 삽입이 완료된다.

해당 과정을 보면 알겠지만, 우리는 기존 연결 리스트에 있던 데이터의 위치를 단 하나도 바꾸지 않았다.

단순 포인터 주소값만 바꿔주며 연결 관계를 다시 재정립한 것이다.

이렇게 기존 배열 기반의 자료구조는 직접 데이터를 움직이기 때문에 삽입과 삭제의 비용이 비교적 크지만,

연결 리스트는 그럴 필요가 없기 때문에 이런 문제를 극복했다고 할 수 있다.

물론, 시간적 비용을 줄이는 대신, 공간적 비용을 늘려 메모리는 더 사용한다....

사진으로 삽입 과정을 보면 다음과 같다

노드 삭제(Node Deletion)

노드를 삭제하는 것은 더욱 더 간단하다. 노드를 새로 가져올 필요도 없이, 기존의 주소값만 손봐주면 끝난다.

만약 위의 사진에서 GAT를 삭제한다면, 다시 FAT의 포인터를 HAT 노드의 주소값으로 설정해주면 끝난다.

연결 고리에서 GAT만 쏙 끊기는 것이기 때문에, 해당 과정을 거침으로써 매우 손쉽게 노드를 삭제할 수 있다.

 

한 가지 유의해야 할 점은, 노드를 삭제한 후 동떨어진 노드의 메모리는 사용하지 않는다면 꼭 반환해야 한다.

기본적으로 동적 할당을 통해 사용하므로, 내가 해제하지 않는 이상 계속 메모리가 할당되어 있다.

무서운 꼴을 보고싶지 않다면 제때제때 메모리를 반환하기 바란다.(필자도 알고싶지 않았다.)

C++에서 연결 리스트의 구현

위에서도 이야기 했지만, 단순하게 노드는 데이터를 담는 부분과 포인터를 담는 부분으로 구성되어 있다.

가장 간단하게 노드를 클래스를 사용해 구현해보면 다음과 같다.

class Node {
    private:
    
        char data[3];
        Node *link;
};

 

이렇게 구현하면 3글자 문자열을 저장할 수 있는 연결 리스트의 노드가 만들어진 것이다.

그냥 단순히 구현하면 저렇지만, 사람들은 효율과 보안 등의 이유때문에 새로운 디자인 방법들을 생각해냈다.

Node Design 1

처음 생각한 방법은 그냥 같은 타입의 포인터 first를 만들어서 데이터에 접근하려는 시도이다.

Node *first; 명령어로 노드에 대한 포인터를 만들고, 이 포인터가 노드의 데이터 멤버들에 접근하게끔 설정한다.

first -> data, first -> link ,,,, 등과 같이 접근할 수 있게 하려고 했으나,

우리가 앞서 클래스에서 data와 link를 private 접근 한정자로 설정했기 때문에, 클래스 바깥에서 직접 접근이 불가능하다.

Node Design 2

그래서 두 번째로 생각해낸 방법은, 접근 한정자 문제를 해결하기 위해 게터/세터를 사용하는 것이다.

오직 데이터를 접근할 때 게터/세터 외에는 접근을 허용하지 않는다. 이는 사실상 가장 ideal 한 해결법이기도 하다.

Node Design 3

극악무도한 손필기

세 번째 방법은, 노드 전체(리스트 전체)를 묶어주는 하나의 클래스를 추가하는 것이다.

클래스 외부에 있을 때 접근 한정자 문제가 생기는 것이므로, 아예 클래스 내부에 노드 클래스를 구현하자는 이야기다.

그래서 연결 리스트 전체를 포함하는 chain 클래스를 하나 생성해 그 안에서 node 클래스를 구현할 것이다.

이런 관계를 HAS-A relationship 이라고 한다.

ex ) ThreeLetterChain HAS-A ThreeLetter Node

 

HAS-A 관계란, 어떤 데이터 타입 A가 개념적으로 B를 포함하거나 혹은 B가 A의 일부인 경우, A HAS-A B 라고 한다.

쉽게 이야기하면, A 타입의 객체가 B 타입의 객체를 정해진 수량만큼 포함하고 있을 때라고도 할 수 있다.

이 관계를 이용해 구현하는 법도 크게 세 가지로 나뉘는데, 간단해서 짧게 설명하고 넘어가겠다.

  1. Chain 클래스가 노드를 포함하지 않고, first 라는 접근 포인터만 포함해, 첫 번째 노드에 연결시켜주는 방법 
    • 그러나 해당 방법은 연결 리스트에 노드 수가 몇 개가 있는지 직접 세어봐야만 알 수 있다. 
  2. Node를 구현할 때, Chain 클래스를 friend 선언해 클래스 멤버에 접근할 수 있게 하는 방법
    • Chain의 멤버함수가 Node의 멤버변수에 접근할 수 있게끔 해준다.
  3. 중첩 클래스로 작성하는 방법
    • 가장 직관적인 방법으로, 결국 클래스 내부에 같이 있으므로 접근이 가능하다.

이 중 중첩 클래스로 작성하는 법에 대한 예시를 보여주겠다.

class ThreeLetterChain {
    public:
    .
    .
 
    private:
 
        class ThreeLetterNode{   //nested class
            public:
                
                char data[3];
                ThreeLetterNode *link;
        };
        ThreeLetterNode *first;
};

 

이런 식으로, Chain 클래스의 private 부분에 Node 클래스를 구현해준다. 이때, Node 클래스 멤버는 public으로 해도 된다.

왜냐면, 어차피 Chain의 private 부에 선언되어있기 때문에, Chain 클래스를 제외한 나머지 클래스는

Node 멤버가 public이어도 절대 접근할 수 없다. 따라서 내부에서도 접근하기 편하게 하기 위해, Node는 public으로 한다.

Chain 클래스의 연산들(Chain Manipulation Operations)

클래스 연산들을 살펴보기 전에, 간단하게 C++ 에서 포인터, 동적 데이터 관련 연산들을 알아보고 가자.

기본적으로 노드를 새로 생성하면, new 명령어를 사용해 메모리를 할당해준다.

  • NodeA *a;     a = new NodeA;
  • NodeB *b;     b = new NodeB; 와 같은 식이다.

그리고 new 를 사용해서 메모리를 동적 할당 했다면, 사용 후 반드시 메모리를 반환해야한다.

  • delete a;       delete b;

그리고 포인터 변수는, 메모리 주소값을 저장하므로 당연히 null(0) 값을 가질 수 있다.

위에서도 이야기했듯이, 연결 리스트에서도 마지막 노드는 null 값을 가질 수 있다!

포인터 변수에서 헷갈릴 만한 연산이 존재하는데, 어떻게 보면 얕은 복사와 깊은 복사에도 해당하는 내용이다.

 

만약에 두 노드 x, y가 있다고 해보자. x = y; 명령어를 작성한다면 어떤 일이 일어날까?

y가 가리키는 메모리 주소와 같은 값을 x도 가리키게 된다. 즉, x가 가리키고 있던 메모리 주소는 그냥 사라져버린다.

 

반면에 *x = *y; 명령어를 작성한다면, y가 가리키는 메모리 주소에 존재하는 데이터를, x가 가리키는 메모리 주소 데이터로 덮어 씌우게 된다. 즉, x와 y가 가리키는 메모리 공간의 적혀있는 데이터가 같은 값이 되는 것이다.(*y로)

이미 포인터에 배웠다면, 잘 이해할 수 있을 거라 믿는다.

그림으로 빠르게 이해하자.

2-node list creation

맨 처음 두 개의 노드를 생성할 때는, 일반적으로 뒤에서부터 노드를 생성하는 것이 규칙이다.

그래야 두 노드를 이어주기가 편하기 때문이다.

void Chain::Create2() {

    ChainNode *second = new ChainNode(20, 0); // (data, link) 이다.
    ChainNode *first = new ChainNode(10, second);
}

 

이러면 먼저 second 노드를 생성하고, 그 만들어진 노드를 가리키는 first 포인터가 생긴다.

Node insertion after node-x

일반적인 노드를 삽입하는 방법은 두 가지 경우로 나뉜다.

빈 리스트에 삽입하는 경우와, 기존의 리스트 중간에 삽입하는 경우인데, 간단하게 조건문을 통해 구현 가능하다.

void Chain::InsertItem(ChainNode *x) {

    if(first)
        
        x->link = new ChainNode(50, x->link);
    else
        
        first = new ChainNode(50);
}

 

이때, first 값을 기준으로 0(비어있으면) 빈 리스트에 삽입하는 경우로 가고, 뭐라도 가리킨다면 중간에 삽입한다.

만약 x 노드 다음에 넣는다고 가정하면, 기존 x->link 값을 새로운 노드로 바꾸어 주어야 하므로,

x->link = new ChainNode(50, x->link) 를 통해 새로운 노드를 가리킴과 동시에, 새로운 노드는 기존에 x가 가리키던

노드를 가리키게끔 설정해주어 자연스럽게 리스트가 연결될 수 있도록 해준다.

 

삭제나 다른 연산들은 이후 더 알아보면서 소개하도록 하겠다.

템플릿을 이용한 Chain class 의 구현

여태 배운 Chain 클래스를 템플릿을 이용해 범용성있게 구현해보면, 다음과 같다.

template <class T> class Chain;
 
template <class T>
class ChainNode {
    
    friend class Chain<T>;
    private:
        
        T data;
        ChainNode<T> *link;
};

template <class T>
class Chain {

    public:
    
        Chain() {first = 0;};    // constructor initializing first to 0
        // chain manipulation operations
        .
        .
        .
    private:
    
        ChainNode<T> *first;
};

 

앞서 언급한 friend 선언이나, 내부에서 사용하는 방식들이 채택된 모습이다.

이렇게 템플릿을 이용해서 구현하면, Chain 타입을 정의할 때 Chain<int> intlist; 와 같이 하면 int 타입으로 생성된다.

템플릿을 활용하는 김에, 위에서 다루지 않은 노드 삽입 함수를 하나 소개하고 가겠다. 맨 뒤에 노드를 삽입하는 함수인데,

template<class T>
void Chain<T>::InsertBack(const T& e) {

    if(first){//nonempty chain
        last→link = new ChainNode<T>(e);
        last = last→link;
    }
    
    else first = last = new ChainNode<T>(e);
}

 

여기서는 last 라는 위치를 파악하기 위한 포인터 변수를 하나 사용한다. 해당 변수는 마지막 노드를 가리키는 변수이다.

뒤에 새로운 노드가 삽입되면 last에 저장된 값도 바뀌어야 하므로, last->link 가 삽입될 마지막 노드를 가리키게 되고,

last는 마지막 노드를 가리키면 되므로, last = last->link 로 다시 초기화해주면 자연스레 이어진다.

반복자(Iterator)

반복자는 컨테이너 클래스에서 각 데이터 요소에 한 번에 하나씩 접근할 수 있게 해주는 객체이다.

그냥 반복문을 돌릴때는 접근하는 데이터 타입만 맞추면 되지만, 클래스로 할 경우 그 타입을 정하기 애매하기 때문이다.

반복자를 통해서 얻을 수 있는 값의 종류는 굉장히 다양한데, 추려보면 다음과 같다.

  1. 컨테이너 클래스의 모든 정수 값을 출력한다.
  2. 컨테이너 클래스의 모든 정수 값들 중 최대, 최소, 평균, 중앙, 최빈값을 얻는다.
  3. 컨테이너 클래스의 모든 정수 값들의 합, 곱, 제곱의 합 등을 얻는다.
  4. 특정 조건을 만족하는 컨테이너 클래스의 모든 정수 값을 출력한다.
  5. 특정 함수의 최댓값을 갖게하는 정수 값을 컨테이너 클래스에서 얻는다.

이런 연산들을 할 수 있고, 꼭 정수에 국한된건 아니다.

수도코드로 반복자를 활용한 방식을 살펴보면,

int x = std::numeric_limits<int>::min();
for each item in C {

    currentItem = current item of C;
    x = max(currentItem, x);
}
return x;

 

최댓값을 찾는 함수를 다음과 같이 구현해줄 수 있다. 즉, 반복문의 반복 주체를 컨테이너 클래스의 객체로 하는 것이다.

기본적으로 반복자는 포인터 변수로 인식되어 메모리 주소값을 기반으로 작동한다.

이를 이용해 STL의 문자열 copy 함수를 구현할 수도 있다.

template <class Iterator>
void copy(Iterator start, Iterator end, Iterator to) {
    //copy from [start, end] to [to, to+end-start]
    while(start != end)
        {*to = *start; start++; to++;}
}

 

두 함수를 살펴보면, 반복자의 사용에 도움을 주는 연산자들이 다름을 알 수 있다.

반복자는 그 사용하는 연산자에 따라 종류가 다섯 가지로 나뉜다.

  1. All : * 를 이용해 실제 저장된 데이터를 파악하고, ==, != 등을 이용해 모든 데이터를 검수한다.
  2. Input : 가리키는 데이터에 대해 입력, 추가적으로 읽기 권한을 제공한다.
  3. Output : 데이터에 관한 출력 권한을 제공한다.
  4. Forward/Bidirectional : 주소 값이 증감하는 연산으로, ++, -- 연산을 사용한다.
  5. Random access : 말 그대로 주소값이 랜덤 이동한다. 점프라고도 하며, i+2, 2j + 1 등 변칙적인 패턴을 갖는다.

원형 리스트(Circular Lists)

이전에 큐를 배우며 원형 큐를 배웠었는데, 원형 리스트도 이와 비슷한 맥락으로 등장했다.

원래대로라면 연결 리스트의 마지막 노드의 link 부분은 null 값이 저장되어야 한다.

원형 리스트는 그 대신에, 마지막 노드의 link가 첫 번째 노드로 향하도록 해주는 것이다. 마치 하나로 연결된 것처럼.

이런 원형 리스트에서 새로운 노드를 삽입하는 경우를 알아보자.

 

여기서는 리스트의 맨 앞에 노드를 삽입하는 경우에 대해서 살펴볼 것이다.

왜냐하면 해당 과정이 다른 삽입 경우보다 더 간단하기 때문이다. 마지막 노드의 링크부분의 값만 잘 움직이면 된다.

앞서 노드를 삽입할 때 메모리 주소 값을 이리저리 옮긴 것을 생각하며 코드를 보자.

template <class T>
void CircularList<T>::InsertFront(const T& e) {
//insert the element e at the ‘‘front’’ of the circular list *this,
// where last points to the last node in the list

    ChainNode<T> *newNode = new ChainNode<T>(e);
    if(last) {
    
        newNode→link = last→link;
        last→link = newNode;
    }
    else {
    
        last = newNode;
        newNode→link = newNode;
    }
}

 

먼저 새로 삽입될 노드 객체를 생성해주고, last 값을 통해 현재 마지막 노드가 존재하는지를 알아본다.

이후 비어있는 리스트가 아니라면, 기존 last->link 값은 첫 번째 노드일테니, 새로 삽입할 노드가 맨 앞에 가므로,

새로 삽입할 노드의 link 부분이 last->link가 되면 노드가 잘 이어진다. 이후 last->link 를 맨 앞의 newNode로 지정하면 끝.

만약 빈 리스트라면 하나의 노드만 존재하므로, 자기 자신을 가리키게 설정해주면 된다.

여기서 예외 처리를 진행했을 때의 오류를 방지하고자, 아예 예외 처리를 필요 없게 해줄 수도 있다.

바로 '헤더 노드'를 사용하는 것이다. 헤더 노드는 데이터가 없는 더미 노드로, 리스트의 시작을 헤더 노드로 하면 된다.

만약 빈 원형 리스트라면, 헤더 노드 하나만 존재하는 상태인 것이다. 그럼 굳이 위의 코드에서 빈 경우를 생각 할

필요가 없다.

자유 공간 리스트(Available Space Lists)

자유 공간 리스트는 현재 데이터가 저장되어있지 않은 노드들을 가지고 있는 리스트이다.

일종의 메모리 버퍼라고 생각해도 좋다. 필요시 자유 공간 리스트의 노드를 가져와서 데이터를 저장하는 것이다.

굳이 새로 노드를 생성할 필요 없이, 끌어다 쓰거나 필요 없어지면 다시 자유 공간 리스트로 보내면 되므로,

노드의 파괴(destruction)가 매우 적은 시간이 걸리게 된다.

 

자유 공간 리스트에서 노드를 가져오고 반환하는 코드를 알아보자.

template <class T>
ChainNode<T>* CircularList<T>::GetNode() {

    ChainNode<T>* x;

    if(av) {
    
        x = av;
        av = av→link;
    }
    else x = new ChainNode<T>;
    return x;
}

 

해당 코드는 av list에서 노드를 가져오는 코드로, av가 자유 공간 리스트를 나타날 때 av가 비어있지 않다면,

포인터 변수 x를 사용해 av의 맨 앞에 있는 노드를 자신의 노드로 만들어 가져가는 방식이다.

이후 av = av->link를 해주면, av의 맨 앞의 노드는 기존의 것에서 하나 다음 노드가 됨을 알 수 있다.

template <class T>
void CircularList<T>::RetNode(ChainNode<T>*& x) {

    x→link = av;
    av = x;
    x = 0;
}

 

반환의 경우는 더욱 간단한데, x 노드를 다시 av list로 돌려준다고 가정한다면,

x의 링크부분이 가리키는 노드를 av의 첫 번째 노드로 하고, av = x 로 다시 설정해주면 x가 av의 처음 노드가 된다.

이후 x 변수에는 null 값을 저장해주면 자연스레 x가 av의 맨 처음 노드로 반환된 모습을 볼 수 있다.

이렇게 노드를 하나씩 받고 지우고 할 수도 있지만, 자유 공간 리스트를 사용시 리스트 전체를 삭제할 수도 있다.

 

template <class KeyT>
void CircularList<T>::~CircularList() {

    if(last) {

        ChainNode<T>* first = last→link;
        last→link = av;
        av = first;  
        last = 0;
    }
}

 

해당 코드가 바로 그 예시로, 원형 리스트 전체를 자유 공간 리스트로 보내는 코드이다.

잘 읽어보면, 리스트가 비어있지 않을 경우, last -> link 즉, 첫 번째 노드를 가리키는 주소값을 first에 저장한다.

이후 last -> link를 av로 보내어 av list와 연결해주고, av = first 를 실행시키면, av의 맨 처음 노드가

기존 원형 리스트의 맨 처음 노드가 되면서 노드 전체가 av list 와 이어지게 된다.

즉, 원형 리스트 전체를 자유 공간 리스트로 보내버린 것이다. 해당 함수의 시간 복잡도는 $O(1)$로 매우 효율적이다!!

 

 

연결 리스트의 첫 포스트는 여기서 마무리 짓도록 하겠다. 더 쓰다보면 너무 길어질 것 같다.

이제부터 뭔가 생소한 자료구조들이 나오게 될 것인데, 이런 자료구조들도 상황에 따라 매우 유용하게 쓰이니

허투루 알지 않고 많이 찾아보면 좋겠다. 물론 나부터 열심히 해야겠지만..

아무튼 다음 포스트까지 해서 연결 리스트를 마무리 지을 것 같다. 그럼 다음 포스트에서 뵙겠다!

저작자표시 비영리 동일조건 (새창열림)