[자료구조] 연결 리스트 (Linked List)

Linked list

: 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조. 데이터를 담고 잇는 노드들이 순서를 유지하며 연결되어 있음.

 

🌀 연결 리스트의 종류

- 단일 연결 리스트

- 이중 연결 리스트

- 원형 연결 리스트

 

🌀 장점

리스트의 중간 지점에서도 자료의 추가와 삭제하는 속도가 빠름

🌀 단점

리스트의 특정 위치의 데이터를 검색하는 데에, 배열에 비해서 시간이 더 소요됨

 

---

단일 연결 리스트

: 각 노드에 데이터와 한 개의 포인터가 있고, 각 노드의 포인터는 다음 노드를 가리키는 구조

 

 

이중 연결 리스트

: 각 노드에 데이터와 두 개의 포인터가 있는 구조

- 한 개의 포인터는 이전 노드를 가리킴

- 다른 한 개의 포인터는 다음 노드를 가리킴

 

 

원형 연결 리스트

: 각 노드에 데이터와 한 개의 포인터가 있는 구조

- 마지막 노드의 포인터는 처음 노드를 가리킴

 

---

C++로 단일 연결 리스트 구현

 

헤더파일

 

#ifndef node_hpp
#define node_hpp

#include <stdio.h>

class node
{
public:
    //생성자
    //인자가 들어오지않으면, data는 0으로, next는 NULL로 초기화
    node(const double &init_data = double(), node *init_next = NULL);
    void set_data(const double& new_data);
    void set_link(node* new_link);
    
    double get_data();
    node* get_next();
    
private:
    double data;
    node* next;
};

class link
{
public:
    node* head = NULL;
    
    void head_insert(node*& head_ptr, double data);
    void list_insert(node* previous_ptr, double data);
    void head_remove(node*& head_ptr);
    void list_remove(node* previous_ptr);
    void list_clear(node*& head_ptr);
    
    node* list_search(node* head_ptr, const double target);
    
    void printData();
};


#endif /* node_hpp */

 

node클래스의 data와 next는 private영역에 선언해주었기 때문에 get함수와 set함수를 따로 구현해 주었다.

node::node(const double &init_data, node *init_next)
{
    data = init_data;
    next = init_next;
}

void node::set_data(const double& new_data)
{
    this->data = new_data;
}

void node::set_link(node* new_link)
{
    this->next = new_link;
}

double node::get_data()
{
    return data;
}

node* node::get_next()
{
    return next;
}

 

link클래스에는 head를 넣어주었고, 다음과 같은 함수들을 구현했다.

 

🌀 void head_insert(node*& head_ptr, double data)

: head에 data를 삽입하는 함수이기 때문에, head_ptr는 새로운 node를 가리키게 된다.

void link::head_insert(node*& head_ptr, double data)
{
    head_ptr = new node(data, head_ptr);
}

 

🌀 void link::list_insert(node* previous_ptr, double data)

: previous_ptr를 인자로 받아오면 해당 노드 이후에 data를 추가해준다. 새로운 노드는 data와 previous_ptr가 가리키던 next를 가리키게 되고, previous_ptr는 새로운 노드를 가리킨다.

void link::list_insert(node* previous_ptr, double data)
{
    node* new_node;
    new_node = new node(data, previous_ptr->get_next());
    previous_ptr->set_link(new_node);
}

 

🌀 void link::head_remove(node*& head_ptr)

: head는 현재 head의 다음 노드를 가리키게 되고, 현재 head는 delete해준다.

void link::head_remove(node*& head_ptr)
{
    node* remove_ptr;
    remove_ptr = head_ptr;
    head_ptr = remove_ptr -> get_next();
    delete remove_ptr;
}

 

🌀 void link::list_remove(node* previous_ptr)

: 삭제할 노드는 previous_ptr이 가리키고 있는 다음 노드이다. 노드를 삭제하면 previous_ptr은 삭제할 노드의 다음 노드를 가리킨다.

void link::list_remove(node* previous_ptr)
{
    node* remove_ptr;
    remove_ptr = previous_ptr -> get_next();
    previous_ptr -> set_link(remove_ptr -> get_next());
    delete remove_ptr;
}

 

🌀 void link::list_clear(node*& head_ptr)

: head를 인자로 전달하면 모든 노드를 삭제해준다.

void link::list_clear(node*& head_ptr)
{
    while(head_ptr != NULL)
        head_remove(head_ptr);
}

 

🌀 node* link::list_search(node* head_ptr, const double target)

: head를 인자로 받아오면 target을 data로 가지고 있는 노드를 탐색하고 리턴해준다.

node* link::list_search(node* head_ptr, const double target)
{
    node* cursor;
    for(cursor = head_ptr;cursor != NULL;cursor = cursor->get_next())
        if(target == cursor->get_data())
            return cursor;
    return NULL;
}

 

🌀 void link::printData()

: 모든 노드의 data를 출력한다.

void link::printData()
{
    node *tmpNode = head;
    
    while (tmpNode != NULL)
    {
        std::cout<<tmpNode->get_data()<<std::endl;
        tmpNode = tmpNode->get_next();
    }
}

 

 

main 함수

#include "node.hpp"
#include <iostream>

int main(int argc, const char * argv[]) {
    // insert code here...
    link link;
    link.head_insert(link.head, 1);
    link.head_insert(link.head, 2);
    link.head_insert(link.head, 3);
    link.head_insert(link.head, 4);
    link.printData();
    
    std::cout<<std::endl<<"insert_33_after_3"<<std::endl;
    node* tmp = link.list_search(link.head, 3);
    link.list_insert(tmp, 33);
    link.printData();
    
    std::cout<<std::endl<<"delete_33"<<std::endl;
    link.list_remove(tmp);
    link.printData();
    
    std::cout<<std::endl<<"delete_head"<<std::endl;
    link.head_remove(link.head);
    link.printData();


    std::cout<<std::endl<<"clear"<<std::endl;
    link.list_clear(link.head);
    link.printData();
}

 

실행화면