[기초] C++ Linked List : 연결 리스트

---

 

연결 리스트(linked list)는 데이터 요소의 집합을 순차적으로 저장하는 선형 자료구조입니다.

배열과 달리, 연결 리스트에서는 데이터 요소들이 메모리의 연속적인 위치에 저장되지 않고

각 요소가 포인터를 통해 다음 요소와 연결됩니다.

이런 특성 때문에 연결 리스트는 동적인 메모리 관리에 적합하며,

삽입과 삭제 연산을 배열에 비해 효율적으로 수행할 수 있습니다.

 

---

 

전체 코드

#include <iostream>

// 연결 리스트의 노드를 정의합니다.
struct Node {
    int data;
    Node* next;
    
    // 생성자를 사용하여 노드를 초기화합니다.
    Node(int val) : data(val), next(nullptr) {}
};

// 연결 리스트 클래스를 정의합니다.
class LinkedList {
private:
    Node* head; // 연결 리스트의 첫 번째 노드를 가리키는 포인터

public:
    // 생성자를 사용하여 연결 리스트를 초기화합니다.
    LinkedList() : head(nullptr) {}

    // 연결 리스트에 요소를 추가하는 함수
    void insert(int val) {
        Node* newNode = new Node(val);
        if (head == nullptr) {
            // 리스트가 비어있을 경우
            head = newNode;
        } else {
            // 리스트가 비어있지 않을 경우
            Node* temp = head;
            while (temp->next != nullptr) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
    }

    // 연결 리스트의 내용을 출력하는 함수
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

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

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

        Node* prev = head;
        Node* curr = head->next;

        while (curr != nullptr && curr->data != val) {
            prev = curr;
            curr = curr->next;
        }

        if (curr != nullptr) {
            // 찾은 요소를 삭제하는 경우
            prev->next = curr->next;
            delete curr;
        }
    }

    // 소멸자를 사용하여 메모리 누수를 방지합니다.
    ~LinkedList() {
        Node* temp = head;
        while (temp != nullptr) {
            Node* next = temp->next;
            delete temp;
            temp = next;
        }
    }
};

int main() {
    LinkedList list;
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);

    std::cout << "Initial List: ";
    list.display();

    list.remove(3);

    std::cout << "After removing 3: ";
    list.display();

    return 0;
}

 

---

 

1. 구조체

 

struct Node {
    int data;
    Node* next;
    
    Node(int val) : data(val), next(nullptr) {}
};

 

• 'Node' 구조체는 리스트의 각 요소(element)를 나타냅니다.
  'data' 멤버 변수는 요소의 값을 저장하고, 'next' 멤버 변수는 다음 노드를 가리킵니다.
  
  
• 생성자는 'data' 멤버를 초기화하고, 'next'는 'nullptr'로 설정하여
  노드가 다음 노드를 가리키지 않음을 나타냅니다 (즉, 현재 노드가 리스트의 마지막임).

 

2. LinkedList 클래스

 

class LinkedList {
private:
    Node* head;
public:
    LinkedList() : head(nullptr) {}
    void insert(int val);
    void display();
    void remove(int val);
    ~LinkedList();
};

 

• 'LinkedList' 클래스는 연결 리스트를 관리합니다.
  'head' 포인터는 리스트의 첫 노드를 가리킵니다.
  
  
• 생성자에서 'head'를 'nullptr'로 초기화하여 리스트가 비어 있음을 나타냅니다.
  
  
  

3. 삽입 함수

 

void insert(int val) {
    Node* newNode = new Node(val);
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

 

• 새로운 노드를 생성하고 리스트의 끝에 추가합니다.
  
  
• 만약 리스트가 비어있다면('head == nullptr'), 'head'가 새 노드를 가리키게 합니다.
  
  
• 그렇지 않다면, 리스트의 마지막 노드를 찾고, 'next' 포인터를 새 노드로 설정합니다.
  
  
  

4. 출력 함수

 

void display() {
    Node* temp = head;
    while (temp != nullptr) {
        std::cout << temp->data << " ";
        temp = temp->next;
    }
    std::cout << std::endl;
}

 

• 'head'부터 시작하여 'next' 포인터를 따라 리스트의 모든 요소를 순회하며 값들을 출력합니다.
  
  
  

5. 삭제 함수

 

void remove(int val) {
    if (head == nullptr) return;
    if (head->data == val) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* prev = head;
    Node* curr = head->next;
    while (curr != nullptr && curr->data != val) {
        prev = curr;
        curr = curr->next;
    }
    if (curr != nullptr) {
        prev->next = curr->next;
        delete curr;
    }
}

 

• 삭제하고자 하는 값이 리스트의 첫 노드에 있을 경우, 첫 노드를 리스트에서 제거합니다.
  
  
• 그렇지 않은 경우, 삭제할 노드를 찾아 'prev' 노드의 'next' 포인터를 삭제할 노드의 다음 노드로 업데이트합니다.
  
  
  

6. 소멸자

 

~LinkedList() {
    Node* temp = head;
    while (temp != nullptr) {
        Node* next = temp->next;
        delete temp;
        temp = next;
    }
}

 

• 클래스 소멸 시, 동적으로 할당된 모든 노드를 메모리에서 해제하여 메모리 누수를 방지합니다.
  
  
  

마무리

 

이 코드는 연결 리스트의 기본적인 구조와 동작을 구현한 것으로,

실제 애플리케이션에서는 더 복잡한 기능과 예외 처리가 필요할 수 있습니다.

또한, 이 구현은 단순 연결 리스트이며,

양방향 연결 리스트나 원형 연결 리스트 등 다른 유형의 리스트 구현도 가능합니다.

 

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