더블 링크드 리스트

서론

템플릿은 역시! 짱짱맨! 메인을 통으로 넣었다!

코드

#include <cstring>
#include <iostream>
using namespace std;
 
template<typename T>
struct NODE{
    //< 요소
    T element;
    //< 이전 노드
    NODE<T> *prev;
    //< 다음 노드
    NODE<T> *next;
};
 
template<typename T>
class DoubleLinkedList
{
public:
    //< 생성자
    DoubleLinkedList(void) : head(NULL), tail(NULL), m_size(0)
    { }
    //< 소멸자
    ~DoubleLinkedList(void) { }
 
    //< 인터페이스 함수
    //< 이니셜라이져
    void initList(void);
    //< 릴리즈
    void releaseList(void);
    
    //< 머리에 넣기
    void push_front(const T& element);
    //< 꼬리에 넣기
    void push_back(const T& element);
    //< 머리 삭제(not Dummy)
    void pop_front(void);
    //< 꼬리 삭제(not Dummy)
    void pop_back(void);
    //< 클리어
    void clear(void);
    //< 현재 리스트 출력
    void printPopura(void);
 
    //< 비었니?
    inline bool empty(void) { return m_size <= 0; }
    //< 사이즈
    inline size_t size() { return m_size; }
 
private:
    //< 편의
    //< 새로운 노드 생성
    NODE<T> *getNewNode(const T &element);
    //< 노드 삭제
    void deleteNode(NODE<T> *delNode);
 
    //< 더미노드들
    //< 머리 노드
    NODE<T> *head;
    //< 꼬리 노드
    NODE<T> *tail;
    //< 노드 길이
    size_t m_size;
};
 
 
void main (void )
{
    //< int 테스트
    DoubleLinkedList<int> intList;
 
    //< 초기화
    intList.initList();
 
    //< 앞에 값 넣기
    intList.push_front(10);
    intList.push_front(20);
    intList.push_front(30);
    intList.push_front(40);
    intList.push_front(50);
    intList.printPopura();
 
    //< 뒤에 값 넣기
    intList.push_back(60);
    intList.push_back(70);
    intList.push_back(80);
    intList.push_back(90);
    intList.push_back(100);
    intList.printPopura();
 
    //< 값 빼기
    intList.pop_back();
    intList.printPopura();
    intList.pop_front();
    intList.printPopura();
 
    //< 클리어
    intList.clear();
    intList.printPopura();
 
    //< char 테스트
    DoubleLinkedList<char> charList;
 
    //< 앞에 값 넣기
    charList.initList();
    charList.push_front('L');
    charList.push_front('O');
    charList.push_front('V');
    charList.push_front('E');
    charList.push_front(' ');
    charList.printPopura();
 
    //< 뒤에 값 넣기
    charList.push_back('P');
    charList.push_back('A');
    charList.push_back('I');
    charList.push_back('N');
    charList.push_back('!');
    charList.printPopura();
 
    //< 값 빼기
    charList.pop_back();
    charList.printPopura();
    charList.pop_front();
    charList.printPopura();
 
    //< 클리어
    charList.clear();
    charList.printPopura();
 
    //< 문자열 테스트
    DoubleLinkedList<char*> stringList;
 
    //< 앞에 값 넣기
    stringList.initList();
    stringList.push_front("ALICE");
    stringList.push_front("POPURA");
    stringList.push_front("ONODERA");
    stringList.push_front("AKARI");
    stringList.push_front("SENJOGAHARA");
    stringList.printPopura();
    
    //< 뒤에 값 넣기
    stringList.push_back("누렁이");
    stringList.push_back("꼬모");
    stringList.push_back("뽀삐");
    stringList.push_back("초롱이");
    stringList.push_back("달순이");
    stringList.printPopura();
    
    //< 값 빼기
    stringList.pop_back();
    stringList.printPopura();
    stringList.pop_front();
    stringList.printPopura();
    
    //< 클리어
    stringList.clear();
    stringList.printPopura();
    
    //< 릴리스
    intList.releaseList();
    charList.releaseList();
    stringList.releaseList();
 
}
 
