[자료구조] 연결 리스트 (Linked List)

연결 리스트 (Linked List)

 

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는

방식으로 데이터를 저장하는 자료 구조이다.

 

이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다.
연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다.

 

그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

 

단일 연결 리스트(Single Linked List)

 

 

먼저 리스트를 이해하기 위해서는 포인터를 이해해야합니다.

처음에 포인터에 대한 이해가 없다면 아주 난해할 수 있습니다.

 

쉽게 단일 연결 리스트는 한줄로 쭉 이어진 노드에 다음 포인터가 연결된 구조로 되어 있습니다.

처음 노드는 머리(HEAD)라고 하고 맨끝에 노드 (다음 포인터가 null인 노드)는 꼬리(TAIL)이라고 합니다.

 

[Node Class]

class Node
{
public :
    
    int data;
    Node* next;
 
    Node() : data(0), next(nullptr) {};
    Node(int _data, Node* const _next)
        : data(_data), next(_next) {};
};

 

[LinkedList Class]

class LinkedList
{
private :
 
    Node* head;
 
public :
 
    LinkedList() : head(nullptr) {};
    ~LinkedList(){};
    
    Node* GetTailNode()
    {
        Node* tailNode = head;
        
        if (tailNode == nullptr)
        {
            cout << "리스트가 비어있습니다." << endl;
            return nullptr;
        }
 
        while (tailNode->next != nullptr)
        {
            tailNode = tailNode->next;
        }
 
        return tailNode;
    }
 
    void Inset(int _data)
    {
        Node* newNode = new Node();
        newNode->data = _data;
 
        if (nullptr == head)
        {
            head = newNode;
        }
        else
        {
            Node* node = GetTailNode();
            node->next = newNode;
        }
    }
 
    void DeleteData(int _data)
    {
        Node* target = head;
        Node* preNode = nullptr;
 
        while (target != nullptr)
        {
            if (target->data == _data)
            {
                if (preNode != nullptr)
                {
                    preNode->next = target->next;
                }
                else
                {
                    head = target->next;
                }
 
                delete(target);
                target = nullptr;
                return;
            }
 
            preNode = target;
            target = target->next;            
        }
    }
 
    void DeleteAt(int _index)
    {
        Node* target = head;
        Node* preNode = nullptr;
        int index = 0;
 
        while (index < _index)
        {
            if (target == nullptr)
                break;
 
            preNode = target;
            target = target->next;
            index++;
        }
 
        if (index == _index)
        {
            if (preNode != nullptr)
            {
                preNode->next = target->next;
            }
            else
            {
                head = target->next;
            }
 
            delete(target);
            target = nullptr;
        }
        
        if (index < _index || _index < 0)
        {
            cout << "찾는 위치가 리스트의 범위를 넘어섰습니다." << endl;
        }
    }
 
    void ShowData()
    {
        Node* target = head;
 
        cout << "--- 리스트 출력 ---" << endl;
 
        while (target != nullptr)
        {
            cout << target->data << "->";
            target = target->next;
        }
 
        cout << "NULL" << endl << "--- 출력 완료 ---" << endl << endl;
    }
 
};

[실행]

void main()
{
    LinkedList linked_List;
 
    linked_List.Inset(10);
    linked_List.ShowData();
 
    linked_List.Inset(20);
    linked_List.Inset(30);
    linked_List.Inset(40);
    linked_List.Inset(50);
    linked_List.ShowData();
 
    linked_List.DeleteData(40);
    linked_List.ShowData();
 
    linked_List.DeleteAt(2);
    linked_List.ShowData();
 
    linked_List.DeleteAt(12);
}

 

[결과]

 

이중 연결 리스트 (Double Linked List)

 

 

단일 연결 리스트와 크게 다르지 않고 달라진 점은 단일 연결 리스트에는 다음 노드의 포인터 밖에 없지만 이중 연결 리스트에는 이전 노드의 포인터가 추가된 점이 다릅니다.

 

이중으로 연결되어 있기 때문에 양방향으로 탐색이 가능합니다. 이것은 이중 연결 리스트에 가장 큰 장점입니다.

 

작성한 코드에서는 삽입 시에만 크기를 비교해서 꼬리 부분부터 찾을 것인지 머리 부분부터 찾을 것 인지를 결정하도록 했습니다.

 

