[자료구조] 연결 리스트(c++)

연결리스트(Linked-List)란?

하나의 노드가 다음 노드의 주소를 가리키어 서로 연결되어 있는 자료구조이다.

단방향 연결 리스트, 양방향 연결 리스트, 환형 연결 리스트 등의 구조가 있다.

 

배열(Array) vs 연결 리스트(Linked List)

비슷한 기능을 가진 배열이 있는데, 연결 리스트를 왜 사용하는 것일까?

배열과 연결 리스트를 비교하며 각각 어떤 특징이 있는 지 알아보자.

	배열	연결 리스트
구조	선언 시 연속된 메모리 공간을 할당하고, 순차적으로 요소들이 저장 된다.	각 노드가 값과 다음 노드를 가리키는 포인터로 구성된다. 메모리 상에서 연속된 위치에 저장되지 않고, 동적으로 할당된다.
크기	초기화 할 때 고정된 메모리로 결정된다.	가변적으로 크기 조정이 가능하다.
삽입 및 삭제	중간에 요소를 삽입하거나 삭제하려면 해당 위치 이후 모든 요소들을 이동시켜야 한다. O(n)의 시간 복잡도를 가진다.	특정 위치에 노드를 삽입 및 삭제할 때, 해당 위치의 앞, 뒤가 가리키는 주소만 변경하면 된다. O(1)의 시간 복잡도를 가진다.
접근	인덱스를 통해 직접 요소에 접근한다. O(1)의 시간 복잡도를 가진다.	Head부터 특정 위치까지 순차적으로 탐색하여야 한다. O(n)의 시간 복잡도를 가진다.

 

연결 리스트의 동작

 -삽입

 -삭제

구현

동적 할당 vs 정적 할당

 기본적으로 연결 리스트는 메모리를 동적으로 할당하는 자료구조이다. 하지만 알고리즘 문제를 품에 있어 매번 동적으로 메모리를 할당하는 것은 비효율적이다. 그래서 메모리를 충분한 만큼 미리 선언해두고,  필요할 때 가져다 쓰는 메모리 풀(memory pool)이란 방법이 있다.

struct node{
    int data;
    node* next;
}

// 동적 할당
node* new_node(int data){
    node* node = new node;
    node->data = data;
    node->next = nullptr;
    return node;
}

//정적 할당
node pool[10000];
int node_cnt = 0;

node* get_node(int data){
    pool[node_cnt].data = data;
    pool[node_cnt].next = nullptr;
    return &pool[node_cnt++];
}

 

1. 단방향 연결 리스트(Singly Linked List)

#include <iostream>
using namespace std;
#define MAX_NODE 10000

struct Node{
    int data;
    node* next;
}

Node node[MAX_NODE];
int node_cnt;
Node* head;
Node* list;

Node *getNode(int data){
    node[node_cnt].data = data;
    node[node_cnt].next = nullptr;
    return &node[node_cnt++];
}

//초기화
void init(){
    head = nullptr;
    node_cnt = 0;
    return;
}

//삽입 -num번째 자리에 data 삽입
void add_node(int data, int num){
    Node* new_node = getNode(data);
    if(num == 1){
    	new_node->next = head;
        head = new_node;
    }
    else{
    	list = head;
        for(int i = 2; i < num; i++){
        	list = list->next;
        }
        new_node->next = list->next;
        list->next = new_node;
    }
    return;
}

//삭제 -제일 먼저 만나는 값이 data인 노드를 삭제
void remove_node(int data){
    if(head->data == data){
    	head = head->next;
    }
    else{
    	list = head;
        while(list->next != nullptr){
        	if(list->next->data == data){
            	list->next = list->next->next;
                return;
            }
            list = list->next;
        }
    }
    return;
}

//출력
void print(){
    list = head;
    cout << "List ";
    while(list->next != nullptr){
    	cout << list->data << " -> ";
        list = list->next;
    }
    cout << list->data << '\n';
    return;
}

int main(){
    int cmd, x, n;
    while(1){
    	cin >> cmd;
        switch(cmd){
        case 0:
        	init();
            break;
       	case 1:
        	cin >> x >> n;
            add_node(x, n);
            break;
        case 2:
        	cin >> x;
            remove_node(x);
            break;
        case 3:
        	print();
            break;
        default:
        	return 0;
        }
    }
}

 

2. 양방향 연결 리스트(Doubly Linked List)

#include <iostream>
using namespace std;
#define MAX_NODE 10000

struct Node{
    int data;
    node* next;
    node* prev;
}

Node node[MAX_NODE];
int node_cnt;
Node* head;
Node* tail;
Node* list;

Node *getNode(int data){
    node[node_cnt].data = data;
    node[node_cnt].next = nullptr;
    node[node_cnt].prev = nullptr;
    return &node[node_cnt++];
}

//초기화
void init(){
    head = nullptr;
    tail = nullptr;
    node_cnt = 0;
    return;
}

//삽입 -num번째 자리에 data 삽입
void add_node(int data, int num){
    Node* new_node = getNode(data);
    if(num == 1){
    	if(head == nullptr){
        	head = new_node;
            tail = head;
        }
        else{
        	head->prev = new_node;
        	new_node->next = head;
        	head = new_node;
        }
    }
    else{
    	list = head;
        for(int i = 2; i < num; i++){
        	list = list->next;
        }
        if(list->next == nullptr){
        	tail->next = new_node;
            new_node->prev = tail;
            tail = new_node;
        }
        else{
        	new_node->next = list->next;
        	list->next = new_node;
            new_node->prev = list;
            list->next->next->prev = new_node;
        }
    }
    return;
}

//삭제 -제일 먼저 만나는 값이 data인 노드를 삭제
void remove_node(int data){
    if(head->data == data){
    	head = head->next;
        head->prev = nullptr;
    }
    else{
    	list = head;
        while(list->next != nullptr){
        	if(list->next->data == data){
            	if(list->next->next != nullptr){
            		list->next = list->next->next;
                	list->next->prev = list;
                }
                else{
                	tail = list;
                    tail->next = nullptr;
                }
                return;
            }
            list = list->next;
        }
    }
    return;
}

//출력
void print(){
    list = head;
    cout << "List ";
    while(list->next != nullptr){
    	cout << list->data << " -> ";
        list = list->next;
    }
    cout << list->data << '\n';
    return;
}

//반대로 출력
void reverse_print(){
    list = tail;
    cout << "reverse List ";
    while(list->prev != nullptr){
    	cout << list->data << " -> ";
        list = list->prev;
    }
    cout << list->data << '\n';
    return;
}

int main(){
    int cmd, x, n;
    while(1){
    	cin >> cmd;
        switch(cmd){
        case 0:
        	init();
            break;
       	case 1:
        	cin >> x >> n;
            add_node(x, n);
            break;
        case 2:
        	cin >> x;
            remove_node(x);
            break;
        case 3:
        	print();
            break;
        case 4:
        	reverse_print();
            break;
        default:
        	return 0;
        }
    }
}