Singly linked list [c++]

singly linked list의 개념

*** single linked list의 노드는 데이터를 보관하는 필드, 다음 노드와 연결고리 역할을 하는 포인터로 이루어집니다.

데이터과 포인터로 이루어진 노드를 연결시키면 linked list가 되는 것입니다. 리스트의 첫 번째 노드는 head(머리), 마지막 노드는 tail(꼬리)라고 부릅니다.

---

c++로 구현한 singly linked list

#include <iostream>
using namespace std;
template <typename T>
struct Node{
        public:
                T data;
                struct Node* next;
};
template <typename T>
class SinglyLinkedList{
        private:
                Node<T>* head_;
                Node<T>* tail_;
        public:
                SinglyLinkedList();
                ~SinglyLinkedList();

                void printAll();
                Node<T>* createNode(T newData);
                void destroyNode(Node<T>* node);
                void appendNode(Node<T>* newNode);
                void insertNode(Node<T>* current, Node<T>* newNode);
                void insertNewHead(Node<T>* newHead);
                void removeNode(Node<T>* Remove);
                void removeHead();
                void removeTail();
                int getSize();
                Node<T>* getNodeAt(int location);
};
template <typename T>
SinglyLinkedList<T>::SinglyLinkedList():head_(nullptr), tail_(nullptr){

}
template <typename T>
SinglyLinkedList<T>::~SinglyLinkedList(){
        Node<T>* current = head_;

        while (current != nullptr){
        		Node<T>* temp = current;
                current = current->next;
                destroyNode(temp);
        }
}
template <typename T>
void SinglyLinkedList<T>::printAll(){
        Node<T>* current = head_;
        cout << "start ->";
        while(current != nullptr){
                cout << current->data << " -> ";
                current = current->next;
        }
        cout << "end"<< endl;
}
template <typename T>
Node<T>* SinglyLinkedList<T>::createNode(T newData){
        Node<T>* newNode = new Node<T>;

        newNode->data = newData;
        newNode->next = nullptr;

        return newNode;
}
template <typename T>
void SinglyLinkedList<T>::destroyNode(Node<T>* node){
        node->next = nullptr;
        delete node;
}
template <typename T>
void SinglyLinkedList<T>::appendNode(Node<T>* newNode){
        if (head_ == nullptr){
                head_ = newNode;
        }
        else {
                tail_->next = newNode;
        }
        tail_ = newNode;
}
template <typename T>
void SinglyLinkedList<T>::insertNode(Node<T>* current, Node<T>* newNode){
        newNode->next = current->next;
        current->next = newNode;
}
template <typename T>
void SinglyLinkedList<T>::insertNewHead(Node<T>* newHead){
        if (head_ == nullptr){
                tail_ = newHead;
        }
        else {
                newHead->next = head_;
        }
        head_ = newHead;
}
template <typename T>
void SinglyLinkedList<T>::removeNode(Node<T>* Remove){
        if (head_ == Remove){
                removeHead();
        }
        else if (tail_ == Remove){
                removeTail();
        }
        else {
                Node<T>* temp = head_;

                while (temp->next != Remove){
                        temp = temp->next;
                }

                temp->next = Remove->next;
                Remove->next = nullptr;
        }
}
template <typename T>
void SinglyLinkedList<T>::removeHead(){
        if (head_ == tail_){
                head_ = nullptr;
                tail_ = nullptr;
        }
        else {
                Node<T>* temp = head_;
                head_ = head_->next;
                temp->next = nullptr;
        }
}
template <typename T>
void SinglyLinkedList<T>::removeTail(){
        if (head_ == tail_){
                head_ = nullptr;
                tail_ = nullptr;
        }
        else {
                Node<T>* current = head_;

                while (current->next != tail_){
                        current = current->next;
                }

                current->next = nullptr;
                tail_ = current;
        }
}
template <typename T>
int SinglyLinkedList<T>::getSize(){
        int count = 0;
        Node<T>* current = head_;

        while (current != nullptr){
                current = current->next;
                count++;
        }

        return count;
}
template <typename T>
Node<T>* SinglyLinkedList<T>::getNodeAt(int location){
        Node<T>* current = head_;

        while ((--location-1)>=0){
                current = current->next;
        }

        return current;
}
int main()
{
        SinglyLinkedList<int>* singlylinkedlist = new SinglyLinkedList<int>();

        for (int i=0;i<10;i++){
                Node<int>* newNode = singlylinkedlist->createNode(i+1);
                singlylinkedlist->appendNode(newNode);
        }

        singlylinkedlist->printAll();

        Node<int>* remove = singlylinkedlist->getNodeAt(5);
        singlylinkedlist->removeNode(remove);

        singlylinkedlist->printAll();

        singlylinkedlist->removeHead();
        singlylinkedlist->printAll();

        singlylinkedlist->removeTail();
        singlylinkedlist->printAll();
}

출력
start ->1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> end
start ->1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9 -> 10 -> end
start ->2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9 -> 10 -> end
start ->2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9 -> end