오늘도 돌아온 자료구조 시간!! 오늘은 C++로 연결 리스트를 구현해보겠습니다.
기본적인 개념은 생략하고 코드 구현을 중심으로 글을 써보도록 하겠습니다.

연결 리스트 설정

연결리스트의 한 요소를 사진과 같이 구현해봅시다.

typedef int Data; 

typedef struct _Node {
    Data item; // 리스트 요소의 내용
    struct _Node *next; // 자기참조구조체, 다음 노드를 가리키기 위함
} Node;

typedef struct {
    Node *head; // 연결 리스트의 head
    int len; // 연결 리스트의 길이
} LinkedList;

먼저 위 코드로 구조체를 정의합니다.

연결 리스트 관련 함수들

InitList() - 비어있는 연결 리스트 만들기

void InitList(LinkedList *plist) {
    plist->head = (Node *) malloc(sizeof(Node));
    plist->head->next = NULL; // dummy node
    plist->len = 0;
}

우리는 리스트의 삽입와 삭제를 보다 편한 방법으로 하기 위해 더미 노드를 필요로 합니다. 이건 나중에 아래에 설명하겠습니다.

IsEmpty() - 리스트가 비어있는가

bool IsEmpty(LinkedList *plist) {
    return plist->len == 0;
}

리스트의 길이가 0일 경우 true를 반환하는 아주 간단한 함수입니다.

리스트의 삽입과 삭제

리스트를 삽입 또는 삭제하는 데에 가능한 케이스는 다양합니다.

삽입

• 비어있는 리스트에 노드 삽입
• 첫번째 위치에 노드 삽입
• 노드의 K번째 위치에 노드 삽입

삭제

• 첫번째 위치의 노드 삭제
• 노드의 K번째 위치에 있는 노드 삭제

이런 경우를 다 고려해서 각각 코드를 짜기에는 너무 불편합니다.
그래서 우리는 하나의 통합된 솔루션을 알아볼겁니다.

더미 노드

더미 노드는 말 그대로 아무 기능도 없는 가짜 노드를 말합니다.
위 사진은 삽입을 예시로 든 것인데 아무것도 없는 더미 노드를 리스트의 head로 지정하면 삽입과 삭제의 여러가지 경우에 대해 똑같은 솔루션을 사용할 수 있습니다.

InsertMiddle() - 요소 삽입

void InsertMiddle(LinkedList *plist, int pos, Data item) {
    Node *cur, *newNode; // 각각 현재 위치, 새로운 노드
    if (pos < 0 || pos > plist->len)
        exit(1);

    newNode = (Node *) malloc(sizeof(Node));
    newNode->item = item;
    newNode->next = NULL; // 새로운 노드를 만들어냅니다.

    cur = plist->head;
    for (int i = 0; i < pos; i++) // 삽입하고자 하는 위치로 이동
        cur = cur->next;

    newNode->next = cur->next; // 새 노드를 삽입하고자 하는 위치의 다음 노드와 연결
    cur->next = newNode; // 현재 위치의 다음 노드는 새 노드가 될 것!
    plist->len++; // 리스트 길이 증가
}

일련의 과정을 개조식으로 정리하자면 이렇습니다.
1. 새 노드 만들기
2. 노드를 넣을 위치의 전 위치로 cur 포인터 옮기기
3. 새 노드를 cur 포인터의 다음 노드에 연결
4. cur 포인터의 다음 노드는 새 노드가 될 것 이기 때문에 둘을 연결
5. 리스트 길이 증가

RemoveMiddle() - 요소 삭제

void RemoveMiddle(LinkedList *plist, int pos) {
    Node *cur, *temp;
    if (IsEmpty(plist) || pos < 0 || pos >= plist->len)
        exit(1);

    cur = plist->head;
    for (int i = 0; i < pos; i++)
        cur = cur->next;

    temp = cur->next;
    cur->next = cur->next->next; // cur->next->next == temp->next
    plist->len--;
    free(temp); // 요소 삭제
}

삽입과 원리는 비슷합니다.
K번째 노드를 삭제한다 치면..
1. cur 포인터를 (K-1) 번째 위치로 이동합니다.
2. temp 포인터를 K번째 노드에 지정합니다.
3. (K-1) 번째 노드와 (K+1) 번째 노드를 연결시킵니다.
4. K 번째 노드(temp)를 제거합니다.

ReadItem() - 요소 읽기

Data ReadItem(LinkedList *plist, int pos) {
    Node *cur;
    if (IsEmpty(plist) || pos < 0 || pos >= plist->len)
        exit(1);

    cur = plist->head->next;
    for (int i = 0; i < pos; i++)
        cur = cur->next;

    return cur->item;
}

인자로 위치를 받아 원하는 위치의 요소를 반환합니다.

PrintList() - 전체 요소 출력

void PrintList(LinkedList* plist) {
    for (Node* cur = plist->head->next; cur != NULL; cur = cur->next)
        cout << cur->item;
    cout << "\n";
}

cur 포인터를 계속 이동시키며 요소를 출력시킵니다.

ClearList() - 연결 리스트 삭제

void ClearList(LinkedList* plist) {
	// 계속 첫 노드만을 삭제하며 모든 노드를 삭제하는 것
    while (plist->head->next != NULL) 
        RemoveMiddle(plist, 0);
    free(plist->head);
}

메모리 누수를 방지하기 위해 리스트를 삭제합니다.

적용해보기

int main() {
    LinkedList list;
    InitList(&list);

    InsertMiddle(&list, 0, 1);
    InsertMiddle(&list, 1, 2);
    InsertMiddle(&list, 2, 3);

    PrintList(&list);

    RemoveMiddle(&list, 1);

    PrintList(&list);

    ClearList(&list);

    return 0;
}

삽입/삭제의 간단한 예제를 작성해보았습니다.

출력 결과

123
13

코드에 따라 올바르게 실행되는 것을 확인할 수 있습니다.