c++로 양뱡향 연결 리스트 구현하기

클래스, 템플릿을 이용해서 양뱡향 연결 리스트를 구현해보았습니다.

주석이 많지 않아 친절하지 않습니다.

참고로 DLL은 Double Linked List의 줄임말입니다.

#include <iostream>
using namespace std;

template <typename T>
class Node{
public:
    T value;
    Node<T>* prev = nullptr;
    Node<T>* next = nullptr;

    Node(T val){
        value = val;
        prev = nullptr;
        next = nullptr;
    }
};


template<typename T>
class DLL{
private:
    Node<T>* begin_node = nullptr;
    Node<T>* end_node = nullptr;
public:

    void push_front(T val){
        if(begin_node == nullptr){
            begin_node = new Node<T>(val);
            end_node = begin_node;
            return;
        }

        Node<T>* tmp_node = new Node<T>(val);
        begin_node -> prev = tmp_node;
        tmp_node -> next = begin_node;
        begin_node = tmp_node;
    }

    void push_back(T val){
        if(end_node == nullptr){
            end_node = new Node<T>(val);
            begin_node = end_node;
            return;
        }

        Node<T>* tmp_node = new Node<T>(val);
        end_node -> next = tmp_node;
        tmp_node -> prev = end_node;
        end_node = tmp_node;
    }

    void pop_back(){
        // 리스트가 비어있는 경우
        if(end_node == nullptr){
            cout << "list is emtpy!" << endl;
            return;
        }

        // 안에 값이 하나 밖에 없을 경우
        if(begin_node == end_node){
            delete begin_node;
            begin_node = nullptr;
            end_node = nullptr;
            return;
        }

        Node<T>* tmp_node = end_node;
        end_node = end_node->prev;
        delete tmp_node;
        end_node->next = nullptr;
    }

    void pop_front(){
        // 리스트가 비어있는 경우
        if(begin_node == nullptr){
            cout << "list is emtpy!" << endl;
            return;
        }

        // 안에 값이 하나 밖에 없을 경우
        if(begin_node == end_node){
            delete begin_node;
            begin_node = nullptr;
            end_node = nullptr;
            return;
        }

        Node<T>* tmp_node = begin_node;
        begin_node = begin_node->next;
        delete tmp_node;
        begin_node->prev = nullptr;
    }
    
    // 리스트의 사이즈를 반환하는 함수
    int size(){
        if(begin_node == nullptr)
            return 0;

        Node<T>* curr_node = begin_node;
        int cnt = 1;
        while(curr_node->next != nullptr){
            curr_node = curr_node->next;
            cnt++;
        }
        return cnt;
    }

    // 특정 값을 찾아 인덱스를 반환하는 함수
    // 값이 없다면 -1, 리스트가 비어있어도 -1 반환
    int find_by_val(T val){
        if(begin_node == nullptr){
            return -1;
        }
        Node<T>* curr_node = begin_node;
        int index = 0;
        while(curr_node->value != val){
            if(curr_node == end_node){
                index = -1;
                break;
            }
            index++;
            curr_node = curr_node->next;
        }
        return index;
    }

    // 특정 인덱스 값의 위치를 찾아 안의 값을 반환하는 함수
    int search_by_index(int idx){
        if(begin_node == nullptr){
            cout << "list is emtpy!" << endl;
            return -1;
        }

        if(idx >= this->size()){
            cout << "can't search because entered index is bigger than list!" << endl;
            return -1;
        }

        Node<T>* curr_node = begin_node;
        for(int i = 0; i < idx; i++){
            curr_node = curr_node->next;
        }
        return curr_node->value;
    }

    // 리스트 내 요소들을 출력하는 함수
    void print_DLL(){
        int size_of_DLL = this->size();
        Node<T>* curr_node = begin_node;
        if(size_of_DLL == 0){
            cout << "there is nothing!" << endl;
            return;
        }
        for(int i = 0; i < size_of_DLL; i++){
            cout << curr_node->value << " ";
            curr_node = curr_node->next;
        }
        cout << endl;
    }

    //리스트를 비우는 함수
    void clear(){
        Node<T>* curr_node = begin_node;
        while(curr_node != nullptr){
            Node<T>* next_node = curr_node->next;
            delete curr_node;
            curr_node = next_node;
        }

        begin_node = nullptr;
        end_node = nullptr;
    }

