[C++] 연결리스트 (list.h , node.h , CMakeLists.txt)-컴도리돌이

우리는 간단한 linked list data 구조를 만들 것이다. 링크된 목록은 연결된 형태의 노드를 말하며, 각 노드가 다음 노드를 가리킨다.
List 클래스는 head라고 불리는 특별한 노드를 가지고 있다. 다음 헤드 노드는 목록의 첫 번째 요소를 가리킨다. 목록의 첫 번째 요소 중 다음 요소는 목록의 두 번째 요소를 가리키며, 이러한 방식으로 nullptr(0x0)이 나타날 때까지 목록을 반복하여 반복적으로 반복할 수 있다.

 

---

<list.h>

#include <string>
#include <functional>

#include "node.h"

template <typename T>
class List {
public:
    List() : count(0) {
        head = new Node<T>(0, nullptr);
    }
    ~List() {
        // TODO: write your code here
        // release remain nodes before delete head node
        while(this->head->next != nullptr)
        {
            pop_front();
        }
        delete this->head;
    }
    void push_front(T value) {
        // TODO: write your code here
        // create new node with value
        // and add node to front of list
        Node<T>* new_node = new Node<T>(value,this->head->next);
        this->head->next = new_node;
        count++;
    }
    void push_back(T value) {
        // TODO: write your code here
        // create new node with value
        // and add node to back of list
        if(count == 0)
        {
            Node<T>* new_node = new Node<T>(value,this->head->next);
            this->head->next = new_node;
            count++;
        }
        else
        {
            Node<T>* new_node = new Node<T>(value,nullptr);
            Node<T>* last_node = this->head;
            while (last_node->next != nullptr)
            {
               last_node = last_node->next;
            }
            last_node->next = new_node; 
            count++;   
        }        
    }
    T pop_front() {
        // TODO: write your code here
        // remove front node(not head)
        // and return its value
        // if try to remove head node return 0
        if(this->head->next == nullptr) return 0;
        Node<T>* delete_node;
        delete_node = this->head->next;
        this->head->next = this->head->next->next;
        count--;
        return delete_node->value;
    }
    T pop_back() {
        // TODO: write your code here
        // remove back node(not head)
        // and return its value
        // if try to remove head node return 0
        if(this->head->next == nullptr) return 0;
        Node<T>* delete_node;
        Node<T>* prev_delete_node= this->head;

        while (prev_delete_node->next->next != nullptr)
        {
           prev_delete_node = prev_delete_node->next;
        }
        delete_node = prev_delete_node->next;
        prev_delete_node->next = nullptr;
        count--;
        return delete_node->value;
    }    
    size_t size() {
        // TODO: write your code here
        // return current items in list (except head)
        return count;
    }
    void traverse(const std::function<void(const Node<T>&)>& f) {
        for (Node<T>* node = head->next; node != nullptr; node = node->next) {
            f(*node);
        }
    }
private:
    Node<T>* head;
    size_t count;
    // OPTIONAL: you can write helper functions
};

 

<node.h>

template <typename T>
class Node {
public:
    Node() {}
    Node(T value) : value(value) {}
    Node(T value, Node* next) : value(value), next(next) {}
    
    T value;
    Node* next;
};

 

<CMakeLists.txt>

cmake_minimum_required(VERSION 3.1.0 FATAL_ERROR)
set (CMAKE_CXX_STANDARD 11)
add_executable(main main.cc)