연결리스트 - Linked list(C++ 코드구현, 소스코드, 개념)

연결리스트 (Linked list)

연결리스트는 데이터를 저장하는 자료구조로, 각각의 데이터 요소가 포인터를 통해 다음 요소와 연결되어 있는 방식으로 동작하는 비선형 자료구조입니다.

 

작동 원리

연결리스트는 노드(node)라고 불리는 개별적인 데이터 요소들이 링크(link)를 통해 연결되어 동작합니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어있습니다. 첫 번째 노드를 가리키는 특별한 포인터인 헤드(head)포인터도 존재합니다.

 

더 자세하게고 쉽게 사진으로 설명하겠습니다.

 

사진 출처 : https://en.wikipedia.org/wiki/Linked_list

사진에서, 데이터필드와 링크필드를 담고있는 한 객체가 노드입니다. 각 노드는 이전에 설명했듯이, 데이터를 담고있는 데이터필드와 다음 노드를 가리키는 포인터인 링크필드로 구성되어있습니다. 

연결리스트는 다음 노드를 가리키는 포인터를 활용해서, 메모리를 동적으로 할당하여 사용할 수 있으며 데이터의 삽입과 삭제가 빈번하게 발생하는 경우에 유용하게 사용됩니다.

 

#include <iostream>

// 연결리스트의 노드를 표현하는 구조체
struct Node {
    int data;       // 노드의 데이터 (데이터 필드)
    Node* next;     // 다음 노드를 가리키는 포인터 (링크 필드)
};

// 연결리스트 클래스
class LinkedList {
private:
    Node* head;     // 첫 번째 노드를 가리키는 포인터 (헤드 포인터)

public:
    // 생성자
    LinkedList() {
        head = nullptr;
    }

    // 연결리스트 끝에 데이터를 추가하는 함수
    void append(int data) {
        // 새로운 노드 생성
        Node* newNode = new Node;
        newNode->data = data;
        newNode->next = nullptr;

        if (head == nullptr) {
            // 연결리스트가 비어있을 경우
            // 첫 번째 노드를 가리키는 헤드포인터를 새로운 노드로 변경합니다.
            head = newNode;
        } else {
            // 연결리스트가 비어있지 않을 경우
            Node* current = head;
            // 마지막 노드 찾기
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // 연결리스트의 데이터를 출력하는 함수
    void print_list() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

    // 연결리스트에서 데이터를 삭제하는 함수
    void remove(int data) {
        if (head == nullptr) {
            // 연결리스트가 비어있을 경우
            return;
        }

        if (head->data == data) {
            // 첫 번째 노드를 삭제해야 할 경우
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* current = head;
        // 삭제 할 데이터를 담고있는 노드가 나오기 직전까지 반복합니다.
        while (current->next != nullptr && current->next->data != data) {
            current = current->next;
        }

        if (current->next != nullptr) {
            // 삭제할 노드를 찾은 경우
            Node* temp = current->next;
            // current : 연결리스트를 순회하면서 삭제할 data를 찾기위해 사용됨
            // 삭제할 데이터가 있으면, 삭제 이전 노드의 링크필드를 삭제 다음 노드로 변경
            current->next = current->next->next;
            delete temp;
        }
    }
};

 

위 코드에서 메소드들을 각각 설명하도록 하겠습니다.

 

void append(int data)

이 메소드는 연결리스트의 끝에 데이터를 추가하는 역할을 수행합니다. 새로운 데이터를 저장하기 위해 새로운 노드를 동적으로 할당하고, 해당 노드의 데이터 필드에 매개변수로 받은 데이터를 저장합니다. 그리고 연결리스트가 비어있는 경우, head 포인터를 새로운 노드로 변경하여 첫 번째 노드를 가리키도록 합니다. 비어있지 않은 경우, 마지막 노드를 찾아 해당 노드의 다음 포인터를 새로운 노드로 연결합니다.

 

void print_list()

이 메소드는 연결리스트의 데이터를 출력하는 역할을 수행합니다. head 포인터부터 시작하여 순차적으로 노드를 따라가면서 데이터를 출력합니다.

 

void remove(int data)

이 메소드는 연결리스트에서 데이터를 삭제하는 역할을 수행합니다. 연결리스트가 비어있는 경우에는 삭제할 데이터가 없으므로 작업을 수행하지 않습니다. 첫 번째 노드를 삭제해야 할 경우, head 포인터를 다음 노드로 변경하여 첫 번째 노드를 제거합니다. 그렇지 않은 경우, 삭제할 데이터가 있는 노드를 찾아 해당 노드의 이전 노드와 다음 노드를 연결하여 삭제합니다.