    bool isEmtpy(){
        return !(this->size());
    }

    // 특정 값을 찾아 제거. 앞에서부터 탐지
    void remove(T val){
        Node<T>* curr_node = begin_node;
        while(curr_node != nullptr && curr_node->value != val){
            curr_node = curr_node->next;
        }
        if(curr_node == nullptr){
            cout << "the value does not exist!" << endl;
            return;
        }
        
        if(curr_node == end_node){
            this->pop_back();
        }
        else if(curr_node == begin_node){
            this->pop_front();
        }
        // 중간 노드를 삭제할 경우
        else{
            Node<T>* prev_node = curr_node->prev;
            Node<T>* next_node = curr_node->next;
            prev_node->next = next_node;
            next_node->prev = prev_node;
            delete curr_node;
        } 
    }

    // 두 리스트를 바꿈.
    void swap_dll(DLL<T>& target_dll){
        swap(this->begin_node, target_dll.begin_node);
        swap(this->end_node, target_dll.end_node);
    }

    // 중복된 값을 모두 삭제하는 함수
    void remove_Duplicate(){
        int size_of_list = this->size();
        DLL<T> removed_dll;
        for(int i = 0; i < size_of_list;i++){
            int val = this->search_by_index(i);
            if(removed_dll.find_by_val(val) == -1){
                removed_dll.push_back(val);
            }
        }
        this->swap_dll(removed_dll);
    }
};

int main(void){
    DLL<int> dll;
    
    while(1){
        cout << "===================================" << endl;
        cout << "enter alphabet  you want..." << endl;
        cout << "a. end this program" << endl;
        cout << "b. add value at front of list" << endl;
        cout << "c. add value at back of list" << endl;
        cout << "d. remove back of list" << endl;
        cout << "e. remove front of list" << endl;
        cout << "f. print size of list" << endl;
        cout << "g. find value's index(search from the front)" << endl;
        cout << "h. print list[index]" << endl;
        cout << "i. print elements of list" << endl;
        cout << "j. clear the list" << endl;
        cout << "k. check if list is empty" << endl;
        cout << "l. remove value(search from the front)" << endl;
        cout << "m. remove all duplicates" << endl;
        cout << "===================================" << endl;
        char alpha;
        cin >> alpha;
        
        if(alpha < 'a' || alpha > 'm'){
            cout << "You must enter an alphabet between 'a' and 'm'" << endl;
            continue;
        }
        
        if(alpha == 'a')
            break;
        if(alpha == 'b'){
            int tmp;
            cout << "enter number you want to add front of list : ";
            cin >> tmp;
            dll.push_front(tmp);
            cout << "complete!" << endl;
        }
        if(alpha == 'c'){
            int tmp;
            cout << "enter number you want to add back of list : ";
            cin >> tmp;
            dll.push_back(tmp);
            cout << "complete!" << endl;
        }
        if(alpha == 'd'){
            dll.pop_back();
            cout << "complete!" << endl;
        }
        if(alpha == 'e'){
            dll.pop_front();
            cout << "complete!" << endl;
        }
        if(alpha == 'f'){
            cout << "size of list : ";
            cout << dll.size() << endl;
        }
        if(alpha == 'g'){
            int tmp;
            cout << "enter number you want to find : ";
            cin >> tmp;
            cout << "index of the value(search from front) : ";
            cout << dll.find_by_val(tmp) << endl;
        }
        if(alpha == 'h'){
            int tmp;
            cout << "enter index : ";
            cin >> tmp;
            cout << "index of the value(search from front) : ";
            cout << dll.search_by_index(tmp) << endl;
        }
        if(alpha == 'i'){
            cout << "current elements of list : ";
            dll.print_DLL();
        }
        if(alpha == 'j'){
            dll.clear();
            cout << "complete!" << endl;
        }
        if(alpha == 'k'){
            if(dll.isEmtpy()){
                cout << "list is empty!" << endl;
            }
            else{
                cout << "list is not empty!" << endl;
            }
        }
        if(alpha == 'l'){
            int tmp;
            cout << "enter number you want to remove(only non-overlapping values remain from the beginning of list) : ";
            cin >> tmp;
            dll.remove(tmp);
        }
        if(alpha == 'm'){
            dll.remove_Duplicate();
            cout << "complete!" << endl;
        }
    } 

    cout << "end this program..." << endl;
    return 0;
}