Doubly Linked List

geminanolja 2024. 12. 11. 08:49

이중 연결 리스트 는 각 노드가 이전 노드와 다음노드에 대한 포인터를 포함한 연결 리스트이다.

리스트를 앞족과 뒤쪽 모두에서 탐색가능하여 노드 삽입과 삭제가 단일 연결 리스트(singly Linked List)보다 효율적이다

시간 복잡도 측면에서 탐색(Search)는 O(N), 삽입(Inserion)의 경우에는 헤드에 삽입시 O(1)의 상수 시간에 처리 가능하며, 맨 뒤에 삽입(Tail)시에도 O(1)의 시간이 소요 된다. 다만 중간에 삽입할 경우에는 삽일할 위치가 탐색되었다는 가정하에 O(1)의 탐색 시간이 소요된다. (만약 탐색까지 포함한다면 O(N) + O(1)의 시간 복잡도를 가지게 된다.

삭제도 동일하다.

DDL 연산 시간 복잡도 요약

연산시간 복잡도설명

탐색	O(N)O(N)	최악의 경우 리스트 전체를 순회해야 함.
맨 앞 삽입	O(1)	포인터 몇 개만 갱신하면 됨.
맨 뒤 삽입	O(1)	포인터 몇 개만 갱신하면 됨.
중간 삽입	O(N)	먼저 위치를 탐색한 후 삽입.
맨 앞 삭제	O(1)	포인터 몇 개만 갱신하면 됨.
맨 뒤 삭제	O(1)	포인터 몇 개만 갱신하면 됨.
중간 삭제	O(N)	먼저 위치를 탐색한 후 삭제.
연결	O(1)	두 리스트의 tail과 head를 연결하는 간단한 작업.

DDL vs SLL (단일 연결 리스트) 시간 복잡도 비교

연산단일 연결 리스트 (SLL)이중 연결 리스트 (DDL)

탐색	O(N)	O(N)
맨 앞 삽입	O(1)	O(1)
맨 뒤 삽입	O(N) (테일 포인터 없음)	O(1) (테일 포인터 있음)
중간 삽입	O(N)	O(N)
맨 앞 삭제	O(1)	O(1)
맨 뒤 삭제	O(N) (테일 포인터 없음)	O(1) (테일 포인터 있음)
중간 삭제	O(N)	O(N)

시간 복잡도:
- 삽입/삭제 연산 자체: O(1)
- 노드 찾기: O(n)
- 전체 과정: O(n)
장점:
- 노드를 찾은 후 삽입/삭제는 매우 빠름 (포인터만 변경)
- 메모리 재할당 필요 없음
단점:
- 특정 위치의 노드를 찾는 데 시간이 걸림 (리스트 순회 필요)

배열과의 비교:

배열 중간 삽입/삭제:
- 시간 복잡도: O(n)
- 요소 이동이 필요함 (삽입/삭제 위치 이후의 모든 요소)
배열 장점:
- 인덱스로 즉시 접근 가능 (O(1))
배열 단점:
- 삽입/삭제 시 요소 이동 필요
- 크기 변경 시 전체 재할당 필요할 수 있음

결론:

연결 리스트의 중간 삽입/삭제가 항상 배열보다 빠르지는 않습니다.
노드를 찾는 과정을 포함하면 전체 시간 복잡도는 O(n)으로 배열과 동일합니다.
하지만 삽입/삭제 위치를 알고 있다면 (예: 포인터로 직접 접근 가능), 연결 리스트가 O(1)로 매우 빠릅니다.

연결 리스트가 유리한 경우:

삽입/삭제가 빈번한 경우
데이터의 크기가 자주 변하는 경우
포인터로 직접 노드에 접근 가능한 경우

배열이 유리한 경우:

빈번한 탐색이 필요한 경우
데이터 크기가 고정적인 경우

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Node
{
public:
    Node(int data) : data(data) {}

public:
    int data;
    Node* prev = nullptr;
    Node* next = nullptr;
};

int main()
{
    /*
    std::cout << "Hello World";
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    Node* n4 = new Node(4);
    Node* n5 = new Node(5);

    n1->next = n2;

    n2->prev = n1;
    n2->next = n3;

    n3->prev = n2;
    n3->next = n4;

    n4->prev = n3;
    n4->next = n5;

    n5->prev = n4;*/


    int N = 1;
    cout << "How many nodes you want??" << endl;
    cin >> N;

    vector<Node*> nodes;
    Node* head = nullptr;
    Node* tail = nullptr;
    Node* prevNode = nullptr;

    for (int i = 1; i <= N; i++)
    {
        Node* newNode = new Node(i);// i 만큼 newNode 를 만들어서
        nodes.push_back(newNode); // nodes 라는 벡터 안에 저장

        if (i == 1)
        {
            head = newNode;
            cout << "Head node created!" << endl;
        }
        else if (i == N)
        {
            tail = newNode;
            cout << "Tail node Created!!" << endl;
        }

        else
        {
            cout << i << " th Node Created" << endl;
        }

        if (prevNode)
        {
            prevNode->next = newNode;// i =1이면 prev =nullptr 이므로 nullptr->next = head 
            newNode->prev = prevNode; // head->prev는 nullptr 가 됨
        }
        prevNode = newNode; //그리고 nullptr 였던 prevNode를 생성된 head로 set해줌
        cout << "Node Address : " << newNode << endl;
        cout << endl;
    }

    //Check Node connections
    Node* current = head;
    while (current)
    {
        cout << "Current Node : " << current << " it's prevNode : " << current->prev << " & nextNode : " << current->next << endl;
        current = current->next;
    }

    for (Node* node : nodes)
    {
        delete node;//nodes vector를 돌면서 Node를 다 지워라
    }

    return 0;
}

continue to DDL2