[Algorithm] 연결 리스트(LinkedList) 구현하기 (C++)

이중 연결 리스트

이번 포스팅에서는 더블 링크드 리스트라고도 하는 이중 연결 리스트에 대해서 알아보고 실제로 구현해보려고 합니다.이중 연결 리스트에는 prev, next라는 이전과 다음 노드를 가리키는 포인터를 가지고 있는 연결 리스트를 말합니다.

 

prev라는 이전 노드를 가리키는 포인터, next라는 다음 노드를 가리키는 포인터를 갖고 있기 때문에 양쪽으로 탐색이 가능하다는 장점이 있습니다. 이중 연결 리스트는 Head라는 처음을 의미하는 노드와 Tail이라는 마지막을 의미하는 노드를 가지고 있습니다. 이것을 시작과 끝으로 노드들을 추가하고 삭제하게 됩니다.

 

노드 추가

노드의 추가는 기존의 마지막 노드와 Tail과의 연결을 끊고 새로운 노드를 추가하여 기존 노드의 Next를 새로운 노드의 Prev에 연결하고 새로운 노드의 Next를 다음 Node의 Prev에 연결하는 과정을 통해 이루어집니다. 이중 연결리스트 이므로 반대방향으로도 연결해주시면 됩니다.

 

노드 삭제

노드의 삭제는 삭제할 노드를 삭제시키기전 이전 노드의 Next와 다음 노드의 Prev를 연결시켜주면 됩니다. 마찬가지로 이중 연결리스트 구조이기에 반대방향으로도 연결을 해주셔야 합니다.

 

이중 연결리스트 구현 (C++)

#pragma once
#include <assert.h> //예외처리

//Node
template <typename T>
class Node {

    template <typename T>
    friend class CList;
    
    template <typename T>
    friend class CIterator;
    
    template <typename T>
    friend class CIterator_Reverse;

private:
    Node() {
        pNext = nullptr;
        pPrev = nullptr;
    }
    
    ~Node() {}
    
    T _Data; //데이터를 저장할 변수
    Node<T>* pNext; //다음 노드의 주소를 저장할 변수
    Node<T>* pPrev; //이전 노드의 주소를 저장할 변수
};

//정방향 Iterator
template <typename T>
class CIterator {
    template <typename T>
    friend class CList;

public:
    CIterator() {
        pNode = nullptr;
    }
    
    ~CIterator() {}

private:
    typedef Node<T>* PNODE;
private:
    PNODE pNode;

public:

    //연산자 오버로딩
    void operator ++ () {
        //현재 노드를 다음 노드로 이동
        pNode = pNode->pNext;
    }
    
    void operator -- () {
        //현재 노드를 이전 노드로 이동
        pNode = pNode->pPrev;
    }

    T& operator * () {
        //현재의 데이터를 뽑음
        return pNode->_Data;
    }

    bool operator == (const CIterator<T>& other) {
        return pNode == other.pNode;
    }
    
    bool operator != (const CIterator<T>& other) {
        return pNode != other.pNode;
    }

};

//정방향 Iterator
template <typename T>
class CIterator_Reverse {
    template <typename T>
    friend class CList;

public:
    CIterator_Reverse() {
        pNode = nullptr;
    }
    
    ~CIterator_Reverse() {}

private:
    typedef Node<T>* PNODE;
private:
    PNODE pNode;

public:
    //연산자 오버로딩
    void operator ++ () {
        //현재 노드를 이전 노드로 이동
        pNode = pNode->pPrev;
    }
    
    void operator -- () {
        //현재 노드를 다음 노드로 이동
        pNode = pNode->pNext;
    }
    
    T& operator * () {
        //현재의 데이터를 뽑음
        return pNode->_Data;
    }
    
    bool operator == (const CIterator_Reverse<T>& other) {
        return pNode == other.pNode;
    }
    
    bool operator != (const CIterator_Reverse<T>& other) {
        return pNode != other.pNode;
    }
};

//LinkedList
template <typename T>
class CList
{
public:
    CList() {
        pHead = new NODE();
        pTail = new NODE();
        
        //처음에는 추가된 노드가 없으므로 Head의 다음으로
        //Tail를 지정하고 Tail의 이전으로 Head을 지정한다.
        pHead->pNext = pTail;
        pTail->pPrev = pHead;
        _size = 0;
    }
    
    ~CList() {
        clear();
        delete pHead;
        delete pTail;
    }
private:
    typedef Node<T> NODE;
    typedef Node<T>* PNODE;

public:
    typedef CIterator<T> iterator;
    typedef CIterator_Reverse<T> reverse_iterator;

private:
    PNODE pHead;
    PNODE pTail;
    int _size; //길이

public:
    void push_back(const T& data) {
        PNODE pNode = new NODE;
        pNode->_Data = data;
        
        //뒤에 추가를 해야 하므로 Tail의 이전 노드를 얻어온다.
        PNODE pPrev = pTail->pPrev;
        
        //얻어온 이전 노드와 Tail노드 사이에 새로 생성한 노드를 추가한다.
        pPrev->pNext = pNode;
        pNode->pPrev = pPrev;
        
        //Tail노드와 새로 생성한 노드를 연결한다.
        pNode->pNext = pTail;
        pTail->pPrev = pNode;
        
        ++_size; //길이 1증가
    }
    
