[C++] Singly Linked List(싱글 링크드 리스트) 구현

Singly Linked List란?

 

◎ 단일 방향으로 노드들이 연결되어 있는 STL container 중 하나이다.

 

◎ 데이터를 가지고 있는 연결된 노드들의 맨 앞과 맨 뒤에는 Head , Tail 이름의 노드가 있다.

 

◎ 노드들은 모두 next라는 노드 포인터를 가지고 있어서 다음 노드와 연결 할 수 있다.

 

 

구현

 

◎ Class 와 Struct를 사용하여 좀 더 깔끔한 코드를 구현하였다.

 

◎ Template 을 사용하여 int 뿐만 아니라 다른 Type의 자료형을 위한 Container로도 사용할 수 있다.

 

 

Coding

 

1) 기본 구조

 

template<typename T>
struct Node{
    T data; // Node 속 data 저장
    Node<T>* next = nullptr;
};

template<typename T>
class Singlist{
private:
    Node<T>* head; // singlist의 시작. list의 data가 들어있지는 않다.
    Node<T>* tail; // sinlist의 마지막. list의 data가 들어있지는 않다.
public:

    Singlist() : head(new Node<T>{-1,nullptr}) , tail(new Node<T>{-1,nullptr}) {}
    ~Singlist() {}

 

2) 함수

 

① addNode : List 끝에 값을 push 한다.

 

void addNode(T new_value){
        if(empty()){
            head->next = new Node<T>{new_value,tail};
        }
        
        else{
            Node<T>* last_node = find_last_node();
            
            last_node->next = new Node<T>{new_value,tail};
        }
    }

// tail 직전 Node를 return

    Node<T>* find_last_node(){
        
        Node<T>* last = head;
        
        if(empty()) return nullptr;
        
        while(last->next != tail){
            last = last->next;
        }   
        
        return last;
    }

 

② deleteNode : List 제일 끝의 값을 pop 한다.

 

void deleteNode(){

        if(empty()){
            cout << "deleteNode function doesn't work. list is empty." << endl;
            return ;
        }
        
        else{
        
            Node<T>* before = head;
            Node<T>* del = head->next;
            
            while(del->next != tail){
                before = before -> next;
                del = del -> next;
            }
            
            before -> next = tail;
        }
    }

 

③ insertNode : List에 값을 N 번째 위치에 insert한다.

 

    void insertNode(T new_value , int N){
    
        if(N > size()){
            cout << "singlist has less datas than " << N << "." << "\n";
        }
        
        else if(N < 0){
            cout << "N is negative number. please give me index number." << "\n";
        }
        
        else if(empty()){
            addNode(new_value);
        }
        
        else{
            Node<T>* before = head;
            for(int i = 0 ; i < N ; i++){
                before = before->next;
            }
            before->next = new Node<T>{new_value,before->next};
        }
    }

 

④ printAll : List 출력

 

void printAll(){
        Node<T>* node = head;
        
        if(empty()) return ;
        
        while(node->next != tail){
            node = node -> next;
            cout << node->data << ' ';
        }
    }

 

⑤ size : List size 반환

 

int size(){
        Node<T>* size = head;
        int cnt = 0;
        
        if(empty()) return cnt;
        
        while(size->next != tail){
            size = size->next;
            cnt++;
        }
        
        return cnt;
    }

 

⑥ search : List 속에 값이 있는지 없는지 확인.

 

bool search(T value){

        Node<T>* node = head->next;
  
  	while(node != tail){
            if(node->data == value) return true;
            node = node->next;
        }
        
        return false;
    }

 

⑦ getData : N 번째 노드의 값을 반환.

 

T getData(int N){

        if(N >= size()){
            return -1;      
        }
        
        Node<T>* node = head;
        for(int i = 0 ; i <= N ; i++){
            node = node -> next;
        }
        
        return node->data;
    }