[자료구조] 양방향 연결리스트

어제에 이어 이번에는 양방향 연결리스트를 구현해보았다.

양방향 연결리스트는 prev 포인터가 추가되기에 이 점을 잘 생각해야한다.

 

---

 

#include <iostream>
#include <stack>
using namespace std;

struct Node
{
    int value;
    Node* next;
    Node* prev;
};
Node* node = NULL;


void addNode(int m)
{
    if (node == NULL)
    {
        node = new Node();
        node->value = m;
        node->next = NULL;
        node->prev = NULL;
    }
    else
    {
        Node* end = node;
        while(end->next != NULL)
        {
            end = end->next;
        }

        Node* newNode = new Node();
        newNode->value = m;
        newNode->next = NULL;
        newNode->prev = end;
        end->next = newNode;
    }
}

void deleteNode(int d)
{
    Node* target = node;
    
    if (target == NULL) 
    {
        cout << "\n노드가 비어있습니다.\n";
        return;
    }
    
    while(target != NULL && target->value != d)
    {
        target = target->next;
    }

    if (target == NULL) 
    {
        cout << "\n삭제할 값을 찾지 못했습니다.\n";
        return;
    }

    if (target == node)
    {
        node = node->next;

        // 노드가 한 개 뿐이라면, node->next가 NULL이 되므로 예외처리
        // node != NULL > 노드가 두 개 이상이었다는 의미
        if (node != NULL)
            node->prev = NULL;
    }
    else
    {
        target->next->prev = target->prev;
        target->prev->next = target->next;
    }

    delete target;
}


void makeCircular()
{
    Node* start = node;
    Node* end = node;
    while(end->next != NULL)
    {
        end = end->next;
    }

    start->prev = end;
    end->next = start;
}


void print()
{
    Node* print = node;
    cout << "현재 노드: ";

    while(print != NULL)
    {
        cout << print->value << " ";
        print = print->next;
    }
}



int main() 
{
    int N;
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        int M;
        cin >> M;
        addNode(M);
    }

    cout << "완성된 노드\n";
    print();
    
    int D;
    cout << "\n\n어떤 요소를 지우시겠습니까? ";
    cin >> D;
    deleteNode(D);

    cout << "\n지우고 난 후의 노드\n";
    print();
    connect();
    
    return 0;
}

 

prev 하나 추가되었다고 전체적으로 맥락이 크게 달라지진 않지만, 몇몇 부분을 세심히 예외처리 해줘야한다

 

if (target == node)
    {
        node = node->next;

        // 노드가 한 개 뿐이라면, node->next가 NULL이 되므로 예외처리
        // node != NULL > 노드가 두 개 이상이었다는 의미
        if (node != NULL)
            node->prev = NULL;
    }

 

가령 deleteNode에서 이 부분인데 (나도 처음에 이해안갔음)

 

노드가 하나밖에 없었다고 가정하면 node->next가 NULL이 된다.

그래서? 그게 무슨 차이인데? 

 

노드가 두 개 이상부터는 node->next가 NULL이 아니다.

 

[5]

[5] [1] [3]

이 차이라면, 다음 노드 3에서 1이라는 target을 가리켰던 prev 포인터를 NULL 처리해줘야 한다.

 

아 그런가? 그래야하나? 싶다가도 말로 설명하니 그럴 수 밖에 없겠구나~ 싶다.

여기서부턴 지피티니 쌤과 얘기하며 나눈 추가 질문들이다.

 

 

1) 양방향 연결 리스트에서 tail 포인터를 따로 두면 좋은 점은?

tail 포인터라면 리스트가 추가/삭제되어도 자동으로 끝 점을 갱신하는 포인터인가?(그렇다고 함)

그렇게 따로 둔다면, 계속해서 내가 while문으로 순회하며 리스트의 끝 점을 찾았던 과정이 없어진다. O(N)에서 O(1)으로 검색 속도가 빨라진다.

 

2) 단일 연결 리스트에서 중간 노드를 O(N) 순회로 찾는 방법은?

(이거 답변한 방법이 비효율적이었음)

노드의 주소를 next 한번 하는 slow 포인터와, 두 번 하는 fast 포인터를 둔다. fast 포인터가 연결 리스트의 끝에 도달하면 slow 포인터는 자연스레 중간 노드가 된다

 

---

 

 

늘 그랬듯이 기본기가 중요함을 느낀다!