C++ 리스트 구현해보기

역시 STL 사용법은 패스

노드 기반 컨테이너, 보통은 이중 연결 리스트를 얘기함, 임의 접근 불가능

추가 삭제에 비용이 적음, 메모리에 연속적으로 구성되지 않아 순회가 상대적으로 느림

이중연결 리스트 구현 코드

#pragma once
#include <iostream>
 
template<typename T>
class MyList {
private:
    template<typename T>
    class Node {
    public:
        Node() : value(nullptr), prev(nullptr), next(nullptr) {}
        Node(T* data) : value(data), prev(nullptr), next(nullptr) {}
        Node(T* data, Node* prev, Node* next) :value(data), prev(prev), next(next) {}
        ~Node() {
            delete value;
        }
        T* value;
        Node* prev;
        Node* next;
    };
    Node<T>* front;
    Node<T>* back;
    size_t size;
    void RemoveNode(Node<T>* node);
public:
    MyList();
    ~MyList();
    T& Front();
    T& Back();
    void Push_Front(const T& value);
    void Pop_Front();
    void Push_Back(const T& value);
    void Pop_Back();
    void Reverse();
    void Insert(size_t index, const T& value);
    void Delete(size_t index);
    void PrintAll();
    size_t Size();
};
 
template<typename T>
MyList<T>::MyList() {
    front = new Node<T>();
    back = new Node<T>();
    front->next = back;
    front->prev = front;
    front->value = nullptr;
    back->next = back;
    back->prev = front;
    back->value = nullptr;
}
template<typename T>
MyList<T>::~MyList() {
    Node<T>* current = front;
    Node<T>* temp = nullptr;
    while (current != nullptr) {
        temp = current->next;
        RemoveNode(current);
        current = temp;
    }
}
template<typename T>
T& MyList<T>::Front() {
    return *(front->value);
}
template <typename T>
T& MyList<T>::Back() {
    return *(back->value);
}
template <typename T>
void MyList<T>::Push_Front(const T& value) {
    T* data = new T(value);
    Node<T>* node = new Node<T>(data);
    node->next = front;
    front->prev = node;
    front = node;
    if (size == 0) {
        back = front;
    }
    size++;
}
template <typename T>
void MyList<T>::Pop_Front() {
    Node<T>* temp = front->next;
    RemoveNode(front);
    front = temp;
    size--;
}
template <typename T>
void MyList<T>::Push_Back(const T& value) {
    T* data = new T(value);
    Node<T>* node = new Node<T>(data);
    node->prev = back;
    back->next = node;
    back = node;
    if (size == 0) {
        front = back;
    }
    size++;
}
template <typename T>
void MyList<T>::Pop_Back() {
    Node<T>* temp = back->prev;
    RemoveNode(back);
    back = temp;
    size--;
}
template <typename T>
void MyList<T>::Reverse() {
    std::cout << "Reverse()" << std::endl;
    Node<T>* temp;
    for (Node<T>* current = front; current != nullptr; current = current->prev) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
    }
    temp = front;
    front = back;
    back = temp;
}
template <typename T>
void MyList<T>::Insert(size_t index, const T& value) {
    if (index > size || index < 0) {
        std::cout << "잘못된 인덱스" << std::endl;
        return;
    }
    if (size == 0 || index == 0) {
        Push_Front(value);
        return;
    }
    if (index == size) {
        Push_Back(value);
        return;
    }
    Node<T>* current = front;
    for (size_t i = 0; i < index - 1; i++) {
        current = current->next;
    }
    T* data = new T(value);
    Node<T>* node = new Node<T>(data, current, current->next);
    //node->next = current->next;
    //node->prev = current;
    if (current->next != nullptr) {
        current->next->prev = node;
    }
    current->next = node;
    size++;
}
template <typename T>
void MyList<T>::Delete(size_t index) {
    if (size <= 0) {
        return;
    }
    if (index >= size || index < 0) {
        return;
    }
    if (index == 0) {
        Pop_Front();
        return;
    }
    if (index == size - 1) {
        Pop_Back();
        return;
    }
    Node<T>* current = front;
    for (size_t i = 0; i < index; i++) {
        current = current->next;
    }
    RemoveNode(current);
}
template <typename T>
void MyList<T>::RemoveNode(Node<T>* node) {
    if (node->next != nullptr) {
        node->next->prev = node->prev;
    }
    if (node->prev != nullptr) {
        node->prev->next = node->next;
    }
    delete node;
}
template <typename T>
void MyList<T>::PrintAll() {
    for (Node<T>* current = front; current != nullptr; current = current->next) {
        std::cout << *(current->value) << std::endl;
    }
}
template <typename T>
size_t MyList<T>::Size() {
    return size;
}

