[자료구조]DblLinkedList - 이중연결리스트 사용

이중연결리스트 노드 클래스

#pragma once
#include <iostream>
 
class DblNode
{
private:
    int data;
public:
    DblNode* prev;
    DblNode* next;
    DblNode(int val = 0) :data(val),prev(NULL), next(NULL) {}
    DblNode* getPrev() { return prev; }
    DblNode* getNext() { return next; }
    void setPrev(DblNode* p) {
        prev = p;
    }
    void setNext(DblNode* p) {
        next = p;
    }
    void display() { printf(" <%2d>", data); }
 
    //이중연결리스트를 사용하면 앞, 뒤로 접근이 가능함
    void insertNext(DblNode* p) {
        if (p != NULL) {
            p->prev = this; //새로 들어오는 노드p의 prev가 this를 가르킴.
            p->next = this->next; //새로 들어오는 노드p의 next가 현재노드의 next를 가르킴.
            if (next != NULL) next->prev = p; //현재노드의 next의 prev가 p를 가르킴.
            next = p; //현재노드의 next가 p를 가르킴.
        }
    }
 
    //이중연결리스트를 사용해서 자기자신에 대한 접근이 가능해짐. 따라서 자기자신을 삭제할 수 있음.
    DblNode* remove() {
        if (prev != NULL) prev->next = this->next; //현재 노드의 prev의 next가 현재 노드의 next를 가르킴.
        if (next != NULL) next->prev = this->prev; //현재 노드의 next의 prev가 현재 노드의 prev를 가르킴.
        return this;
    }
};

이중연결리스트 리스트 클래스

#pragma once
#include "DblNode.h"
 
class DblLinkedList
{
private:
    DblNode org;
public:
    DblLinkedList() :org(0) {}
    ~DblLinkedList() { clear(); }
    void clear() {
        while (!isEmpty()) delete remove(0);
    }
 
    DblNode* getHead() { return org.getNext(); }
    bool isEmpty() { return getHead() == NULL; }
 
    DblNode* getEntry(int pos) {
        DblNode* n = &org;
        for (int i = -1; i < pos; i++, n = n->getNext()) //헤드노드의 인덱스는 -1.
            if (n == NULL) break;
        return n;
    }
 
    void insert(int pos, DblNode* n) {
        DblNode* prev = getEntry(pos-1);
        if (prev != NULL)
            prev->insertNext(n);
    }
 
    DblNode* remove(int pos) {
        DblNode* n = getEntry(pos);
        return n->remove();
    }
 
    void display() {
        for (DblNode* n=getHead(); n != NULL; n = n->getNext())
            n->display();
    }
};