[DS] 연결 리스트(Linked List)란?

Array를 사용한 list 표현에는 고정된 크기, 연속된 공간에 필요, 중간 원소 추가/삭제가 비효율적이라는 단점이 존재합니다.

 

 

이러한 단점을 개선한 자료 구조가 연결 리스트(Linked list)입니다.

연결 리스트(Linked List)란?

데이터(data)와 포인터(pointer)를 포함하는 노드(node)가 한 줄로 연결되어 있는 자료 구조입니다.

 

 

Linked list를 구현하기 위한 ADT 정의

---

class node {
public:
    string name;
    double score;
    node *link;
    void set_data(string s, double d);
};

데이터와 포인터를 포함한 node 클래스를 만들어줍니다.

포인터는 node 클래스를 가르키기 때문에 node type으로 정의합니다.

 

 

class linked_list {
    node *head, *tail;
public:
    linked_list();
    void add_to_head(node t);
    void add_to_tail(node t);
    node delete_from_head();
    int num_nodes();
    double score_sum();
    double get_score(string t_name);
    int remove_a_node(string t_name);
    bool list_empty();
};

head - 연결 리스트(linked list)에 첫 노드(node)

tail - 연결 리스트(linked list)에 마지막 노드(node)

linked_list - 연결 리스트(linked list)를 생성한 초기 상태

add_to_head - 연결 리스트(linked list) head에 원소 한 개 추가

add_to_tail - 연결 리스트(linked list) tail에 원소 한 개 추가

delete_from_head - 연결 리스트(linked list) head 원소 하나 제거

num_nodes - 현재 노드(node)의 개수

score_sum - node 데이터(data)로 들어온 점수를 합산

get_score - 파라미터(parameter)로 들어온 문자열에 해당하는 점수 반환

remove_a_node - 연결 리스트(linked list) 중간에 있는 원소 한 개 제거

list_empty - 현재 연결 리스트(linked list)가 empty인지에 대한 상태 확인

 

 

 

함수코드를 보다가 이해가 안되는 부분이 있다면 main 함수를 먼저 보는 걸 추천드려요!

함수 구현

---

node *p;
p = new node;
(*p) = t;

이 코드는 자주 사용되서 먼저 설명하고 함수 설명 들어가겠습니다.

연결 리스트(linked list)는 list를 사용하지 않고 포인터를 통해 node를 연결시킵니다.

 

그래서 원소를 추가할 때마다 node의 자리(메모리)를 만들어줘야 됩니다.

node *p; p = new node; 코드가 바로 node의 새로운 자리를 만들어주는 코드입니다.

 

그리고 나서 새로 생성된 노드 자리에 파라미터(parameter)로 들어온 데이터 값을 넣어주면 node를 추가해줄 준비가 끝납니다.

 

 

 

void node::set_data(string s, double d) {
    name = s;
    score = d;
}

node class의 data를 셋팅(setting)해주는 메소드(method)입니다.

 

 

 

linked_list::linked_list() {
    head = NULL;
    tail = NULL;
}

linked list class의 생성자(constructor)에서는 head와 tail을 NULL로 초기화시켜 줍니다.

 

 

 

void linked_list::add_to_head(node t) {
    node *p;
    p = new node;
    (*p) = t;

    p->link = head;
    head = p;

    if(tail == NULL) tail = p;
}

add_to_head는 연결 리스트(linked list) head에 원소 한 개를 추가하는 함수입니다.

 

<위에 설명 참고>

 

p-> link = head;

new node의 link를 현재 head가 가르키는 node와 연결시켜줍니다.

 

head = p;

그리고나서 head는 새로 들어온 node를 가르키게 됩니다.

 

if(tail == NULL) tail = p;

tail이 NULL이면 new node가 추가되기 전 linked list가 empty 상태였다는 의미였기에 tail도 p에 연결시켜줍니다.

 

 

 

void linked_list::add_to_tail(node t) {
    node *p;
    p = new node;
    (*p) = t;

    p->link = NULL;
    if(tail!=NULL) tail->link = p;
    else head = p;

    tail = p;
}

add_to_tail는 연결 리스트(linked list) tail에 원소 한 개를 추가하는 함수입니다.

 

<위에 설명 참고>

 

p->link = NULL;

new node의 마지막 노드에 붙기 때문에 link를 NULL로 해줘야 됩니다.

 

if(tail!=NULL) tail->link = p;

pre node의 link를 new node에 연결해줍니다.

 

else head = p;

tail이 NULL이면 new node가 추가되기 전 linked list가 empty 상태였다는 의미였기에 head도 p(new node)에 연결시켜줍니다.

 

tail = p;

어떠한 경우든 tail은 p(new node)가 됩니다.

 

 

 

node linked_list::delete_from_head() {
    node *t;
    node tmp;

    t = head;
    tmp = *head;
    head = head->link;

    delete t;
    if(head == NULL) tail = NULL;

    return tmp;
}

delete_from_head는 연결 리스트(linked list) head에 원소 한 개를 제거하는 함수입니다.

 

node *t;

node를 추가할 때 메모리에 공간을 만들어줬기 때문에 node를 제거할 때는 메모리를 삭제해줘야 됩니다.

