在链表中删除

Question

所以我重新审视了双链表，发现我真的很笨，即使将问题缩小到 delete 运算符也无法解决问题。我还在玩模板，所以模板也可能有问题。在不删除节点的情况下打印工作正常。请告诉我哪里出了问题。

代码运行的结果只是它不打印任何东西。

template<typename T>
class DoubleLinkedList
{
    struct Node;
    Node *head;
    Node *tail;
public:
    DoubleLinkedList(Node *head = nullptr) : head(head) {
        if (head == nullptr) {
            tail = nullptr;
            return;
        }
        Node *tmp;
        for (tmp = head; tmp->next != nullptr; tmp = tmp->next);
        tail = tmp;
    }

    void addfront(T val) {
        Node *newnode = new Node(val, head);
        if (head == nullptr) {
            head = tail = newnode;
            return;
        }
        newnode->next = head;
        head->prev = newnode;
        head = newnode;
    }
    void addend(T val) {
        Node *newnode = new Node(val, nullptr, tail); 
        // There's probably a very obvious reason here, but my brain is busted and can't figure out 
        // what's wrong 
        if (head == nullptr) {
            head = tail = newnode;
            return;
        }
        tail->next = newnode;
        newnode->prev = tail;
        tail = newnode;
        
    }

    void del(T val) {
    
        for (Node *tmp = head; tmp != nullptr; tmp = tmp->next) {
            if (tmp->value == val) {
                if (tmp != head)
                    tmp->prev->next = tmp->next;
                else 
                    head = tmp->next;
                if (tmp->next != nullptr)
                    tmp->next->prev = tmp->prev;
                else
                    tail = tmp->prev;
                // print();
                delete tmp;  // delete not working, even when delete function is empty with just 
                             // delete head, it's a memory issue that my head can't wrap around
                break;
            }
        }
    }
    void print()
    {
        for (Node *tmp = head; tmp != nullptr; tmp = tmp->next)
            std::cout << tmp->value << ", ";
    }
    ~DoubleLinkedList() {
        Node *tmp;
        for (tmp = head; tmp->next != nullptr; tmp = tmp->next) 
            delete tmp->prev;
        delete tmp->prev;
        delete tmp;
    }
};

template<typename T>
struct DoubleLinkedList<T>::Node : DoubleLinkedList<T>
{
    T value;
    Node *prev;
    Node *next;

    Node(T val, Node *next = nullptr, Node *prev = nullptr) : 
    value(val), prev(prev), next(next) {}
};

int main()
{
    DoubleLinkedList<int> numlist;
    for (int i = 0; i < 10; i++)
        numlist.addend(i);
    numlist.del(0);
    numlist.print();
}

Answer 1

~DoubleLinkedList()逻辑全错了。当列表为空时，head 是 nullptr，因此在循环中访问 tmp->next 是 未定义的行为 。通常，您删除节点的方式很奇怪。它应该看起来更像这样：

~DoubleLinkedList() {
    Node *tmp, *next;
    for (tmp = head; tmp != nullptr; tmp = next) {
        next = tmp->next;
        delete tmp;
    }
}

这导致问题的原因是因为您有 DoubleLinkedList::Node 从 DoubleLinkedList 派生，所以 delete'ing 节点正在调用无效的 ~DoubleLinkedList() 析构函数。 Node 根本没有充分的理由派生自 DoubleLinkedList。

修复这两个问题后，其余代码对我来说工作正常，尤其是 del() 调用：

#include <iostream>
using namespace std;
 
template<typename T>
class DoubleLinkedList
{
    struct Node
    {
        T value;
        Node *prev;
        Node *next;

        Node(T val, Node *next = nullptr, Node *prev = nullptr) : 
            value(val), prev(prev), next(next) {}
    };

    Node *head;
    Node *tail;
public:
    DoubleLinkedList(Node *head = nullptr) : head(head) {
        if (head == nullptr) {
            tail = nullptr;
            return;
        }
        Node *tmp;
        for (tmp = head; tmp->next != nullptr; tmp = tmp->next);
        tail = tmp;
    }
 
    void addfront(T val) {
        Node *newnode = new Node(val, head);
        if (head == nullptr) {
            head = tail = newnode;
            return;
        }
        newnode->next = head;
        head->prev = newnode;
        head = newnode;
    }
 
