问简单祈使双链接列表
EN

Code Review用户

提问于 2016-10-29 13:33:55

回答 1查看 293关注 0票数 0

我已经开始学习C++，并且还在做我的第一个程序。这是我上一篇文章的续集。

我最初的目的是在专业层面上列出一份相互关联的清单。但现在已经将其更改为双链接列表，以简化代码。它实现了几个公共功能，可以显着地提高列表的可用性。

我还试图实现一个内部迭代器。但是没有看到为内部使用的双向迭代器来代替getNode的好处。

虽然我认为我改进了我上一篇文章中提到的所有问题。我主要集中在执行哨兵。我不认为这是哨兵，因为它所做的不只是我的结束条件。所以我很想得到一些关于我的实施情况的反馈。但是所有的批评都是被通缉的。

#include <iostream>

template <class T>
class LinkedList {
private:
    class Node {
    public:
        Node* next;
        Node* prev;
        T data;
        // For the sentinal
        Node(): data('\0'), prev(this), next(this) {}
        Node(T data, Node* before)
                : data(data) {
            prev = before;
            next = before->next;
            prev->next = this;
            next->prev = this;
        }
        ~Node() {
            prev->next = next;
            next->prev = prev;
        }
        Node(Node const&)            = delete;
        Node& operator=(Node const&) = delete;
    };
    Node sentinal;
    Node* getNode(int index) {
        if (index >=  0) {
            int i = 0;
            for (Node* node = sentinal.next; node != &sentinal; node = node->next) {
                if (i == index) {
                    return node;
                }
                i++;
            }
        } else {
            int i = -1;
            for (Node* node = sentinal.prev; node != &sentinal; node = node->prev) {
                if (i == index) {
                    return node;
                }
                i--;
            }
        }
        throw std::out_of_range("List doesn't contain that item.");
    }
public:
    LinkedList() {}
    ~LinkedList() {
        clear();
    }
    LinkedList(LinkedList const&)            = delete;
    LinkedList& operator=(LinkedList const&) = delete;

    void clear() {
        while (sentinal.next != &sentinal) {
            delete sentinal.next;
        }
    }

    int length() {
        int length = 0;
        for (Node* node = sentinal.next; node != &sentinal; node = node->next) {
            length += 1;
        }
        return length;
    }

    void append(T data) {
        new Node(data, sentinal.prev);
    }

    T get(int index) {
        return getNode(index)->data;
    }

    void insert(T data, int index) {
        new Node(data, getNode(index)->prev);
    }

    T pop(int index=-1) {
        Node* node = getNode(index);
        T data = node->data;
        delete node;
        return data;
    }
};

int main() {
    LinkedList<char> list;
    list.append('h');
    list.append('l');
    list.append('l');
    list.append('l');
    list.append('o');
    list.insert('e', 1);
    std::cout << list.pop(2) << list.get(-1) << '\n';
    for (int i=0; i < list.length(); i++) {
        std::cout << list.get(i);
    }
    std::cout << '\n';
    list.clear();
    std::cout << list.length() << '\n';
}