메모리를 삭제하기 위한 포인터 변수입니다.

 

node tmp;

제거된 값을 reutrn 해주기 위해 만든 변수입니다.

 

t = head;

삭제할 node가 연결된 head를 포인터 변수 t에 넣습니다.

 

tmp = *head;

삭제할 node의 값을 변수에 저장해 둡니다.

 

head = head->link;

head를 delete될 node의 다음 node와 연결합니다.

 

delete t;

제거될 node의 메모리를 삭제해줍니다.

 

if(head == NULL) tail = NULL;

node를 삭제했을 때 head가 NULL이면 연결 리스트(linked list)가 빈 상태라는 의미기 때문에 tail을 NULL로 만들어 줍니다.

 

return tmp;

제거된 node의 값을 미리 저장해둔 tmp를 return 해줍니다.

 

 

 

int linked_list::num_nodes() {
    node *t;
    int cnt = 0;

    for(t = head; t != NULL; t = t->link) cnt++;

    return cnt;
}

num_nodes는 연결 리스트(linked list) 현재 node의 개수를 반환하는 함수입니다.

 

node *t;

for문을 돌리기 위한 포인터 변수를 하나 생성해 줍니다.

 

int cnt = 0;

cnt 변수는 node의 개수를 세기 위한 변수입니다.

 

for(t = head; t != NULL; t = t->link) cnt++;

처음 시작을 head로 잡고 null이 될 때까지 t의 link를 따라 for문을 반복시켜 줍니다.

 

t가 null이 될 때까지 count(cnt)를 증가시켜 주고,

for문이 종료되면 cnt를 return 시켜줍니다.

 

 

 

double linked_list::score_sum() {
    node *t;
    double sum = 0;

    for(t = head; t != NULL; t = t->link) 
        sum += t->score;
    
    return sum;
}

score_sum은 현재 node에 들어있는 score 값들을 모두 더해서 반환하는 함수입니다.

 

 < for문은 num_nodes 함수 참고 >

 

for문을 돌리면서 node의 score을 하나씩 더해주고,

for문이 끝나면 sum 함수를 return 해줍니다.

 

 

 

double linked_list::get_score(string t_name) {
    node *t;

    for(t = head; t != NULL; t = t->link) 
        if(t->name == t_name) return t->score;

    return 0;
}

get_score은 파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾아 score를 반환하는 함수입니다.

 

 < for문은 num_nodes 함수 참고 >

 

for문을 돌릴 때 파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾으면 그 자리에서 바로 score을 return 해줍니다.

 

 

 

int linked_list::remove_a_node(string t_name) {
    node *pre_node;
    node *t;

    for(t = head; t != NULL; t = t->link) {
        if(t->name == t_name) {
            pre_node->link = t->link;
            delete t;
            return 1;
        }
        pre_node = t;
    }
    return 0;
}

remove_a_node는 파라미터(parameter)로 들어온 문자열과 일치하는 node를 삭제하는 함수입니다.

 

node *pre_node;

파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾았을 때

이전 node와 이후 node를 연결해주기 위해 이전 node를 변수에 저장해 둡니다.

 

node *t;

삭제될 node의 메모리를 제거하기 위해 포인터 변수를 선언했습니다.

 

 < for문은 num_nodes 함수 참고 >

 

if(t->name == t_name) { pre_node->link = t->link;

파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾으면 이전 node와 이후 node를 연결해 줍니다.

 

pre_node = t;

파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾지 못했으면 변수에 현재 node를 저장해둡니다.

 

 

 

 

bool linked_list::list_empty() {
    if(head == NULL) 
        return true;
    else 
        return false;
}

list_empty는 열결 리스트(linked list)가 빈 상태인지 확인하는 함수입니다.

head에 연결된 node가 없으면 연결 리스트(linked list)가 비었다는 의미이기 때문에 true를 return 해줍니다.

 

 

 

main 함수 구현

---

int main( ){
    linked_list a;
    node tmp;

    tmp.set_data("A", 100);
    a.add_to_head(tmp);

    tmp.set_data("B", 99.2);
    a.add_to_head(tmp);                                         
    cout << a.num_nodes() << " : " << a.score_sum() << "\n";    

    tmp.set_data("C", 52.3);   
    a.add_to_tail(tmp);                                         
    cout << a.num_nodes() << " : " << a.score_sum() << "\n";  

    tmp = a.delete_from_head();
    cout  << tmp.name << " is deleted.\n";                      

    tmp.set_data("D", 76.1);   
    a.add_to_tail(tmp);        

    tmp.set_data("E", 21.3);   
    a.add_to_head(tmp);                                        

    cout << a.num_nodes()<< " : "  << a.score_sum() << "\n";
    cout << "C's score : " << a.get_score("C")<< "\n";  

    if ( a.remove_a_node("A") == 1)
        cout << "A is deleted from the list. \n";            
    cout << a.num_nodes()<< " : " << a.score_sum() << "\n";     

    return 0;
}

결과가 잘 나오는 것을 확인할 수 있습니다.

 

 

 

◡̈