    void addend(T val) {
        Node *newnode = new Node(val, nullptr, tail); 
        if (head == nullptr) {
            head = tail = newnode;
            return;
        }
        tail->next = newnode;
        newnode->prev = tail;
        tail = newnode;
    }

    void del(T val) {
        for (Node *tmp = head; tmp != nullptr; tmp = tmp->next) {
            if (tmp->value == val) {
                if (tmp != head)
                    tmp->prev->next = tmp->next;
                else 
                    head = tmp->next;
                if (tmp->next != nullptr)
                    tmp->next->prev = tmp->prev;
                else
                    tail = tmp->prev;
                // print();
                delete tmp;
                break;
            }
        }
    }

    void print()
    {
        for (Node *tmp = head; tmp != nullptr; tmp = tmp->next)
            std::cout << tmp->value << ", ";
        std::cout << "\n";
    }

    ~DoubleLinkedList() {
        Node *tmp, *next;
        for (tmp = head; tmp != nullptr; tmp = next) {
            next = tmp->next;
            delete tmp;
        }
    }
};

int main()
{
    DoubleLinkedList<int> numlist;
    for (int i = 0; i < 10; i++)
        numlist.addend(i);
    numlist.print();
    numlist.del(0);
    numlist.print();
}

Online Demo

Answer 2

无关。

对于带有显式“头”和“尾”指针的双链表，您选择了“朴素”的方法（一切都好！）。这主要会导致代码不是最优的，因为需要与这些指针和赋值进行大量比较。

标准实现使用哨兵，这也是一个节点，但具有特殊功能。基本上，这个哨兵节点的下一个指针是真正列表的开始，前一个指针是列表的结尾。

有了它，您可以更简单地使用标准函数。主要的工作马是“插入”和“擦除”功能。大多数其他东西都可以从中派生出来。

值得研究一下。

请参阅下面基于该设计方法的示例实现（仅部分测试，未完全完成）。我还添加了迭代器功能（甚至是低效和非标准的双向和随机访问）。

这可能有助于您对未来的工作和实践有所了解。

#include <iostream>
#include <iterator>
#include <vector>
#include <type_traits>
#include <initializer_list>
#include <algorithm>

// ------------------------------------------------------------------------------------------------
// This would be in a header file -----------------------------------------------------------------

// Type trait helper to identify iterators --------------------------------------------------------
template<typename T, typename = void> 
struct is_iterator { static constexpr bool value = false; };
template<typename T>
struct is_iterator<T, typename std::enable_if<!std::is_same<typename std::iterator_traits<T>::value_type, void>::value>::type> {
    static constexpr bool value = true;
};

// The List class ---------------------------------------------------------------------------------
template <typename T>
class List {
    // Sub class for a Node -----------
    struct Node {
        Node* next{};
        Node* previous{};
        T data{};
        Node(Node* const n, Node* const p, const T& d) : next(n), previous(p), data(d) {}
        Node(Node* const n, Node* const p) : next(n), previous(p) {}
        Node() {}
    };


    // Private list data and functions --------
    size_t numberOfElements{};
    Node* head{};
    void init() { head = new Node(); head->next = head; head->previous = head; numberOfElements = 0; }

public:
    struct iterator;    // Forward declaration

    // Constructor --------------------
    List() { init(); }
    explicit List(const size_t count, const T& value) { init(); insert(begin(), count, value); };
    explicit List(const size_t count) { init(); insert(begin(), count); }
    template <typename Iter>
    List(const Iter& first, const Iter& last) { init(); insert(begin(),first, last); }
    List(const List& other) { init(), insert(begin(), other.begin(), other.end()); };
    List(List&& other) : head(other.head), numberOfElements(other.numberOfElements) { other.init(); }
    List(const std::initializer_list<T>& il) { init(); insert(begin(), il.begin(), il.end()); }

    // Assignment ---------------------
    List& operator =(const List& other) { clear(); insert(begin(), other.begin(), other.end()); return *this; }
    List& operator =(List&& other) { clear(); head = other.head; numberOfElements = other.numberOfElements; other.init(); return *this; }
    List& operator =(const std::initializer_list<T>& il) { clear(); insert(begin(),il.begin(),il.end()); return *this; }

