[자료구조] Doubly Linked List / 이중 연결 리스트 구현 :: C++

 

1. 이중 연결 리스트란?

• 이중 연결 리스트란 단일 연결리스트와 다르게 양방향으로 노드가 이어진 리스트이다.  
• 이중 연결 리스트는 이전 노드와 이후 노드가 이어져 있기 때문에 삽입 삭제 연산 시 이전, 이후 노드를 저장하지 않아도 되기 때문에 훨씬 유연하게 사용할 수 있다.

---

2. 이중 연결 리스트 구현

이번 이중 연결 리스트 구현은 Head와 Tail에 data가 들어있지 않은 더미(dummy)노드를 사용해서 구현했다.

2-1. 구조체 및 클래스 선언부

이중 연결 리스트는 노드 두개가 서로 연결 되어있기 때문에 이전 노드와 다음 노드를 포인팅하는 prev, next 구조체 포인터를 선언해줬다.

이중 연결 리스트의 노드

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

class DoublyLinkedList{
private:
    Node* head;
    Node* tail;
    int size = 0;

public:
    DoublyLinkedList();
    ~DoublyLinkedList() {}
    void AddHead(int value);
    void AddTail(int value);
    void AddSomewhere(Node* node, int value);
    void DeleteHead();
    void DeleteTail();
    void DeleteSomewhere(Node* node);
    Node* FindByIndex(int idx);
    void PrintAll();
};

2-2. FindByIndex

원하는 인덱스에 값을 삽입하기 위해 인덱스로 노드를 찾는 함수이다. 인덱스를 매개변수로 받아서 찾은 노드를 반환한다.

Node* DoublyLinkedList::FindByIndex(int idx) {
    if(idx < 0 || idx > size) return tail;

    Node* temp = head->next;
    for(int i = 0; i < idx-1; i++) {
        temp = temp->next;
    }

    return temp;
}

2-3. AddHead

리스트의 맨 앞 Head부분에 삽입하는 함수이다.

void DoublyLinkedList::AddHead(int value) {
    Node* newNode = new Node;
    newNode->data = value;  //0

    newNode->next = head->next;   //1
    head->next = newNode;         //2
    newNode->prev = newNode->next->prev; //3
    newNode->next->prev = newNode;  //4

    size++;
}

0. 삽입할 데이터를 담은 노드를 생성한다.
1. 새로운 노드의 next를 head의 next로 포인팅한다. (첫번째 원소 삽입 연산이면 tail을 포인팅한다.)
2. head의 next는 새로운 노드를 포인팅한다.
3. 새로운 노드가 포인팅하는 이전노드는 새로운 노드의 다음 노드의 이전노드를 포인팅한다.(첫번째 원소 삽입 연산이면 Head노드를 포인팅 함)
4. 새로운 노드의 다음 노드는 새로운 노드를 포인팅 한다.

말로만 하면 어렵기 때문에 아래 그림을 보자

2-4. AddTail

Tail에 원소를 삽입하는 함수이다.

void DoublyLinkedList::AddTail(int value) {
    Node* newNode = new Node;
    newNode->data = value;

    newNode->prev = tail->prev;   //1
    tail->prev = newNode;         //2
    newNode->next = newNode->prev->next;  //3
    newNode->prev->next = newNode; 	//4

    size++;
}

2-5. AddSomewhere

내가 원하는 인덱스에 원소를 삽입하는 함수이다.

void DoublyLinkedList::AddSomewhere(Node* node, int value) {
    Node* newNode = new Node;
    newNode->data = value;

    newNode->next = node;  //1
    node->prev->next = newNode;  //2
    newNode->prev = node->prev;  //3
    node->prev = newNode;  //4

    size++;
}

2-6. DeleteHead

Head쪽 즉 가장 앞에 있는 원소를 삭제하는 함수이다.

void DoublyLinkedList::DeleteHead() {
    
    head->next = head->next->next; //1
    delete(head->next->prev);      //2
    head->next->prev = head;       //3

    size--;
}

삭제 연산은 삽입연산보다 비교적 쉽다.

1. Head 노드가 포인팅 하는 노드를 삭제하고 싶은 노드의 다음 노드를 포인팅한다.

2. 삭제하고싶은 노드의 메모리를 해제해준다.(안하면 메모리 누수)

3. Head다음 노드가 포인팅하는 prev노드를 Head노드로 변경해준다.

 

삭제 연산 부분도 말로하면 어려우니 아래의 그림으로 보자

2-7. DeleteTail

Tail과 연결된 노드를 삭제하는 함수다.

void DoublyLinkedList::DeleteTail() {
    tail->prev = tail->prev->prev;
    delete(tail->prev->next);
    tail->prev->next = tail;

    size--;
}

