2024-12 - 31 연결 리스트 , 단일 연결 리스트

연결 리스트(Linked List)는 데이터를 저장하는 구조로,

각 데이터 요소가 노드라는 단위로 구성되며,

각 노드는 다음 노드에 대한 포인터를 포함

-동적으로 크기 조절

-삽입과 삭제가 용이한 특징이 있음.

단일 연결 리스트 (Singly Linked List):

각 노드가 데이터와 다음 노드에 대한 포인터를 가지고 있음.
마지막 노드는 NULL 포인터를 가리킴
탐색이 한 방향으로만 가능하며, 이전 노드로의 접근이 불가능

이중 연결 리스트 (Doubly Linked List):

각 노드가 데이터, 다음 노드에 대한 포인터, 그리고 이전 노드에 대한 포인터를 가지고 있음.
양방향 탐색이 가능하여 더 유연함.

원형 연결 리스트 (Circular Linked List):

마지막 노드가 첫 번째 노드를 가리키도록 연결되어 있습니다.
단일 및 이중 연결 리스트 모두 원형 구조로 만들 수 있습니다.

#include <iostream>

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

class SinglyLinkedList {
private:
    Node* head;     // 리스트의 첫 번째 노드

public:
    SinglyLinkedList() : head(nullptr) {}

    // 노드 추가 (리스트의 앞에 추가)
    void push_front(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = head;
        head = newNode;
    }

