双向链表C++的insert方法

Question

我正在用 C++ 实现双向链表，我一直试图让我的插入方法工作但没有成功。 class 应该包含两个节点指针：一个指向列表的头部，一个指向列表的尾部。如果列表为空，则它们都应指向 nullptr。 insert 方法应该在给定索引处获取一个值并将其添加到列表中，并增加一个元素的大小。我的代码是：

#include <iostream>
#include <vector>
using namespace std;

struct Node
{
    int value;
    Node *next;
    Node *prev; //previous node pointer
    Node(int v) : value(v), next(nullptr), prev(nullptr) {}
};

class LinkedList
{
private:
    Node *head;
    Node *tail;
    Node *prev;

    Node *get_node(int index)
    {
        if (index < 0 or index >= size)
        {
            throw range_error("IndexError: Index out of range");
        }

        Node *current = head;
        for (int i = 0; i < index; i++)
        {
            current = current->next;
        }
        return current;
    }

public:
    int size;
    LinkedList()
    {
        head = nullptr;
        tail = nullptr;
    }

    int length()
    {
        Node *current = head;
        int count = 0;

        while (current != nullptr)
        {
            count++;
            current = current->next;
        }

        cout << "Length of list is " << count << endl;
        return count;
    }

    void append(int value)
    {
        Node *new_node = new Node(value);

        if (head == nullptr)
        {
            head = new_node;
            head->prev = nullptr;
            new_node->next = tail;
        }
        else if (tail == nullptr)
        {
            tail = new_node;
            new_node->next = nullptr;
        }
    }

    void print()
    {
        Node *current = head;
        Node *prev;
        cout << "[";
        if (current->next == NULL)
        {
            cout << current->value;
            cout << "]";
        }
        else
        {

            while (current->next != nullptr)
            {
                cout << current->value;
                cout << ", ";
                prev = current;
                current = current->next;
            }
            cout << current->value << "]" << endl;
        }
    }

    ~LinkedList()
    {
        Node *current;
        Node *next;

        current = head;

        while (current != nullptr)
        {
            next = current->next;
            delete current;
            current = next;
        }
    }

    int &operator[](int index)
    {
        return get_node(index)->value;
    }

    void insert(int val, int index)
    {
        Node *current = new Node(val);
        Node *prev = get_node(index - 1);
        Node *next = current->next;
        prev->next = current;
    }
};

int main()
{
    LinkedList a;
    a.append(1); // Appending elements to list
    a.append(2);
    a.append(3);
    a.append(4);
    a.append(5);
    a.print(); // [1, 2, 3, 4, 5]
    a.insert(3, 1);
    a.print(); 
};

这给了我错误

libc++abi.dylib: terminating with uncaught exception of type std::range_error: IndexError: Index out of range
Abort trap: 6

Answer 1

嗯，insert 中的明显问题是它调用 get_node 测试 size 成员，但任何地方都没有更新 size。

但是，从根本上说，您的 append 函数是错误的。它应该是一个 class 不变量，链表要么是空的并且它的头和尾都是 nullptrs，要么它应该有一个有效的 head 和一个有效的 tail.

您的 append 函数不强制执行此不变量。它尝试处理两种情况，一种是头部为空，另一种是尾部为空。问问自己这两个案例是否有意义。

重写 append 使列表为空或具有有效的头和尾。

Answer 2

我试图修复你所有的方法，可能成功了，至少当前的测试示例正在打印正确答案：

Try it online!

#include <iostream>
#include <vector>
using namespace std;

struct Node
{
    int value;
    Node *next;
    Node *prev; //previous node pointer
    Node(int v) : value(v), next(nullptr), prev(nullptr) {}
};

class LinkedList
{
private:
    Node *head;
    Node *tail;

    Node *get_node(int index)
    {
        if (index < 0)
            throw range_error("IndexError: Index out of range");

        Node *current = head;
        for (int i = 0; i < index; i++) {
            if (!current)
                break;
            current = current->next;            
        }

        if (!current)
            throw range_error("IndexError: Index out of range");

        return current;
    }

public:
    LinkedList()
    {
        head = nullptr;
        tail = nullptr;
    }

    int length()
    {
        Node *current = head;
        int count = 0;

        while (current != nullptr)
        {
            count++;
            current = current->next;
        }

        cout << "Length of list is " << count << endl;
        return count;
    }

    void append(int value)
    {
        Node *new_node = new Node(value);

        if (head == nullptr)
        {
            head = new_node;
            tail = head;
        }
        else
        {
            tail->next = new_node;
            new_node->prev = tail;
            tail = new_node;
        }
    }

    void print()
    {
        Node *current = head;
        cout << "[";
        if (current->next == NULL)
        {
            cout << current->value;
            cout << "]";
        }
        else
        {

            while (current->next != nullptr)
            {
                cout << current->value;
                cout << ", ";
                current = current->next;
            }
            cout << current->value << "]" << endl;
        }
    }

    ~LinkedList()
    {
        Node *current;
        Node *next;

        current = head;

        while (current != nullptr)
        {
            next = current->next;
            delete current;
            current = next;
        }
    }

    int &operator[](int index)
    {
        return get_node(index)->value;
    }

    void insert(int val, int index)
    {
        Node *node = new Node(val);
        if (index == 0) {
            if (!head) {
                head = node;
                tail = head;
            } else {
                node->next = head;
                head->prev = node;
                head = node;
            }
        } else {
            Node *prev = get_node(index - 1);
            Node *next = prev->next;
            prev->next = node;
            node->prev = prev;
            node->next = next;
            if (next)
                next->prev = node;
            if (prev == tail)
                tail = node;
        }
    }
};

int main()
{
    LinkedList a;
    a.append(1); // Appending elements to list
    a.append(2);
    a.append(3);
    a.append(4);
    a.append(5);
    a.print(); // [1, 2, 3, 4, 5]
    a.insert(3, 1);
    a.print(); 
};

输出：

[1, 2, 3, 4, 5]
[1, 3, 2, 3, 4, 5]

双向链表C++的insert方法

insert method for doubly linked list C++

c++

doubly-linked-list