[DS] Linked List 구현(3) - Double Linked List

1. 그림

[그림1] Double Linked List - 초기상태

[그림2] Double Linked List - data삽입후 상태

 

 

 

2. 전체 코드

DoubleLinkedList.h

#ifndef DOUBLE_LINKED_LIST
#define DOUBLE_LINKED_LIST
#include<malloc.h>

struct Node {
    int data;
    Node* prev;                 // 양방향 연결을 위해 prev 추가
    Node* next;
};

class DoubleLinkedList {
private:
    Node* head;
    Node* tail;                 // 후방삽입을 위한 tail Node 추가
public:
    DoubleLinkedList();
    Node* getHead() { return head; }
    Node* getTail() { return tail; }
    Node* createNode(int data);

    void pushFront(int data);
    void pushBack(int data);    // 후방삽입 기능 추가
    void removeNode(int data);
    void removeAllNodes();
};

#endif // DOUBLE_LINKED_LIST

 

DoubleLinkedList.cpp

#include "DoubleLinkedList.h"

DoubleLinkedList::DoubleLinkedList() {
    head = createNode(0);
    tail = createNode(0);
    head->next = tail;
    tail->prev = head;
}

Node* DoubleLinkedList::createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;

    return newNode;
}

void DoubleLinkedList::pushFront(int data) {
    Node* newNode = createNode(data);
    newNode->prev = head;
    newNode->next = head->next;
    head->next->prev = newNode;
    head->next = newNode;
}

void DoubleLinkedList::pushBack(int data) {
    Node* newNode = createNode(data);
    newNode->prev = tail->prev;
    newNode->next = tail;
    tail->prev->next = newNode;
    tail->prev = newNode;
}

void DoubleLinkedList::removeNode(int data) {
    Node* cur = head->next;

    while (cur != tail) {
        if (cur->data == data) {
            Node* deleteNode = cur;
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            cur = cur->next;
            free(deleteNode);
        }
        else 
            cur = cur->next;
    }
}

void DoubleLinkedList::removeAllNodes() {
    Node* cur = head;
    while (cur != NULL) {
        Node* temp = cur;
        cur = cur->next;
        free(temp);
    }
    head = NULL;
}

 

main.cpp

#include<iostream>
#include "DoubleLinkedList.h"
using namespace std;

void printLinkedList(DoubleLinkedList* linkedList) {
    printf("[dmy head]<->");
    Node* cur = linkedList->getHead()->next;
    for (; cur != linkedList->getTail(); cur = cur->next)
        printf("%d<->", cur->data);
    printf("[dmy tail]\n");
}

int main() {
    DoubleLinkedList doubleLinkedList;
    printLinkedList(&doubleLinkedList);	// [dmy head]<->[dmy tail]

    doubleLinkedList.pushFront(3);
    doubleLinkedList.pushFront(2);
    doubleLinkedList.pushFront(1);
    doubleLinkedList.pushBack(4);
    doubleLinkedList.pushBack(5);
    printLinkedList(&doubleLinkedList);	// [dmy head]<->1<->2<->3<->4<->5<->[dmy tail]

    doubleLinkedList.removeNode(3);
    printLinkedList(&doubleLinkedList);	// [dmy head]<->1<->2<->4<->5<->[dmy tail]

    doubleLinkedList.removeNode(1);
    printLinkedList(&doubleLinkedList);	// [dmy head]<->2<->4<->5<->[dmy tail]

    doubleLinkedList.removeNode(2);
    doubleLinkedList.removeNode(4);
    doubleLinkedList.removeNode(5);
    printLinkedList(&doubleLinkedList);	// [dmy head]<->[dmy tail]

    doubleLinkedList.removeAllNodes();

    return 0;
}