    // 노드 출력
    void printList() {
        Node* current = head;
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

    // 메모리 해제
    ~SinglyLinkedList() {
        Node* current = head;
        Node* nextNode;
        while (current) {
            nextNode = current->next;
            delete current;
            current = nextNode;
        }
    }
};

int main() {
    SinglyLinkedList list;
    list.push_front(10);
    list.push_front(20);
    list.push_front(30);

    std::cout << "연결 리스트 요소: ";
    list.printList();

    return 0;
}

ai한태 물어봐서 가져온 코드입니다.

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

노드 데이터에 Node*를 만들어줘서 연결이 가능 하게하고

private:
Node* head; // 리스트의 첫 번째 노드

연결 리스트 클래스에서는 노드의 첫번째 주소를 가지고 있습니다.

SinglyLinkedList() : head(nullptr) {}

현재 노드를 nullptr로 만들어줍니다 이 노드가 끝을 확인 하는용도로 사용 가능합니다.

// 노드 추가 (리스트의 앞에 추가)
    void push_front(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = head;
        head = newNode;
    }

이부분을 보면

새로운 노드를 생성 해주고
노드에 값을 넣고
중요! 여기서 새로만든 노드에 다음 주소를 현재 리스트가 가지고있던 첫번째 노드를 넣습니다
그다음 리스트가 가지고 있는 첫번째 노드를 새로 만든 노드로 만들어줍니다.

그러면

SinglyLinkedList list;
    list.push_front(10);
    list.push_front(20);
    list.push_front(30);

아래 메인에서 이코드를 보면

10- nullptr
20 - 10 - nullptr
30 - 20 - 10 - nullptr

순으로 push_back과는 반대로 앞으로 넣어주는 방식입니다.

노드를 찾는 방법은

// 노드 출력
    void printList() {
        Node* current = head;
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

현재 노드를 정해주고
반복문을 통해서 노드의 데이터 출력 후 current노드를 current노드의 자식노드로 지정하면서 순회 합니다.
필요시 if문을 사용해서 data = n인 경우 등 의 조건을 넣어서 해당 노드를 찾을 수 있습니다.

사용후 메모리 삭제는

// 메모리 해제
    ~SinglyLinkedList() {
        Node* current = head;
        Node* nextNode;
        while (current) {
            nextNode = current->next;
            delete current;
            current = nextNode;
        }
    }

출력 방식과유사합니다.

현재 노드를 정해주고
다음 노드도 정해줍니다.
반복 문에서 다음 노드를 현재노드의 자식노드로 지정후
현재 노드를 delete해줍니다.
현재노드는 다음 노드로 지정해주면서 모든 노드를 삭제시켜줍니다.

그러면 왜 vector나 배열과 같은 기능을 이렇게 풀어서 사용할까요?

배열은 고정된 크기를 가진다는 점에서 크기를 다로 조절 해주는 코드를 만들어야되고

벡터는 크기가 조절 가능하지만 내부적으로 연속적인 메모리 블록을 사용합니다.

연결리스트는 메모리에서 비연속적으로 할당됩니다.

예시) 벡터 공간 0 1 2 3 4 , 연결리스트 1 9 2 8 0

접근 속도는

배열 과 벡터는 O(1)상수 시간

으로 연속적으로 저장되기 때문에 인덱스를 사용하여 직접 접근할 수 있습니다.

연결리스트의 접근 속도는 O(n) 선형시간

으로 특정 인덱스의 요소에 접근하려면 처음부터 끝까지 순회해야합니다.

즉 접근속도는 배열과 벡터가 우수합니다.

여기서 하나 깨달은것 벡터는 동적 배열의 한 종류이다.

추가 및 삭제는

배열과 벡터의 경우

O(n) 최악의 경우입니다.

배열의 중간에 요소를 추가하거나 삭제할 경우,

나머지 요소를 이동해야 하므로 O(n)의 시간이 걸립니다.

하지만 배열의 끝에 추가하는 경우는 O(1)입니다

메모리 사용
배열
메모리가 연속적으로 할당되므로, 공간 효율성이 높습니다. 하지만 크기를 동적으로 조절할 수 있는 경우, 추가적인 메모리 할당이 필요할 수 있습니다.

연결 리스트
각 노드가 포인터를 포함하므로, 포인터를 저장하는 데 추가적인 메모리가 필요합니다. 따라서 메모리 사용 효율이 낮을 수 있습니다.

요약

연결리스트와 배열의 차이는
탐색은 배열이 우수
추가및 삭제는 연결리스트가 우수하지만

배열이 push_back을 사용할 경우동급(중간에서 추가와 삭제는 O(n)소요

연속적인 메모리와 비연속적인 메모리

연속적인 메모리
연속적인 메모리는 데이터가 메모리에서 인접한 위치에 저장되는 것을 의미합니다. 즉, 메모리 주소가 연속적으로 할당

O(1) 시간에 접근 가능.
데이터가 메모리의 인접한 위치에 저장되어 CPU 캐시를 효율적으로 사용

비연속적인 메모리

데이터가 메모리의 서로 다른 위치에 저장되는 것을 의미합니다. 각 요소는 독립적인 메모리 블록에 할당

데이터가 추가되거나 삭제될 때 메모리를 동적으로 할당할 수 있어, 크기에 제한이 없음
메모리에서 큰 연속 블록이 필요하지 않으므로, 작은 조각을 사용하여 메모리를 효율적으로 사용할 수 있음

메모리를 비연속적으로 할당한다는건 , 연속 블록이 필요하지 않다는 뜻입니다.

즉 메모리 단편화 문제를 피할 수 있습니다!!

메모리 단편화란

메모리가 비효율적으로 사용되어 사용 가능한 큰 메모리 블록이 없게 되는 상황을 말합니다.

내부 단편화와 외부 단편화.로 나뉘는데

내부 단편화

할당된 메모리 블록이 실제로 필요한 메모리보다 더 큰 경우 발생합니다.

할당된 메모리의 일부가 사용되지 않고 남는 것입니다.

1000의 공간에서 실제로 필요한메모리가 800일 경우 200의 공간 이 남게 되는데 이 남은 공간을

다른 프로세스에서 사용할 수 없습니다.!! (즉 메모리 낭비)

외부 단편화 (External Fragmentation)

여러 개의 작은 메모리 블록이 남아 있어도, 이 블록들이 연속적이지 않아 큰 메모리 블록을 할당할 수 없는 상황을 말합니다.

메모리에서 100KB, 200KB, 50KB의 블록이 남아 있다면, 이론적으로는 350KB의 메모리가 남아 있지만, 300KB의 메모리를 요청할 경우 할당할 수 없는 상황이 발생합니다.

간단하게 말하면

비효율적인 메모리 사용 , 성능 저하

글쓴이 생각

알고리즘과 자료구조 둘다 효율적인 코드와 메모리 관리이지만

코드에서 어느 자료구조나 알고리즘이 유용한지 생각하고 사용하는 것이 중요함.

저작자표시 비영리 변경금지

비구름

2024-12 - 31 연결 리스트 , 단일 연결 리스트

티스토리툴바