Doubly Linked List - Sentinel Nodes, prev

3번문제 ADT

list.h

class Node{
private:
    int data;
    Node *next;
    Node *prev;
    friend class LinkedList;
};

class LinkedList {
public:
    LinkedList() {
        head = new Node;
        tail = new Node;
        tail->prev = head;
        head->next = tail;
    }
    void prepend(int data);
    void append(int data);
    int length();
    void print();
    void printReverse();
private:
    Node *head;
    Node *tail;

};

list.cpp

#include "list.h"
#include "iostream"

void LinkedList::prepend(int data) {
    Node *newNode = new Node();
    newNode->data = data;
    newNode->prev = head;
    newNode->next = head->next;
    head->next->prev = newNode;
    head->next = newNode;
}

void LinkedList::append(int data) {
    Node *newNode = new Node();
    newNode->data = data;
    newNode->prev = tail->prev;
    newNode->next = tail;
    tail->prev->next = newNode;
    tail->prev = newNode;
}

int LinkedList::length() {
    int count = 0;
    Node* currentNode = head->next;
    while(currentNode != tail) {
        count ++;
        currentNode = currentNode->next;
    }
    return count;
}

void LinkedList::print() {
    Node* currentNode = head->next;
    while (currentNode != tail) {
        std::cout << currentNode->data << " ";
        currentNode = currentNode->next;
    }
    std::cout << "\n";
}
void LinkedList::printReverse() {
    Node* currentNode = tail->prev;
    while (currentNode != head) {
        std::cout << currentNode->data << " ";
        currentNode = currentNode->prev;
    }
    std::cout << "\n";
}

• 더블 링크드 리스트 구현의 편리함을 위해 head와 tail은 data를 포함하지 않는 sentinel node(종료점 감시 노드)를 사용한다.
• head의 prev와 tail의 next는 nullptr로 지정한다.
• print(), printReverse() 구현 시 currentNode가 각각 tail, head이기 전까지 출력하면 된다.
• length()도 currentNode가 tail일 때까지 count하면 된다.