双方向リストの実装

やっぱりアルゴリズムとデータ構造の知識って重要だよねってことで
プログラミングの基礎を勉強しなおしてます。
C言語で単方向リストの実装 - Gobble up pudding
この続きです。
この実装もArrayDequeやLinkedListが備えているメソッドを実装しきれてません。

この実装のポイントは先頭にダミーノードを用意して、prevやnextは初期状態では自分自身を指します。
ちなみにdummyのprevは末尾で、nextは先頭ノードを表します。
実際にダミーなしで書いてみるとわかりますが、ダミーがないとif文が増えて面倒です。

ソース

C++

#include <iostream>
#include <string>
#include <stdexcept>

using namespace std;

template <typename T>
struct Node
{
    T value_;
    Node *prev_;
    Node *next_;
    Node()
    {
        prev_ = this;
        next_ = this;
    }
    Node(T value, Node *prev, Node *next)
    {
        value_ = value;
        prev_ = prev;
        next_ = next;
    }
};

template <typename T>
class DoublyLinkedList
{
private:
    Node<T> *dummy_;
    int size_;

public:
    DoublyLinkedList()
    {
        dummy_ = new Node<T>();
        size_ = 0;
    }

    ~DoublyLinkedList()
    {
        clear();
    }
    
    void add(T v, Node<T> *node)
    {
        // insert a new node between the current node and the next of current node
        Node<T> *newNode = new Node<T>(v, node, node->next_);
        node->next_->prev_ = newNode;
        node->next_ = newNode;
        // update the current node
        node = newNode;
        size_++;
    }

    void push_front(T value)
    {
        Node<T> *cur = dummy_;
        add(value, cur);
    }

    void push_back(T value)
    {
        Node<T> *cur = dummy_->prev_;
        add(value, cur);
    }

    bool empty()
    {
        return dummy_->next_ == dummy_;
    }
    
    T remove(Node<T> *node)
    {
        if (empty())
        {
            throw std::logic_error("node is empty!");
        }
        T ret = node->value_;
        node->prev_->next_ = node->next_;
        node->next_->prev_ = node->prev_;
        delete node;
        node = node->prev_;
        size_--;
        return ret;
    }

    T pop_front()
    {
        Node<T> *cur = dummy_->next_;
        return remove(cur);
    }
    
    T pop_back()
    {
        Node<T> *cur = dummy_->prev_;
        return remove(cur);
    }

    void dump()
    {
        Node<T> *ptr = dummy_->next_;
        while (ptr != dummy_)
        {
            cout << ptr->value_ << ' ';
            ptr = ptr->next_;
        }
        cout << '\n';
    }
    
    void clear()
    {
        while(!empty())
        {
            pop_front();
        }        
    }
    
    int size()
    {
        return size_;
    }
};

int main()
{
    DoublyLinkedList<int> list;
    list.push_front(13);
    list.push_front(7);
    list.push_front(10);
    cout << "size: " << list.size() << '\n';
    list.dump();

    list.push_back(11);
    cout << "size: " << list.size() << '\n';
    list.dump();

    cout << "remove: " << list.pop_back() << '\n';
    cout << "size: " << list.size() << '\n';
    list.dump();

    cout << "remove: " << list.pop_front() << '\n';
    cout << "size: " << list.size() << '\n';
    list.dump();
    
    return 0;
}

Java

package algo.dataStructure;

public class DoublyLinkedList<T> {
    static class Node<T> {
        public T value;
        public Node<T> next;
        public Node<T> prev;

        public Node() {
        	this.prev = this;
        	this.next = this;
        }
        
        public Node(T value, Node<T> prev, Node<T> next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }
    
    private Node<T> dummy;
    private int size;

    public DoublyLinkedList() {
        dummy = new Node<>();
        size = 0;
    }
    
    private void add(T v, Node<T> node) {
    	Node<T> newNode = new Node<>(v, node, node.next);
    	// insert a new node between the current node and the next of current node
    	node.next.prev = newNode;
    	node.next = newNode;
    	// update the current node
    	node = newNode;
    }

    public void pushFront(T v) {
    	Node<T> current = dummy;
    	add(v, current);
        size++;
    }

    public void pushBack(T v) {
        Node<T> current = dummy.prev;
        add(v, current);
        size++;
    }

    private boolean empty() {
        return dummy.next == dummy;
    }
    
    public T remove(Node<T> node) {
        if (empty()) {
        	throw new IllegalStateException("node is empty!");
        }
    	T ret = node.value;
    	node.prev.next = node.next;
    	node.next.prev = node.prev;
    	node = node.prev;
    	size--;
        return ret;
    }
    
    public T popFront() {
    	Node<T> current = dummy.next;
    	return remove(current);
    }

    public T popBack() {
    	Node<T> current = dummy.prev;
    	return remove(current);
    }

    public void dump() {
        Node<T> n = dummy.next;
        while (n != dummy) {
            System.out.print(n.value + " ");
            n = n.next;
        }
        System.out.println();
    }
    
    public int size() {
    	return this.size;
    }
    
    public static void main(String args[]) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
        list.pushFront(13);
        list.pushFront(7);
        list.pushFront(10);
        System.out.println("size: " + list.size());
        list.dump();

        list.pushBack(11);
        System.out.println("size: " + list.size());
        list.dump();

        System.out.println("remove: " + list.popBack());
        System.out.println("size: " + list.size());
        list.dump();

        System.out.println("remove: " + list.popFront());
        System.out.println("size: " + list.size());
        list.dump();
    }
}

参考文献

明解Javaによるアルゴリズムとデータ構造