双向链表在第 n 个位置添加节点

Question

我需要帮助在我的双向链表中添加一个节点部分。我已经干掉了运行我的程序，它看起来很完美，但在添加第二个或第三个节点时崩溃了。我想要一个合乎逻辑的理由为什么会这样。任何人？这是我的代码。

class node
    {
    public:
        int data;
        node* next;
        node* previous;
    };

    class linklist
    {
    private:
        node* current;
        node* head;
        node* tail;
        int count;
        int size;

    public:
        linklist() : head(NULL), tail(NULL), size(1) {}

    void addNthNode(int Data, unsigned int position)
        {
            node* currentNew = new node;
            currentNew->data = Data;

            if (position == 1)
            {
                currentNew->next = head;
                currentNew->previous = NULL;
                head = currentNew;
                return;
            }

            node* temp1 = head;
            for (int i = 1; i < position - 1; i++)
                temp1 = temp1->next;

            node* temp2 = temp1->next;

            currentNew->previous = temp1;
            currentNew->next = temp2;
        }

    int getSizeOfList()
        {
            node* temp = head;
            while (temp->next != NULL)
            {
                temp = temp->next;
                ++size;
            }
            return size;
        }

    void main()
    {
        linklist l;

        l.addNthNode(1, 1);
        l.addNthNode(2, 2);
        l.addNthNode(3, 3);

        l.printList();
        cout << "\nSize of list : " << l.getSizeOfList() << endl << endl;

    }

Answer 1

插入新节点时，您不会更新所选位置任何现有节点的 next 和 previous 字段，因此它们指向新节点。您也没有增加列表的 count 和 size 字段，或者在列表末尾插入时更新其 tail 字段。

试试这个：

class node
{
public:
    int data;
    node* next;
    node* previous;

    node(int value = 0) : data(value), next(NULL), previous(NULL) {}
};

class linklist
{
private:
    node* head;
    node* tail;
    int size;

public:
    linklist() : head(NULL), tail(NULL), size(0) {}

    void addNthNode(int Data, unsigned int position)
    {
        node* currentNew = new node(Data);

        if (position <= 1)
        {
            currentNew->next = head;
            if (head)
                head->previous = currentNew;
            head = currentNew;
        }

        if (position >= size)
        {
            currentNew->previous = tail;
            if (tail)
                tail->next = currentNew;
            tail = currentNew;
        }

        if ((position > 1) && (position < size))
        {
            node *temp = head;
            while (position-- > 1)
                temp = temp->next;

            currentNew->next = temp;

            if (temp->previous)
                temp->previous->next = currentNew;
            temp->previous = currentNew;
        }

        ++size;
    }

    int getSizeOfList()
    {
        return size;
    }

    void printList()
    {
        //...
    }
};

int main()
{
    linklist l;

    l.addNthNode(1, 1);
    l.addNthNode(2, 2);
    l.addNthNode(3, 3);

    l.printList();
    std::cout << "\nSize of list : " << l.getSizeOfList() << std::endl << std::endl;

    return 0;
}

话虽如此，您应该认真考虑使用 std::list 而不是手动实施：

#include <list>

class linklist
{
private:
    std::list<int> l;

public:
    void addNthNode(int Data, unsigned int position)
    {
        std::list<int>::iterator iter = l.begin();
        std::advance(iter, position-1);
        l.insert(iter, Data);
    }

    int getSizeOfList()
    {
        return l.size();
    }

    void printList()
    {
        //...
    }
};

int main()
{
    linklist l;

    l.addNthNode(1, 1);
    l.addNthNode(2, 2);
    l.addNthNode(3, 3);

    l.printList();
    std::cout << "\nSize of list : " << l.getSizeOfList() << std::endl << std::endl;

    return 0;
}

双向链表在第 n 个位置添加节点

Doubly linked list adding node at nth location

doubly-linked-list