[Node Class]

class Node
{
public :
    
    int data;
    Node* prev;
    Node* next;
 
    Node() : data(0), prev(nullptr), next(nullptr) {};
};

 

[LinkedList Class]

class LinkedList
{
private :
 
    Node* head;
    Node* tail;
    int dataSize = 0;
 
    void InsertLeft(int _data, Node *_insertNode)
    {
        if (_insertNode == head)
            return;
 
        Node* node = new Node();
        node->data = _data;
 
        _insertNode->prev->next = node;
        node->prev = _insertNode->prev;
 
        _insertNode->prev = node;
        node->next = _insertNode;
        dataSize++;
    }
 
    bool DeleteNode(Node* _deleteNode)
    {
        if (_deleteNode == head && _deleteNode == tail)
            return false;
 
        _deleteNode->prev->next = _deleteNode->next;
        _deleteNode->next->prev = _deleteNode->prev;
 
        delete(_deleteNode);
        _deleteNode = nullptr;
 
        dataSize--;
        return true;
    }
 
    Node* FindNodeFromFront(int _index)
    {
        if (Empty() == true)
            return nullptr;
 
        Node* target = head->next;
        int index = 0;
 
        while (target != tail)
        {
            if (index == _index)
                break;
 
            target = target->next;
            index++;
        }
 
        return target;
    }
 
    Node* FindNodeFromEnd(int _index)
    {
        if (Empty() == true)
            return nullptr;
 
        Node* target = tail->prev;
        int index = 0;
 
        while (target != head)
        {
            if (index == _index)
                break;
 
            target = target->prev;
            index++;
        }
 
        return target;
    }
 
public :
 
    LinkedList() : head(nullptr) 
    {
        tail = new Node();
        head = new Node();
 
        head->prev = head;
        head->next = tail;
        
        tail->prev = head;
        tail->next = tail;    
    };
    
    ~LinkedList(){};
 
    void Insert(int _data)
    {        
        InsertLeft(_data, tail);
    }
 
    int GetSize()
    {
        return dataSize;
    }
    
    bool Empty()
    {
        return (head->next == tail);
    }
 
    void InsertAt(int _index , int _data)
    {
        Node* findNode = nullptr;
 
        int index = dataSize - 1 * 0.5f;
 
        if (_index <= index)
        {
            findNode = FindNodeFromFront(_index);
        }
        else if (_index > index)
        {
            findNode = FindNodeFromEnd(_index - index);
        }        
 
        if (findNode == nullptr)
        {
            cout << "특정 인덱스 " << _index << 
                " 번째에 노드를 추가 할 수 없습니다." << endl;
            return;
        }
 
        InsertLeft(_data, findNode);
    }
 
    void RemoveData(int _data)
    {
        Node* target = head->next;
        
        while (target != tail)
        {
            if (target->data == _data)
                break;
 
            target = target->next;
        }
 
        if (DeleteNode(target) == false)
            cout << _data << " 데이터 삭제에 실패하였습니다." << endl;
    }
 
 
    void ShowData()
    {
        Node* node = head->next;
 
        cout << " Head -> ";
 
        while (node != tail)
        {
            cout << node->data << " -> ";
            node = node->next;            
        }
 
        cout << " Tail" << endl << endl;
    }
};

 

[실행]

void main()
{
    LinkedList linked_List;
 
    cout << std::boolalpha;
    cout << "리스트가 비어있는지 여부 = " << 
        linked_List.Empty() << endl << endl;
 
    linked_List.Insert(10);
    linked_List.Insert(20);
    linked_List.Insert(30);
    linked_List.Insert(40);
 
    linked_List.ShowData();
 
    cout << "리스트 크기 = " <<
        linked_List.GetSize() << endl << endl;
 
    linked_List.RemoveData(20);
 
    linked_List.ShowData();
 
    linked_List.InsertAt(1 , 15);
    linked_List.InsertAt(3, 55);
 
    linked_List.ShowData();
 
    cout << "리스트 크기 = " << 
        linked_List.GetSize() << endl << endl;
 
    cout << std::boolalpha;
    cout << "리스트가 비어있는지 여부 = " << 
        linked_List.Empty() << endl << endl;
}

 

[결과]

 

원형 연결 리스트

 

 

원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조입니다.