자료구조 - 연결 리스트(1)

앞에서 리스트를 배열로 구현해 보았는데 이번에는 연결 리스트를 통해서 리스트를 구현해보겠습니다.

 

[연결 리스트]

연결 리스트는 각 노드 가 데이터와 다음 노드에 대한 포인터를 포함하는 구조입니다.

연결 리스트는 동적 메모리 할당을 사용하므로 크기 변경이 용이하지만, 요소 접근 시간이 배열에 비해 느립니다.

 

연결 리스트의 구조

연결 리스트의 기본 단위는 노드(Node)입니다. 각 노드는 다음과 같은 구조를 가집니다.

struct Node {
    int data;   // 데이터
    Node* next; // 다음 노드를 가리키는 포인터
};

 

 

공백 리스트의 생성

Node* head = nullptr;  // 공백 리스트는 헤드 포인터가 nullptr

 

 

노드의 생성과 연결

Node* newNode = new Node();  // 새로운 노드 생성
newNode->data = 10;          // 데이터 저장
newNode->next = head;        // 새 노드가 리스트의 첫 번째 노드가 되도록 연결
head = newNode;              // 헤드 포인터를 새 노드로 갱신

 

 

 

 

 

[연결 리스트의 종류]

 

 

원형 연결 리스트와 이중 연결 리스트는 추후에 살펴보고

우선 단순 연결 리스트에 대해서만 알아보겠습니다.

 

 

[단순 연결 리스트]

단순 연결 리스트는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결되어 있습니다.

마지막 노드의 링크 필드 값은 NULL이 됩니다.

아래 그림은 A, B, C, D 가 단순 연결 리스트에 저장되어 있는 상태입니다.

 

단순 연결 리스트를 구현하기 위해서는 우선 노드를 구현해야 합니다.

 

 

노드의 정의

struct Node 
{
    int data;
    Node* next;
};

 

 

단순 연결 리스트의 연산에는 주로 다음과 같은 함수들이 있습니다.

insertFront(e) : 리스트의 시작 부분에 항목을 삽입하는 함수
insertRear(e) : 리스트의 끝 부분에 항목을 삽입하는 함수
remove(index) : 리스트의 지정된 위치의 요소를 삭제하는 함수
get(index) : 지정된 위치의 요소를 반환하는 함수
display() : 리스트의 내용을 출력하는 함수

 

다음과 같은 연산들을 구현해보고 연결 리스트를 구현해보겠습니다.

#include <iostream>

struct Node 
{
    int data;
    Node* next;
};

class LinkedList 
{
    private:
        Node* head;

    public:
        // 생성자: 공백 리스트 생성
        LinkedList() : head(nullptr) {}

        // 리스트가 비어있는지 확인
        bool isEmpty()
        {
            return head == nullptr;
        }
    
        // 리스트의 앞에 요소 삽입
        void insertFront(int element) 
        {
            Node* newNode = new Node();
            newNode->data = element;
            newNode->next = head;
            head = newNode;
        }

        // 리스트의 뒤에 요소 삽입
        void insertRear(int element) 
        {
            Node* newNode = new Node();
            newNode->data = element;
            newNode->next = nullptr;
            if (head == nullptr) 
            {
                head = newNode;
            }
            else 
            {
                Node* temp = head;
                while (temp->next != nullptr) 
                {
                    temp = temp->next;
                }
                temp->next = newNode;
            }
        }

        // 지정된 위치의 요소 삭제
       void remove(int index) 
        {
            if (isEmpty() || index < 0) 
            {
                std::cout << "Index out of bounds or List is empty\n";
                return;
            }
            Node* temp = head;
        
            if (index == 0) 
            {
                head = head->next;
                delete temp;
            } 
            else
            {
                Node* prev = nullptr;
                for (int i = 0; i < index && temp != nullptr; i++)
                {
                    prev = temp;
                    temp = temp->next;
                }
            
                if (temp == nullptr)
                {
                    std::cout << "Index out of bounds\n";
                    return;
                }
                prev->next = temp->next;
                delete temp;
            }
        }

        // 지정된 위치의 요소 반환
        int get(int index) 
        {
            if (isEmpty() || index < 0)
            {
                std::cout << "Index out of bounds or List is empty\n";
                return -1;
            }
            
            Node* temp = head;
            for (int i = 0; i < index && temp != nullptr; i++) 
            {
                temp = temp->next;
            }
        
            if (temp == nullptr)
            {
                std::cout << "Index out of bounds\n";
                return -1;
            }
            return temp->data;
        }

        // 리스트 출력 (디버깅 용도)
        void display()
        {
            Node* temp = head;
            while (temp != nullptr) 
            {
                std::cout << temp->data << " ";
                temp = temp->next;
            }
            std::cout << std::endl;
        }
};

int main()
{
    LinkedList list;
    list.insertFront(3);
    list.insertFront(2);
    list.insertFront(1);
    list.display();

    list.insertRear(4);
    list.display();

    list.remove(1);
    list.display();

    std::cout << "Element at index 1: " << list.get(1) << std::endl;

    return 0;
}

 

 

 

 

[연결리스트와 배열로 구현한 리스트의 차이점]

 

1. 메모리 사용 방식:

• 배열 리스트: 연속된 메모리 블록을 사용합니다. 크기 변경이 어렵고, 메모리 낭비가 발생할 수 있습니다.
• 연결 리스트: 동적 메모리 할당을 사용하여 필요한 만큼 메모리를 사용합니다. 크기 변경이 용이하지만, 각 노드에 추가 메모리(포인터)가 필요합니다.

2. 접근 시간:

• 배열 리스트: 인덱스를 통해 O(1) 시간에 요소에 접근할 수 있습니다.
• 연결 리스트: 순차 접근만 가능하며, O(n) 시간이 소요됩니다.

3. 삽입 및 삭제 연산:

• 배열 리스트: 중간에 삽입/삭제 시 요소들을 이동해야 하므로 O(n) 시간이 소요됩니다.
• 연결 리스트: 노드의 포인터만 변경하면 되므로 O(1) 시간에 가능하지만, 특정 위치를 찾기 위해 O(n) 시간이 필요할 수 있습니다.

4. 크기 변경:

• 배열 리스트: 고정 크기이며, 크기 변경 시 전체 배열을 재할당해야 합니다.
• 연결 리스트: 동적 크기이며, 필요에 따라 노드를 추가/삭제할 수 있습니다.

•