[Data Structure] 단순 연결 리스트

연결 표현

순차 저장 방법은 임의의 원소에 접근하거나 스택이나 큐에 원소를 삽입하거나 삭제하는 것과 같은 작업에 적합하다.

하지만 삽입, 삭제가 자주 일어나는 경우 매우 불리한 구조가 된다. (예를 들어, 배열의 경우 원소 하나를 삭제하면 뒤에 있는 모든 원소를 앞으로 당겨야 함)

 

연결된(linked) 표현의 특징은 다음과 같음

• 각 원소들이 메모리의 어떤 곳에나 위치할 수 있음 (물리적으로 순차적인 위치에 존재할 필요 없음)
• 각 원소와 함께 그 다음 원소를 가리키는 주소 또는 위치를 저장함 (포인터 또는 링크라 함)

연결 리스트는 배열과 비교해 동적 크기 조정이 가능한 것이 장점

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

https://www.geeksforgeeks.org/singly-linked-list-tutorial/

단순 연결 리스트 또는 체인의 특징은 다음과 같음

• 정확히 하나의 포인터 필드를 가짐
• 삽입하거나 삭제할 때 리스트에 있는 다른 원소들을 이동시킬 필요가 없음

단순 연결 리스트의 삽입

빈 리스트에 노드를 삽입하는 경우, 바로 head로 설정해주면 된다.

https://www.geeksforgeeks.org/singly-linked-list-tutorial/

리스트의 맨 앞에 노드를 삽입하는 경우 새로 삽입할 노드의 포인터를 기존 head를 가리키게 한 후, 새로 삽입할 노드를 head로 만든다.

https://www.geeksforgeeks.org/singly-linked-list-tutorial/

리스트의 맨 마지막에 삽입하는 경우 새로운 노드의 포인터를 기존 마지막 노드의 포인터(NULL)를 가리키게 한 후, 기존 마지막 노드의 포인터가 새로운 노드를 가리키게 한다.

https://www.geeksforgeeks.org/singly-linked-list-tutorial/

리스트의 가운데 삽입하는 경우, 새로운 노드의 포인터를 뒷 노드의 포인터로 설정한 후, 뒷 노드의 포인터가 새로운 노드를 가리키게 한다.

단순 연결 리스트의 삭제

빈 리스트에서 노드를 삭제하려고 하는 경우 오류 메시지를 띄운다.

https://www.geeksforgeeks.org/singly-linked-list-tutorial/

head를 삭제하는 경우는 두 가지로 나눌 수 있다.

• head만 있는 경우, head를 삭제하고 nullptr를 가리키게 한다.
• head 뒤에 더 있는 경우, 현재 head를 삭제하고 그 다음 노드를 head로 만든다.

https://www.geeksforgeeks.org/singly-linked-list-tutorial/

https://www.geeksforgeeks.org/singly-linked-list-tutorial/

리스트 가운데 혹은 마지막에 있는 노드는 다음 과정으로 삭제한다.

• 삭제할 노드의 이전 노드의 포인터를 삭제할 노드의 포인터를 가리키게 함
• 삭제할 노드를 삭제함

단순 연결 리스트의 연결

만약 빈 리스트인 경우, 합칠 리스트의 head와 rear를 현재 리스트의 head와 rear로 설정한다.

그렇지 않은 경우, 현재 리스트의 rear의 포인터를 합칠 리스트의 head로 설정하고, rear를 합칠 리스트의 rear로 설정한다.

위의 과정이 끝나면 합쳐서 사라진 리스트의 head와 rear를 nullptr로 설정한다.

 

단순 연결 리스트 뒤집기

연결 리스트 뒤집기에는 현재, 이전, 다음 노드를 가리키는 세 개의 포인터가 필요하다.

http://blog.devgenius.io/reverse-a-linked-list-iterative-and-recursive-methods-c-e2399eb8f085?gi=8cc26437c7ac

