단방향 연결 리스트

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이번 내용에서 배워볼 방법은 동적 할당으로 연결 리스트를 구현해볼 예정이다. 기본 개념만 익힐 것이니 응용은 자신의 생각으로 더 나은 구조로 구현하길 바라겠다.

들어가기 전 노드와 리스트의 형태
1. 노드
 - 노드란, 리스트에서 연결되는 하나의 데이터 정보를 말하는데 어떠한 데이터를 담을 공간과 자신의 다음 위치를 가리킬 포인터를 노드라고한다. 이해하기 쉽도록 아래의 그림을 떠올리면 된다.

노드의 형태

2. 리스트
 - 리스트는 위의 노드를 연결한 모양인데 꼬리에서 꼬리를 무는 형태로 그려진다. 수많은 구현 방법이 있겠지만 지금 구현하는 방법은 head와 tail 즉, 머리(시작점)와 꼬리(끝점)라는 멤버 변수를 추가하여 삽입, 탐색, 삭제에서 유용하게 쓰일 변수들을 추가할 것이다. 아래의 그림에서 head가 가리키는 위치와 tail이 가리키는 위치를 기억하자.

시작 지점을 head, 끝 지점을 tail로 설정

① 데이터 삽입을 보자. 노드를 생성하여 값은 10으로 다음 주소를 가리키는 포인터를 nullptr로 생성한 후 리스트에 담아준다. 리스트에 첫 번째로 담길 노드이기 때문에 이 노드는 head와 tail이 가리키게 된다. 가장 머리에 있는 노드라고 정하는 것이다. 

처음 노드를 리스트에 삽입한 그림

② 두 번째 이후 삽입부터는 20이라는 값을 가진 노드를 생성하여 현재 tail이 가리키는 0x100 노드 멤버 변수 nextNode가 nullptr을 가리켰었는데 0x200 주소를 가리키도록 연결을 시켜준다. 그 후 tail을 가장 마지막에 연결한 노드로 이동시켜준다.

0x200 노드 삽입이 완료된 그림

 

③ 데이터 검색 및 출력은 리스트는 연결된 형태이기 때문에 앞에서부터 순차탐색을 이용한다. head의 위치를 변경되지 않도록 current가 노드에서부터 하나씩 nextNode를 이용하여 다음 연결된 노드로 이동하여 데이터를 검색한다. 검색을 실패하거나 출력이 완료되었을 경우 다음 노드로 이동한다.

Current의 이동 방향 그림

④ 데이터 삭제는 ③번과 동일하게 순회하면서 다음 위치를 삭제해버리면 다다음 위치를 접근할 수 없게 되어버린다. 바로 아래의 그림을 보면 이와 같은 상황을 볼 수 있다. 정상적으로 삭제를 하려면 0x200 노드를 삭제하기 전 0x100 노드의 nextNode를 0x300에 연결을 시켜준 후에 삭제를 해야 한다.

연결된 노드를 바로 삭제하면 접근할 수 없는 문제가 발생!!

0x100 노드의 nextNode를 0x300 노드로 연결한 후 정상적으로 삭제하는 그림

리스트의 삽입, 탐색, 삭제의 개념을 알아보았으니 간단하게 코드로 단방향 연결 리스트를 구현해보자.

 

#include <iostream>
 
using namespace std;
 
#define MAX_LENGTH 5
 
// 노드 구조체
typedef struct node
{
    // 생성자
    node() : data(0), nextNode(nullptr) {}
 
    // 데이터
    int data;
 
    // 다음 노드를 가리키는 포인터
    node* nextNode;
}NODE;
 
// 리스트 구조체
typedef struct list
{
    // 생성자
    list() : head(nullptr), tail(nullptr) {}
 
    // 리스트의 시작점을 나타내는 노드
    node* head;
 
    // 리스트의 끝점을 나타내는 노드
    node* tail;
}LIST;
 
void Insert(LIST* list, int data)
{
    // 노드 생성
    NODE* newNode = new NODE;
    newNode->data = data;
    newNode->nextNode = nullptr;
 
    // head 노드가 비어있을 경우
    if (list->head == nullptr)
    {
        // 처음 생성한 노드를 head에 대입
        list->head = newNode;
    }
    else
    {
        // 마지막 노드의 nextNode에 생성한 노드 연결
        list->tail->nextNode = newNode;
    }
 
    // 가장 마지막으로 생성한 노드를 tail에 대입
    list->tail = newNode;
}
 
void Find(LIST* list, int findData)
{
    // head 노드가 비어있을 경우
    if (list->head == nullptr)
    {
        cout << "탐색할 데이터가 없습니다." << endl;
        return;
    }
    
    // head 부터 탐색할 노드, 탐색할 다음 노드 저장
    NODE* curNode = list->head;
 
    // 탐색할 값이 없을 때까지 순회
    while (curNode != nullptr)
    {
        // 탐색하고자하는 데이터와 비교
        if (curNode->data == findData)
        {
            cout << "탐색 값 : " << curNode->data << endl << endl;
            return;
        }
 
        // 다음 위치 노드 저장
        curNode = curNode->nextNode;
    }
 
    cout << "탐색 실패" << endl << endl;
}
 
void Delete(LIST* list)
{
    // head 노드가 비어있을 경우
    if (list->head == nullptr)
    {
        cout << "삭제할 데이터가 없습니다." << endl;
        return;
    }
 
    // 시작 위치를 삭제 변수에 대입
    NODE* deleteNode = list->head;
    cout << "리스트 삭제 : " << "\t";
 
    // 삭제할 노드가 더이상 없을 경우 루프 탈출
    while (deleteNode != nullptr)
    {
        // head의 다음 위치를 head로 대입
        list->head = list->head->nextNode;
 
        // 노드 삭제
        cout << deleteNode->data << "\t";
        delete deleteNode;
        deleteNode = nullptr;
 
        deleteNode = list->head;
    }
 
    // 줄바꿈 처리
    cout << endl << endl;
}
 
void Display(LIST* list)
{
    // head 노드가 비어있을 경우 연산하지 않음
    if (list->head == nullptr)
    {
        cout << "저장된 데이터가 없습니다." << endl;
        return;
    }
 
    // 시작 위치를 출력 변수에 대입
    NODE* printNode = list->head;
    cout << "리스트 출력 : " << "\t";
 
    // 다음 노드를 가리키는 nextNode가 비어있을 때까지 순회
    while (printNode != nullptr)
    {
        // 데이터 출력
        cout << printNode->data << "\t";
 
        // 출력 변수에 다음 위치를 가리키도록 대입
        printNode = printNode->nextNode;
    }
 
    // 줄바꿈 처리
    cout << endl << endl;
}
 
int main()
{
    // 리스트 생성
    LIST* newList = new LIST;
 
    // 노드 삽입
    for (int i = 0; i < MAX_LENGTH; ++i)
    {
        Insert(newList, (i + 1) * 10);
    }
 
    // 리스트 출력
    Display(newList);
 
    // 리스트 검색
    Find(newList, 30);
 
    // 리스트 삭제
    Delete(newList);
}