    void assign(const size_t count, const T& value) { clear(); insert(begin(), count, value); }
    template <typename Iter>
    void assign(const Iter& first, const Iter& last) { clear(); insert(begin(), first, last);}
    void assign(const std::initializer_list<T>& il) { clear(); insert(begin(), il.begin(), il.end()); }
    

    // Destructor ---------------------
    ~List() { clear(); }

    // Element Access -----------------
    T& front() { return *begin(); }
    T& back() { return *(--end()); }

    // Iterators ----------------------
    iterator begin() const { return iterator(head->next, head); }
    iterator end() const { return iterator(head, head); }

    // Capacity -----------------------
    size_t size() const { return numberOfElements; }
    bool empty() { return size() == 0; }

    // Modifiers ----------------------
    void clear();

    iterator insert(const iterator& insertBeforePosition, const T& value);
    iterator insert(const iterator& insertBeforePosition);
    template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool> = true>
    iterator insert(const iterator& insertBeforePosition, const Iter& first, const Iter& last);
    iterator insert(const iterator& insertBeforePosition, const size_t& count, const T& value);
    iterator insert(const iterator& insertBeforePosition, const std::initializer_list<T>& il);

    iterator erase(const iterator& posToDelete);
    iterator erase(const iterator& first, const iterator& last);


    void push_back(const T& d) { insert(end(), d); }
    void pop_back() { erase(--end()); };

    void push_front(const T& d) { insert(begin(), d); }
    void pop_front() { erase(begin()); };

    void resize(size_t count);
    void resize(size_t count, const T& value);

    void swap(List& other) { std::swap(head, other.head); std::swap(numberOfElements, other.numberOfElements); }

     // Operations --------------------
    void reverse();

    // Non standard inefficient functions --------------------------
    T& operator[](const size_t index) const { return begin()[index]; }

    // ------------------------------------------------------------------------
    // Define iterator capability ---------------------------------------------
    struct iterator {

        // Definitions ----------------
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        // Data -----------------------
        Node* iter{};
        Node* head{};

        // Constructor ----------------
        iterator(Node*const node, Node* const h) : iter(node), head(h) {};
        iterator() {};

        // Dereferencing --------------
        reference operator*() const { return iter->data; }
        reference operator->() const { return &**this; }

        // Arithmetic operations ------
        iterator operator++() { if (iter != head) iter = iter->next; return *this; }
        iterator operator++(int) { iterator tmp = *this; ++* this; return tmp; }
        iterator operator--() { if (iter != head->next) iter = iter->previous; return *this; }
        iterator operator--(int) { iterator tmp = *this; --* this; return tmp; }

        iterator operator +(const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)++temp; else while (k++)--temp; return temp;
        }
        iterator operator +=(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)++* this; else while (k++)--* this; return *this;
        };
        iterator operator -(const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)--temp; else while (k++)++temp; return temp;
        }
        iterator operator -=(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)--* this; else while (k++)++* this; return *this;
        };
        // Comparison -----------------
        bool operator ==(const iterator& other) const { return iter == other.iter; };
        bool operator !=(const iterator& other) const { return iter != other.iter; };
        bool operator < (const iterator& other) const { return other.iter - iter < 0; };
        bool operator <= (const iterator& other) const { return other.iter - iter <= 0; };
        bool operator > (const iterator& other) const { return other.iter - iter > 0; };
        bool operator >= (const iterator& other) const { return other.iter - iter >= 0; };

        // Special non standard functions -----------------
        difference_type operator-(const iterator& other) const;
        reference operator[] (const size_t index);
    };
};


// ------------------------------------------------------------------------------------------------
// Implementation of list functions. This would normally go into a TCC file -----------------------

// List class functions ---------------
template <typename T>
void List<T>::clear() {

    for (Node* nextNode{}, * currentNode(head->next); currentNode != head; currentNode = nextNode) {
        nextNode = currentNode->next;
        delete currentNode;
    }
    init();
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const T& value)
{
    Node* nodeInsertBeforePosition = insertBeforePosition.iter;
    Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous, value);
    nodeInsertBeforePosition->previous = newNode;
    (newNode->previous)->next = newNode;
    ++numberOfElements;
    return iterator(newNode, head);
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition)
{
    Node* nodeInsertBeforePosition = insertBeforePosition.iter;
    Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous);
    nodeInsertBeforePosition->previous = newNode;
    (newNode->previous)->next = newNode;
    ++numberOfElements;
    return iterator(newNode, head);
}