현재 노드의 포인터를 이전 노드를 가리키게 하면서 계속 바꿔나가면 된다. 현재 노드를 가리키는 포인터가 NULL에 도착했다면, 이전 노드가 제일 마지막 노드에 있는 상태이므로 그 노드를 head로 설정해준다.

코드

템플릿을 사용해 단일 연결 리스트를 구현함

#include <iostream>

// 노드 클래스
template <typename T>
class Node 
{
public:
    Node(T data)
    {
        this->data = data;
    }

    T data;
    Node<T>* next = nullptr;
};

template <typename T>
class SinglyLinkedList
{
public:
    // 생성자
    SinglyLinkedList()
    {
        head = nullptr;
    }

    // 소멸자
    ~SinglyLinkedList()
    {
        Node<T>* currNode = head;
        Node<T>* prevNode = nullptr;

        // 모든 노드 삭제  
        while (currNode != nullptr)
        {
            prevNode = currNode;
            currNode = currNode->next;
            delete prevNode;
        }
    }

    Node<T>* GetHead()
    {
        return head;
    }

    Node<T>* GetRear()
    {
        return rear;
    }

    // 앞쪽 노드 삽입
    void InsertFront(Node<T>* node)
    {
        if (head)
        {
            node->next = head;
        }
        else // 빈 리스트인 경우 rear로 설정
        {
            rear = node;        
        }

        head = node; // 맨 앞에 삽입한 노드를 head로 설정
    }

    // 뒷쪽 노드 삽입
    void InsertRear(Node<T>* node)
    {
        if (head)
        {
            node->next = rear->next;
            rear->next = node;
        }
        else
        {
            head = node;
        }

        rear = node;
    }

    // value 값을 가지는 노드 삭제
    void Delete(T value)
    {
        if (head == nullptr) // 빈 리스트인 경우
        {
            std::cout << "List is empty\n";
        }
        else if (head->next == nullptr) // head만 있는 경우
        {
            if (head->data == value)
            {
                delete head;
                head = nullptr;
            }
            else
            {
                std::cout << "Cannot find node\n";
                return;
            }

        }
        else // 2개 이상 있는 경우
        {
            if (head->data == value) // head를 지우는 경우
            {
                Node<T>* temp = head;
                head = head->next; // head의 다음 노드를 새로운 head로 설정
                delete temp;
            }
            else
            {
                Node<T>* findNode = head;
                Node<T>* prevNode = nullptr;

                while (findNode != nullptr)
                {
                    if (findNode->data == value) break; // 찾은 경우 break
                    prevNode = findNode;
                    findNode = findNode->next;
                }

                if (findNode == nullptr)
                {
                    std::cout << "Cannot find node\n";
                    return;
                }

                if (findNode == rear) // 만약 지우려는 노드가 마지막 노드면
                {
                    rear = prevNode; // 마지막 노드를 prevNode로 설정
                }

                prevNode->next = findNode->next;
                delete findNode; // 노드 삭제
            }
        }
    }

    // Linked List 연결
    void Concatenate(SinglyLinkedList<T>* list)
    {
        if (head)
        {
            rear->next = list->head;
            rear = list->rear;
        }
        else
        {
            head = list->head;
            rear = list->rear;
        }

        // 합쳐져 사라진 리스트의 head와 rear를 nullptr로 설정
        list->head = nullptr;
        list->rear = nullptr;
    }

    // Linked List 뒤집기
    void Reverse()
    {
        Node<T>* currNode = head;
        Node<T>* prevNode = nullptr;
        Node<T>* nextNode = nullptr;

        rear = head; // 현재 head -> 뒤집힌 리스트의 rear

        while (currNode != nullptr)
        {
            nextNode = currNode->next;
            currNode->next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
        }

        head = prevNode; // 뒤집힌 리스트의 head를 설정
    }

    // Linked List 출력
    void Print()
    {
        Node<T>* currNode = head;

        while (currNode != nullptr)
        {
            std::cout << currNode->data << " ";
            currNode = currNode->next;
        }

        std::cout << "\n";
    }

private:
    Node<T>* head = nullptr;
    Node<T>* rear = head;
};