C++ 실습 - 링크드리스트

< 링크드리스트 (Linked list) >

동적할당을 이용해 자료를 저장할 공간이 필요할 때마다 메모리를 할당하는 데이터 관리법입니다.

'노드'를 연결해 목록을 만드는 방식인데, 시작 노드를 안다면 중간 노드들을 거쳐 종료 노드까지 탐색할 수 있습니다.

노드의 특징으로 다음 노드와 연결점을 가지고 있다는 점이 그것을 가능하게 만듭니다.

장점 : 노드 개수의 제한이 없다.

단점 : 특정 데이터에 바로 접근 불가 (<-> 배열은 인덱스로 접근 가능)

#include <iostream>
#include <string>
 
using namespace std;
 
int i;
 
// 구조체
typedef struct Student {
    string name;
    Student *next = NULL;  // 다음 노드의 주소 저장 초기값은 NULL
} S;
 
S *head = new S;
 
void add_node(string name) {
    S *temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
 
    S *node = new S;
    node->name = name;
    temp->next = node;
}
 
void del_node(string name) {
    S *temp = head;
    while (temp->next->name != name) {
        if ((temp = temp->next) == NULL) {  // 일치하는 노드가 없다면 함수 종료
            return;
        }
    }
 
    S *node_del = temp->next;
    temp->next = temp->next->next;
 
    delete node_del;
}
 
S *find_node(string name) {
    S *temp = head;
    while (temp->next->name != name) {
        if ((temp = temp->next) == NULL) {  // 일치하는 노드가 없다면 함수 종료
            return NULL;
        }
    }
 
    return temp->next;
}
 
void print_list() {
    S *temp = head;
    for (i = 1; temp->next != NULL; i++) {
        cout << i << " : " << temp->next->name << endl;
        temp = temp->next;
    }
}
 
int main() {
    string name;
    cout << "< 추가할 이름 입력 > (입력 종료는 0)" << endl;
    while (name != "0") {
        cout << "이름 : ";
        cin >> name;
        add_node(name);
    }
 
    print_list();
    name = "";
 
    cout << "< 제거할 이름 입력 > (입력 종료는 0)" << endl;
    while (name != "0") {
        cout << "이름 : ";
        cin >> name;
        del_node(name);
    }
 
    print_list();
 
    return 0;
}