    void push_front(const T& data) {
        PNODE pNode = new NODE;
        pNode->_Data = data;
        
        //Head의 Head의 다음 노드에 새로 생성한 노드를 추가한다.
        PNODE pNext = pHead->pNext;
        
        //새로 생성한 노드의 다음 노드로 Head의 다음 노드를 준다. 
        //Head의 다음 노드의 이전노드로 새로 생성한 노드를 준다.
        pNode->pNext = pNext;
        pNext->pPrev = pNode;
        
        //Head의 다음노드로 새로 생성한 노드를 준다.
        //새로 생성한 노드의 이전 노드로 Head을 준다.
        pHead->pNext = pNode;
        pNode->pPrev = pHead;
        
        ++_size;
    }
    
    //맨뒤 제거
    void pop_back() {
        //비어 있다면 에러
        if (empty()) {
            assert(false);
        }
        
        //가장 마지막 노드를 지워야하기에 Tail노드의 이전 노드를 얻어온다.
        PNODE pDeleteNode = pTail->pPrev;
        
        //지울 노드의 이전 노드를 얻어온다.
        PNODE pPriv = pDeleteNode->pPrev;
        
        //이전 노드의 다음으로 Tail를 주고 Tail의 이전으로 이전노드를 준다.
        pPriv->pNext = pTail;
        pTail->pPrev = pPriv;
        
        //노드를 지워준다.
        delete pDeleteNode;
        
        //사이즈를 1 감소시킨다.
        --_size;
    }
    
    //가장 앞 제거
    void pop_front() {
        if (empty()) {
            assert(false);
        }
        
        //지울 노드를 얻어온다.
        PNODE pDeleteNode = pHead->pNext;
        
        //지울 노드의 다음 노드를 얻어온다.
        PNODE pNext = pDeleteNode->pNext;
        
        //다음 노드의 이전으로 Head을 주고 Head의 다음으로 다음 노드를 준다.
        pNext->pPrev = pHead;
        pHead->pNext = pNext;
        
        //노드를 지워준다.
        delete pDeleteNode;
        
        //사이즈를 1 감소시킨다.
        --_size;
    }
    
    //가장 앞의 원소 리턴
    T front() const {
        if (empty()) {
             assert(false);
         }
         return pHead->pNext->mData;
    }
    
    //가장 뒤의 원소 리턴
    T back() const {
        if (empty()) {
            assert(false);
        }
        return pTail->pPrev->mData;
    }
    
    //Head과 Tail를 제외한 실제 추가한 노드의 삭제 기능
    void clear() {
        PNODE pNode = pHead->pNext;
        while (pNode != pTail) {
            //현재 노드의 다음 노드를 얻어온다.
            PNODE pNext = pNode->pNext;
            
            //현재 노드를 지워준다.
            delete pNode;
            
            //pNode에 다음 노드의 주소를 넣어준다.
            pNode = pNext;   
        }
        
        _size = 0;
        
        //Head과 Tail를 서로 연결해준다.
        pHead->pNext = pTail;
        pTail->pPrev = pHead;
    }
    
    //노드 삭제
    void remove(int index) {
    
        if (size() < index) {
            assert(false);
        }
        
        PNODE pDeleteNode = pHead;
        
        //지울노드로 이동
        for (int i = 0; i <= index; i++) {
            pDeleteNode = pDeleteNode->pNext;
        }
        
        //지울노드의 이전노드의 다음 노드를 지울노드의 다음노드로 준다.
        pDeleteNode->pPrev->pNext = pDeleteNode->pNext;
        
        //지울노드의 다음노드의 이전 노드를 지울노드의 이전노드로 준다.
        pDeleteNode->pNext->pPrev = pDeleteNode->pPrev;
        
        //노드를 지워준다.
        delete pDeleteNode;
        
        //사이즈를 1 감소시킨다.
        --_size;
    }
    
    //길이 반환
    int size() const {
        return _size;
    }
    
    //리스트가 비어있을 경우 true, 아닐경우 false를 반환한다.
    bool empty() const {
        return _size == 0;
    }
    
    T get(int index) const{
        if (size() < index) {
            assert(false);
        }
        
        PNODE temp = pHead;
        
        for (int i = 0; i <= index; i++) {
            temp = temp->pNext;
        }
        return temp->_Data;
    }
    
    //Begin() 함수는 추가된 첫번째 노드의 주소를 가지고 있는 iterator를 반환
    iterator Begin() const {
        iterator iter;
        iter.pNode = pHead->pNext;
        return iter;
    }
    
    //End() 함수는 Tail 노드를 가지고 있는 iterator를 반환한다.
    iterator End() const {
        iterator iter;
        iter.pNode = pTail;
        return iter;
    }
    
    //rBegin()은 마지막에 추가된 노드를 가지고 있는 reverse_iterator를 반환
    reverse_iterator rBegin() const {
        reverse_iterator iter;
        iter.pNode = pTail->pPrev;
        return iter;
    }
    
    //rEnd()은 Head노드를 가지고 있는 reverse_iterator를 반환한다.
    reverse_iterator rEnd() const {
        reverse_iterator iter;
        iter.pNode = pHead;
        return iter;
    }
    
    iterator erase(iterator iter) {
        //삭제할 이터레이터의 노드저장
        PNODE pNode = iter.pNode;
        //앞뒤 노드를 서로 이어줌
        pNode->pPrev->pNext = pNode->pNext;
        pNode->pNext->pPrev = pNode->pPrev;
        
        //리턴할 이터레이터를 다음노드로
        iterator riter;
        riter.pNode = pNode->pNext;
        
        //노드 삭제
        delete pNode;
        --_size;

        return riter;
    }
};