단일 링크드 리스트

#pragma once
 
template<typename T>
class MySingleList {
private:
    template<typename T>
    class Node {
    public:
        Node() : value(nullptr), next(nullptr) {}
        Node(T* data) : value(data), next(nullptr) {}
        Node(T* data, Node* next) :value(data), next(next) {}
        ~Node() {
            delete value;
        }
        T* value;
        Node* next;
    };
    Node<T>* front;
    Node<T>* back;
    size_t size;
    //void RemoveNode(Node<T>* node);
public:
    MySingleList();
    ~MySingleList();
    T& Front();
    T& Back();
    void Push_Front(const T& value);
    void Pop_Front();
    void Push_Back(const T& value);
    void Pop_Back();
    void Reverse();
    void Insert(size_t index, const T& value);
    void Delete(size_t index);
    void PrintAll();
    size_t Size();
};
template<typename T>
MySingleList<T>::MySingleList() {
    front = new Node<T>();
    back = new Node<T>();
    front->next = back;
    front->value = nullptr;
    back->next = back;
    back->value = nullptr;
}
template<typename T>
MySingleList<T>::~MySingleList() {
    Node<T>* current = front;
    Node<T>* temp = nullptr;
    while (current != nullptr) {
        temp = current->next;
        //RemoveNode(current);
        delete current;
        current = temp;
    }
}
template<typename T>
T& MySingleList<T>::Front() {
    return *(front->value);
}
template<typename T>
T& MySingleList<T>::Back() {
    return *(back->value);
}
template<typename T>
void MySingleList<T>::Push_Front(const T& value) {
    T* data = new T(value);
    Node<T>* node = new Node<T>(data);
    node->next = front;
    front = node;
    if (size == 0) {
        back = front;
    }
    size++;
}
template<typename T>
void MySingleList<T>::Pop_Front() {
    Node<T>* temp = front->next;
    delete front;
    front = temp;
    size--;
}
template<typename T>
void MySingleList<T>::Push_Back(const T& value) {
    T* data = new T(value);
    Node<T>* node = new Node<T>(data);
    back->next = node;
    back = node;
    if (size == 0) {
        front = back;
    }
    size++;
}
template<typename T>
void MySingleList<T>::Pop_Back() {
    Node<T>* current = front;
    while (current->next != back) {
        current = current->next;
    }
    delete back;
    current->next = nullptr;
    back = current;
    size--;
}
template<typename T>
void MySingleList<T>::Reverse() {
    std::cout << "Reverse()" << std::endl;
    Node<T>* prev = nullptr;
    Node<T>* next = nullptr;
    for (Node<T>* current = front; current != nullptr; current = next) {
        next = current->next;
        current->next = prev;
        prev = current;
    }
    prev = front;
    front = back;
    back = prev;
}
template<typename T>
void MySingleList<T>::Insert(size_t index, const T& value) {
    if (index > size || index < 0) {
        std::cout << "잘못된 인덱스" << std::endl;
        return;
    }
    if (size == 0 || index == 0) {
        Push_Front(value);
        return;
    }
    if (index == size) {
        Push_Back(value);
        return;
    }
    Node<T>* current = front;
    for (size_t i = 0; i < index - 1; i++) {
        current = current->next;
    }
    T* data = new T(value);
    Node<T>* node = new Node<T>(data, current->next);
    current->next = node;
    size++;
}
template<typename T>
void MySingleList<T>::Delete(size_t index) {
    if (size <= 0) {
        return;
    }
    if (index >= size || index < 0) {
        return;
    }
    if (index == 0) {
        Pop_Front();
        return;
    }
    if (index == size - 1) {
        Pop_Back();
        return;
    }
    Node<T>* current = front;
    for (size_t i = 0; i < index - 1; i++) {
        current = current->next;
    }
    if (current->next != nullptr) {
        Node<T>* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
    //delete current;
    //RemoveNode(current);
}
//template<typename T>
//void MySingleList<T>::RemoveNode(Node<T>* node) {
//    delete node;
//}
template<typename T>
void MySingleList<T>::PrintAll() {
    for (Node<T>* current = front; current != nullptr; current = current->next) {
        std::cout << *(current->value) << std::endl;
    }
}
template<typename T>
size_t MySingleList<T>::Size() {
    return size;
}