2-8. DeleteSomewhere

원하는 부분의 인덱스를 받아서 해당 노드를 삭제하는 연산이다.

void DoublyLinkedList::DeleteSomewhere(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    delete(node);

    size--;
}

3. 전체 코드

#include <iostream>
#include <cstdlib>

using namespace std;

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

class DoublyLinkedList{
private:
    Node* head;
    Node* tail;
    int size = 0;

public:
    DoublyLinkedList();
    ~DoublyLinkedList() {}
    void AddHead(int value);
    void AddTail(int value);
    void AddSomewhere(Node* node, int value);
    void DeleteHead();
    void DeleteTail();
    void DeleteSomewhere(Node* node);
    Node* FindByIndex(int idx);
    void PrintAll();
};

DoublyLinkedList::DoublyLinkedList() {
    head = new Node;
    tail = new Node;

    head->next = tail;
    tail->prev = head;

    size = 0;
}

void DoublyLinkedList::AddHead(int value) {
    Node* newNode = new Node;
    newNode->data = value;

    newNode->next = head->next;
    head->next = newNode;
    newNode->prev = newNode->next->prev;
    newNode->next->prev = newNode;

    size++;
}

void DoublyLinkedList::AddTail(int value) {
    Node* newNode = new Node;
    newNode->data = value;

    newNode->prev = tail->prev;
    tail->prev = newNode;
    newNode->next = newNode->prev->next;
    newNode->prev->next = newNode;

    size++;
}

void DoublyLinkedList::AddSomewhere(Node* node, int value) {
    Node* newNode = new Node;
    newNode->data = value;

    newNode->next = node;
    node->prev->next = newNode;
    newNode->prev = node->prev;
    node->prev = newNode;

    size++;
}

void DoublyLinkedList::DeleteHead() {
    
    head->next = head->next->next;
    delete(head->next->prev);
    head->next->prev = head;

    size--;
}

void DoublyLinkedList::DeleteTail() {
    tail->prev = tail->prev->prev;
    delete(tail->prev->next);
    tail->prev->next = tail;

    size--;
}

void DoublyLinkedList::DeleteSomewhere(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    delete(node);

    size--;
}

Node* DoublyLinkedList::FindByIndex(int idx) {
    if(idx < 0 || idx > size) return tail;

    Node* temp = head->next;
    for(int i = 0; i < idx-1; i++) {
        temp = temp->next;
    }

    return temp;
}

void DoublyLinkedList::PrintAll() {
    cout << "Head";
    Node* node = head->next;
    while(node != tail) {
        cout << " - " << node->data;
        node = node->next;
    }
    cout << " - Tail" << "\n";
}

void menuPrint() {
    cout << "==============SinglyLinkedList===============" << "\n";
    cout << "[1] AddHead" << "\n";
    cout << "[2] AddTail" << "\n";
    cout << "[3] AddSomewhere" << "\n";
    cout << "[4] DeleteHead" << "\n";
    cout << "[5] DeleteTail" << "\n";
    cout << "[6] DeleteSomewhere" << "\n";
    cout << "[7] PrintAll" << "\n";
    cout << "[Exit] Exit(1~6제외 아무키나 누르세요)" << "\n";
}

int main() {
    DoublyLinkedList DLL;

    while(true) {
        menuPrint();
        char cmd;
        cin >> cmd;
        if(cmd == '1') {
            int value;
            cout << "제일 처음에 삽입 할 값 입력 : ";
            cin >> value;
            DLL.AddHead(value);
        }
        else if(cmd == '2') {
            int value;
            cout << "제일 끝에 삽입 할 값 입력 : ";
            cin >> value;
            DLL.AddTail(value);
        }
        else if(cmd == '3') {
            int value, idx;
            
            cout << "원하는 인덱스 : " ;
            cin >> idx;
            cout << "\n";
            cout << "삽입 할 값 입력 : ";
            cin >> value;
            DLL.AddSomewhere(DLL.FindByIndex(idx), value);
        }
        else if(cmd == '4') {
            DLL.DeleteHead();
        }        
        else if(cmd == '5') {
            DLL.DeleteTail();
        }
        else if(cmd == '6') {
            int idx;            
            cout << "삭제를 원하는 인덱스 : " ;
            cin >> idx;
            DLL.DeleteSomewhere(DLL.FindByIndex(idx));
        }
        else if(cmd == '7') {
            DLL.PrintAll();
        }
        else {
            exit(0);
        }
    }
}

 

백문이 불여일타 연결리스트는 확실히 그림 그려가면서 구현해보는게 훨씬 이해가 빠른 것 같다.

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