template <typename T>
template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool>>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const Iter& first, const Iter& last) {
    iterator result(insertBeforePosition.iter, head);
    if (first != last) {
        result = insert(insertBeforePosition, *first);
        Iter i(first);
        for (++i; i != last; ++i)
            insert(insertBeforePosition, *i);
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const size_t& count, const T& value) {

    iterator result(insertBeforePosition.iter, head);
    if (count != 0u) {
        result = insert(insertBeforePosition, value);
        for (size_t i{ 1u }; i < count; ++i)
            insert(insertBeforePosition, value);
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const std::initializer_list<T>& il) {
    return insert(insertBeforePosition, il.begin(), il.end());
}

template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& posToDelete) {

    iterator result = posToDelete;
    ++result;

    Node* nodeToDelete = posToDelete.iter;

    if (nodeToDelete != head) {

        nodeToDelete->previous->next = nodeToDelete->next;
        nodeToDelete->next->previous = nodeToDelete->previous;

        delete nodeToDelete;
        --numberOfElements;
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& first, const List<T>::iterator& last) {
    iterator result{ end() };
    if (first == begin() && last == end())
        clear();
    else {
        while (first != last)
            first = erase(first);
        result = last;
    }
    return result;
}

template <typename T>
void List<T>::resize(size_t count) {
    if (numberOfElements < count)
        for (size_t i{ numberOfElements }; i < count; ++i)
            insert(end());
    else
        while (count--)
            pop_back();
}
template <typename T>
void List<T>::resize(size_t count, const T& value) {
    if (numberOfElements < count)
        for (size_t i{ numberOfElements }; i < count; ++i)
            insert(end(),value);
    else
        while (count--)
            pop_back();
}
template <typename T>
void List<T>::reverse() {
    const Node* oldHead = head;

    for (Node* nptr = head; ; nptr = nptr->previous) {
        std::swap(nptr->next, nptr->previous);
        if (nptr->previous == oldHead) // Previous was the original next
            break;
    }
}

// ------------------------------------
// Iterator functions -----------------
template <typename T>
typename List<T>::iterator::difference_type List<T>::iterator::operator-(const iterator& other) const {

    difference_type result{};
    Node* nptr = head;

    int indexThis{ -1 }, indexOther{ -1 }, index{};

    do {
        nptr = nptr->next;
        if (nptr == iter)
            indexThis = index;
        if (nptr == other.iter)
            indexOther = index;
        ++index;
    } while (nptr != head);

    if (indexThis >= 0 and indexOther >= 0)
        result = indexThis - indexOther;
    return result;
}
template <typename T>
typename List<T>::iterator::reference List<T>::iterator::operator[] (const size_t index) {
    Node* nptr = head->next;
    for (size_t i{}; i < index and nptr != head; ++i, nptr = nptr->next)
        ;
    return nptr->data;
}

// ------------------------------------------------------------------------------------------------
// This would be in a cpp file --------------------------------------------------------------------
int main() {
    List<int> list{ 1,2,3,4,5 };

    std::cout << "Original List\n";
    for (int i : list) std::cout << i << ' '; std::cout << '\n';

    std::cout << "\nInternal reverse function. Kust swap ointers in Node\n";
    list.reverse();
    for (int i : list) std::cout << i << ' '; std::cout << '\n';

    // Sort it again
    std::cout << "\nSort it again (Values will be copied)\n";
    std::sort(list.begin(), list.end());
    for (int i : list) std::cout << i << ' '; std::cout << '\n';

    std::cout << "\nReverse function from algorithm library. Reverse values with copy\n";
    std::reverse(list.begin(), list.end());
    for (int i : list) std::cout << i << ' '; std::cout << '\n';

    // Use reverse iterators
    std::cout << "\nBuild and use reverse iterators\n";
    std::reverse_iterator<List<int>::iterator> riter = std::make_reverse_iterator(list.end());
    std::reverse_iterator<List<int>::iterator> riterEnd = std::make_reverse_iterator(list.begin());

    for (; riter != riterEnd; ++riter)
        std::cout << *riter << ' '; std::cout << '\n';

    return 0;
}

在链表中删除

Delete in Linked List

c++

linked-list

doubly-linked-list