[C++/템플릿으로 만드는 자료구조] 이중연결원형리스트(Doubly Circular Linked List)

이중연결원형 리스트의 템플릿화된 소스입니다. 사용시엔 Iostream을 인클루드 시켜야합니다.

template<typename Type>
class Node
{
public:
    Type VALUE;                
    Node<Type> *Before;        
    Node<Type> *After;        
};
 
template<typename Type>
class List
{
private:
    Node<Type> *header = NULL;    
    Node<Type> *tailer = NULL;    
 
public:
    List();
    ~List();
    void Add_First(Type Item);
    void Add(int Position, Type Item);
    void Push_Back(Type Item);
    Type Delete(int Position);
    void Replace(int Position, Type Item);
    void Find(Type Item);
    void Find_R(Type item);
    void Get_Entry(int Position);
    void Get_Entry_R(int Position);
    void Get_Length();
    bool Is_Empty();
    void Printing();
    void Printing_R();
};
 
template<typename Type>
List<Type>::List()
{
    this->header = NULL;
    this->tailer = NULL;
}
 
template<typename Type>
List<Type>::~List()
{
 
}
 
template<typename Type>
void List<Type>::Add_First(Type Item)
{
    Node<Type> *New = new Node<Type>;        
    New->VALUE = Item;                        
    if (this->header == NULL)// 리스트가 비었을 때의 경우
    {
        this->tailer = New;                    
        this->tailer->After = New;            
        this->tailer->Before = New;            
        New->After = this->tailer;            
        New->Before = this->tailer;            
        this->header = New;                    
        return;
    }
    if (this->header != NULL)//리스트에 값이 있을 경우
    {
        New->Before = this->header->Before;    
        this->tailer->After = New;            
        New->After = this->header;            
        this->header->Before = New;            
        this->header = New;                    
        return;
    }
}
 
template<typename Type>
void List<Type>::Add(int Position, Type Item)
{
    if (Position == 1 || this->header == NULL || this->tailer == NULL)    //1번째의 경우와 그 이외의 경우의 연산 차이가 있으므로 1번 쨰 경우를 분리
    {
        this->Add_First(Item);
        return;
    }
    Node<Type> *Cur = this->header;
    Node<Type> *Temp = NULL;
    Node<Type> *New = new Node<Type>;
    int pos = 1;                                                        //위치 한계값 설정을 위해 지정
    if (this->header == this->tailer)
    {
        this->header->After = New;
        this->header->Before = New;
        New->Before = this->header;
        New->After = this->header;
        this->tailer = New;
        New->VALUE = Item;
        return;
    }
    if (Position == 2)                                                    //시작시에 커서 이동을 해야하나 이전 것을 체크해줘야 하기 때문에 2번쨰와 그 이후를 분리
    {
        Temp = Cur;
        Cur = Cur->After;
        New->VALUE = Item;
        New->Before = Cur->Before;
        New->After = Temp->After;
        Temp->After = New;
        New->After = Cur;
        return;
    }
    if (Position == 3 && (this->header->After == this->tailer))
    {
        tailer->After = New;
        New->Before = this->tailer;
        New->After = this->header;
        this->header->Before = New;
        New->VALUE = Item;
        this->tailer = New;
        return;
    }
    if (Position == 3 && (this->header->After->After == this->tailer))
    {
        New->Before = this->tailer->Before;
        New->After = New->Before->After;
        New->Before->After = New;
        this->tailer->Before = New;
        New->VALUE = Item;
        return;
    }
    if (Position == 3)
    {
        New->After = this->header->After->After;
        New->Before = this->header->After;
        this->header->After->After = New;
        New->After->Before = New;
        New->VALUE = Item;
        return;
    }
    Cur = Cur->After;
    pos++;
    while (pos != Position - 1)
    {
        if (Cur->After == this->header)
        {
            std::cout << "Cannot Create Node in" << Position << "(th) Node" << std::endl;
            return;
        }
        pos++;
        Cur = Cur->After;
    }
    if (Cur == this->header)
    {
        New->After = this->header;
        New->Before = this->tailer;
        this->tailer->After = New;
        this->header->Before = New;
        New->VALUE = Item;
        return;
    }
    New->VALUE = Item;
    New->After = Cur->After;
    New->Before = Cur;
    New->After->Before = New;
    Cur->After = New;
}
 
template<typename Type>
void List<Type>::Push_Back(Type Item)
{
    Node<Type> *New = new Node<Type>;
    Node<Type> *Cur = this->tailer;
    if (this->header == NULL)
    {
        Add_First(Item);
        return;
    }
    New->After = this->tailer->After;
    New->Before = this->header->Before;
    this->header->Before = New;
    this->tailer->After = New;
    New->VALUE = Item;
}
 