//< 인터페이스 함수
//< 이니셜라이져
template <typename T>
void DoubleLinkedList<T>::initList(void)
{
    //< 둘다 할당
    if( NULL != head)
    {
        clear( );
    }
    //< 할당
    head = new NODE<T>;
    tail = new NODE<T>;
 
    //< 연결
    head->prev = NULL;
    head->next = tail;
 
    tail->next = NULL;
    tail->prev = head;
 
    m_size = 0;
}
 
//< 레리즈!!!
template <typename T>
void DoubleLinkedList<T>::releaseList(void)
{
    if (head->next != NULL)
    {
        clear();
    }
    delete head;
    head = NULL;
    delete tail;
    tail = NULL;
}
   
//< 머리에 넣기
template <typename T>
void DoubleLinkedList<T>::push_front(const T& element)
{
       NODE<T> *newNode = getNewNode( element );
    //< 연결
    //< 새로운 노드 연결 완료
    newNode->next = head->next;
    newNode->prev = head;
 
    //< 헤더연결
    head->next->prev = newNode;
    head->next = newNode;
 
    //< 추가
    m_size++;
}
//< 꼬리에 넣기
template <typename T>
void DoubleLinkedList<T>::push_back(const T& element)
{
    NODE<T>* newNode = getNewNode( element );
    //< 연결
    //< 새로운 노드 연결 완료
    newNode->next = tail;
    newNode->prev = tail->prev;
 
    //< 꼬리연결
    tail->prev->next = newNode;
    tail->prev = newNode;
 
    //< 추가
    m_size++;
}
//< 머리 삭제(not Dummy)
template <typename T>
void DoubleLinkedList<T>::pop_front(void)
{
    if( head->next != tail )
    {
        NODE<T> *delNode = head->next;
 
        //< 헤더연결
        deleteNode(delNode);
 
        //< 감소
        m_size--;
    }
}
 
//< 꼬리 삭제(not Dummy)
template <typename T>
void DoubleLinkedList<T>::pop_back(void)
{
    if( tail->prev != head )
    {
        NODE<T>* delNode = tail->prev;
        deleteNode(delNode);
         //< 감소
        m_size--;
    }
}
//< 클리어
template <typename T>
void DoubleLinkedList<T>::clear(void)
{
    while (tail != head->next)
    {
        pop_front();
    }
    m_size = 0;
   
}
//< 현재 리스트 출력
template <typename T>
void DoubleLinkedList<T>::printPopura(void)
{
    //< 대신 뛸 임시 노드 포인터, 헤드 더미노드 다음을 가리킨다.
    NODE<T> * tempNode = head->next;
    cout<<"============"<<endl;
    cout<<"노드 수 = "<<m_size<<endl;
    while (tail != tempNode)
    {
        cout<<tempNode->element<<endl;
        tempNode = tempNode->next;
    }
    cout<<"============"<<endl;
}
    
//< 새로운 노드 생성
template <typename T>
NODE<T>* DoubleLinkedList<T>::getNewNode(const T &element)
{
    //< 새 노드 생성
    NODE<T> *newNode = new NODE<T>;
    //< 앨리먼트의 값 복사
    //memmove_s(&newNode->element, sizeof(T), &element, sizeof(T));
    newNode->element = element;
    //< next, prev 널로 초기화
    newNode->next = NULL;
    newNode->prev = NULL;
 
    return newNode;
}
 
template <typename T>
void DoubleLinkedList<T>::deleteNode(NODE<T> *delNode)
{
    //< 지울 노드의 다음의 이전을 지울 노드 이전으로
    delNode->next->prev = delNode->prev;
    //< 지울 노드의 이전의 다음을 지울 노드 다음으로
    delNode->prev->next = delNode->next;
    
    //< 노드 삭제
    delete delNode;
    delNode = NULL;
}

결과