자료구조 - 연결 리스트

컴퓨터에서는 많은 양의 데이터를 처리하기 위해 자료구조를 사용합니다.

자료구조는 일련의 설계규칙에 따라 데이터를 처리하는데

이 포스트에서는 그 중에서도 연결 리스트에 대해 알아보겠습니다.

 

1) 연결 리스트

연결 리스트는 자료구조 중에서 선형 자료구조에 속합니다.

선형 자료구조는 데이터가 순차적으로 나열되어 있는 자료구조를 일컫는데,

대표적으로 배열, 연결 리스트, 스택 등이 있습니다.

 

연결 리스트의 특징으로는 

 

바로 현재 노드의 정보와 다음 노드만을 갖는 단방향 연결 리스트와

 

 

바로 현재 노드의 정보에 추가적으로 앞의 노드와 바로 뒤의 노드 둘다를 갖는 양방향 연결 리스트가 존재합니다.

일반적으로는 순회와 삽입/삭제의 용이함을 위해 양방향 연결 리스트를 사용합니다. 

 

연결 리스트의 특징은 자료구조의 방향성을 갖고 있다는 것인데,

 

[1] -> [2] -> [3] -> [4]

 

와 같은 연결 리스트가 존재한다고 했을때,

 

[3] 이 삭제되면, [3] 노드에서 갖고 있던 정보를 바탕으로 앞과 뒤의 노드를 이어주게 됩니다.

결과적으로 리스트는 

 

[1] -> [2] -> [4] 와 같이 연결되게 됩니다.

 

반대로, [3]과 [4] 사이에 [5] 노드가 추가된다면, [3]과 [4] 노드 사이의 연결고리를 끊고 

 

[1] -> [2] -> [3] -> [5] -> [4] 와 같이 연결되게 됩니다.

 

이러한 특징을 갖고 있기에 리스트의 가장 큰 장점으로는 빠른 삽입 / 삭제가 가능하다는 것입니다.

대신 배열과 같이 인덱스를 통한 임의 접근이 불가능합니다.

왜냐하면 컴퓨터는 리스트의 시작점만을 알고 있기 때문입니다.

 

또 연결 리스트에서 가장 앞에 위치한 노드를 Head, 가장 뒤에 위치한 노드를 Tail이라고 합니다.

 

최종적으로 정리하면 다음과 같습니다.

 

따라서 연결 리스트의 경우, 검색 위주의 연산보다는 삽입/삭제가 빈번한 경우 사용하는 것이 좋습니다.

 

2) 예제

연결 리스트는 STL로 제공되고 있지만,

리스트가 내부적으로 어떻게 동작되는 지 알기 위해 양방향 연결 리스트를 코드로 한번 작성해보겠습니다.

 

클래스는 총 2개로 구성됩니다.

하나는 데이터를 갖고 있으며 이전, 이후 노드를 가리킬 노드 클래스입니다. 

 

마지막 하나는 노드들이 선형적으로 연결된 연결 리스트입니다.

이때 Head와 Tail은 더미노드로 지정하여 연산에서 편의성을 높여주도록 하였습니다.

 

// 리스트의 역할 수행
class List
{
public:
    // Head 와 Tail 앞에 비어있는 더미노드 2개를 생성하여 연산의 편의성을 확보
    List()
    {
        Head = new Node(0);
        Tail = new Node(0);
        Head->Next = Tail;
        Tail->Prev = Head;
    }

    // 리스트를 소멸시킬 때, 채워져 있는 노드가 존재하지 않을 때까지, 리스트의 노드들을 delete
    ~List()
    {
        Node* node = Head;
        while (node)
        {
            Node* DeleteNode = node;
            node = node->Next;
            delete DeleteNode;
        }
    }

    // Head에 삽입 연산을 수행, 더미 노드를 제외하고 기존의 Head 노드는 뒤로 밀림
    Node* AddAtHead(int InData)
    {
        Node* node = new Node(InData);
        Node* nextNode = Head->Next;

        node->Next = nextNode;
        nextNode->Prev = node;
        Head->Next = node;
        node->Prev = Head;

        return node;
    }

    // Tail에 삽입 연산을 수행, 더미 노드를 제외하고 기존의 Tail 노드는 앞으로 당겨짐
    Node* AddAtTail(int InData)
    {
        Node* node = new Node(InData);
        Node* prevNode = Tail->Prev;

        node->Prev = prevNode;
        prevNode->Next = node;
        Tail->Prev = node;
        node->Next = Tail;

        return node;
    }

    // 노드의 데이터를 가져오는 함수, 더미 노드는 포함하지 않음
    Node* GetNode(int index)
    {
        // 아직 리스트에 데이터를 넣지 않았을 때 == 오직 더미 노드만 존재하는 경우
        Node* node = Head->Next;
        if (node == Tail)
            return nullptr;
        
        // 리스트를 순회
        for (int i = 0; i < index; i++)
        {
            if (node == Tail->Prev)
                return nullptr;

            node = node->Next;
        }

        return node;
    }

    // 노드를 삽입하는 함수, 삽입하는 위치를 함께 넘겨줌
    void Insert(Node* PosNodeToAdd, int Data)
    {
        // 노드 간의 연결을 재구성
        Node* NewNode = new Node(Data);
        Node* PrevNode = PosNodeToAdd->Prev;

        PrevNode->Next = NewNode;
        NewNode->Prev = PrevNode;

        NewNode->Next = PosNodeToAdd;
        PosNodeToAdd->Prev = NewNode;
    }

    // 노드를 삭제하는 함수, 삭제하는 위치를 함께 넘겨줌
    Node* Remove(Node* NodeToDelete)
    {
        Node* PrevNode = NodeToDelete->Prev;
        Node* NextNode = NodeToDelete->Next;

        PrevNode->Next = NextNode;
        NextNode->Prev = PrevNode;

        delete NodeToDelete;
        return NextNode;
    }

    // 리스트를 출력 , 더미 데이터가 아닌 실제 데이터를 출력
    void Print()
    {
        Node* node = Head->Next;
        while (node != Tail)
        {
            cout << node->Data << " ";
            node = node->Next;
        }

        cout << "\n" << endl;
    }

private:
    Node* Head = nullptr;
    Node* Tail = nullptr;
};

 

양이 너무 방대해 스크린샷이 아닌 코드 블럭을 사용하였습니다.

 

이제 main함수에서 코드가 잘 동작하는지 확인해보겠습니다.

 

 

main 함수는 위와 같이 구성되었고 실행해보면

 

의도한것과 같이 잘 실행되는 것을 확인 할 수 있습니다.

 

리스트는 검색과 순회에 사용하기 보다는 삽입 + 삭제의 연산에 더 많은 이점을 갖고 있습니다.

이 점을 꼭 알아두셔서 적절한 개발 방향에 맞춰 사용해주시면 되겠습니다.

 

마지막으로, 연결 리스트에 관한 공식문서를 링크로 걸어두겠습니다.

참고하시는데 도움이 되길 바랍니다.

https://learn.microsoft.com/ko-kr/cpp/standard-library/list-class?view=msvc-170