template<typename Type>
Type List<Type>::Delete(int Position)
{
    int pos = 1;
    int Return_Value;
    Node<Type> *Temp = NULL;
    Node<Type> *Cur = this->header;
    while (pos < Position)
    {
        if (pos == Position - 1)
            Temp = Cur;
        Cur = Cur->After;
        pos++;
    }
    Return_Value = Cur->VALUE;
    Cur->After->Before = Cur->Before;
    Cur->Before->After = Cur->After;
    delete(Cur);
    return Return_Value;
}
 
template<typename Type>
void List<Type>::Replace(int Position, Type Item)
{
    int pos = 1;
    Node<Type> *Cur = this->header;
    while (pos < Position)
    {
        Cur = Cur->After;
        pos++;
    }
    Cur->VALUE = Item;
}
 
template<typename Type>
void List<Type>::Find(Type Item)
{
    Node<Type> *Cur = this->header;
    int i = 1;
    if (Cur->VALUE == Item)
        std::cout << " Value" << Item << " in " << i << " (th) node" << std::endl;
    i++;
    Cur = Cur->After;
    while (Cur != this->header)
    {
        if (Cur->VALUE == Item)
            std::cout << " Value" << Item << " in " << i << " (th) node" << std::endl;
        i++;
        Cur = Cur->After;
    }
    if (Cur == NULL)
        std::cout << Item << " is not in this List" << std::endl;
}
 
template<typename Type>
void List<Type>::Find_R(Type Item)
{
    Node<Type> *Cur = this->tailer;
    int i = 1;
    if (Cur->VALUE == Item)
        std::cout << "Value " << Item << " is in " << i << " (th) Node" << std::endl;
    i++;
    Cur = Cur->Before;
    while (Cur != this->header)
    {
        if (Cur->VALUE == Item)
            std::cout << "Value " << Item << " is in " << i << " (th) Node" << std::endl;
        i++;
        Cur = Cur->Before;
    }
}
 
template<typename Type>
void List<Type>::Get_Entry(int Position)
{
    int pos = 1;
    Node<Type> *Cur = this->header;
    if (Position == 1)
    {
        std::cout << Cur->VALUE << " is in " << Position << "(th) Node" << std::endl;
        return;
    }
    Cur = Cur->After;
    pos++;
    while (pos < Position)
    {
        if (Cur == NULL)
        {
            std::cout << "No Node" << std::endl;
            return;
        }
        Cur = Cur->After;
        pos++;
    }
    std::cout << Cur->VALUE << " is in " << Position << "(th) Node" << std::endl;
}
 
 
template<typename Type>
void List<Type>::Get_Entry_R(int Position)
{
    int pos = 1;
    Node<Type> *Cur = this->header;
    if (Position == 1)
    {
        std::cout << "(Reverse) " << Cur->VALUE << " is in " << Position << "(th) Node" << std::endl;
        return;
    }
    Cur = Cur->Before;
    pos++;
    while (pos < Position)
    {
        if (Cur == NULL)
        {
            std::cout << "No Node" << std::endl;
            return;
        }
        Cur = Cur->Before;
        pos++;
    }
    std::cout << "(Reverse) " << Cur->VALUE << " is in " << Position << "(th) Node" << std::endl;
}
 
template<typename Type>
void List<Type>::Get_Length()
{
    Node<Type> *Cur = this->header;
    int i = 1;
    i++;
    Cur = Cur->After;
    while (Cur != this->header)
    {
        i++;
        Cur = Cur->After;
    }
    std::cout << "This List has " << i << "nodes" << std::endl;
}
 
template<typename Type>
bool List<Type>::Is_Empty()
{
    if (this->header == NULL)
    {
        std::cout << "List is empty" << std::endl;
        return true;
    }
    std::cout << "List is not empty" << std::endl;
    return false;
}
 
template<typename Type>
void List<Type>::Printing()
{
    if (this->Is_Empty())
    {
        std::cout << "There is No Node to display" << std::endl;
        return;
    }
    Node<Type> *Cur = this->header;
    std::cout << Cur->VALUE << " -> ";
    Cur = Cur->After;
    while (Cur != this->header)
    {
        std::cout << Cur->VALUE << " -> ";
        Cur = Cur->After;
    }
    std::cout << std::endl;
}
 
template<typename Type>
void List<Type>::Printing_R()
{
    if (this->Is_Empty())
    {
        std::cout << "There is No Node to display" << std::endl;
        return;
    }
    Node<Type> *Cur = this;
    std::cout << Cur->VALUE << " -> ";
    Cur = Cur->Before;
    while (Cur != this->header)
    {
        std::cout << Cur->VALUE << " -> ";
        Cur = Cur->Before;
    }
    std::cout << std::endl;
}

이중연결원형리스트는 STL에서 List 헤더를 이용하여 이용하게됩니다.

같이보기

2015/11/07 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List)- 이중 원형 연결 리스트