在特定位置插入节点

Question

我需要在链表的给定位置插入一个节点。有没有更好的方法呢？这是我的代码：

struct node
{
    int data;
    node* next;
};
void InsertNodeAtPosition(node *& first , int x , int position)
{

//0 based indexing
    int i = 0;
    node *q = new node;
    q = first;
    while (i != position - 1)
    {
      q = q->next;
      i++;
    }
    node *t = new node;
    t->data = x;
    t->next = q->next;
    q->next = t;
}

我测试了它 works.But 我想在进入下一个之前真正擅长链表 chapter.Thanks！

Answer 1

Is there any better way to do it?

当然，最好不要泄漏内存：

node *q = new node;
q = first;

至于算法本身：对于单向链表，将元素插入特定位置的更好方法是将指向前一个节点的指针作为参数而不是头和位置传递。这样就不需要线性搜索。但是对于给定的参数，您尝试的算法是最优的。

至于class设计：更好的方法是为列表实现迭代器并使用它们而不是指向节点的指针，以便可以使用标准算法。并遵循 5 法则，以符合 RAII 模式和容器概念。并使用模板来支持不同的数据类型。并支持使用自定义分配器，以便用户可以控制节点的分配方式。

至于更高层次的设计：使用单链表的更好方法是不做任何这些，因为标准库已经提供了数据结构的实现：std::forward_list.

Answer 2

你写的函数是错误的，有内存泄漏和未定义的行为。

例如，首先指针q 被分配了动态分配内存的地址，然后它被重新分配了指针first 的值。所以分配内存的地址丢失，内存无法释放

node *q = new node;
q = first;

此外，通过引用传递给函数的指针 first 在函数内永远不会更改。

在 while 循环中你没有检查指针 q 是否等于 nullptr

while (i != position - 1)
{
  q = q->next;
  i++;
}

所以这个声明

q = q->next;

调用未定义的行为。

另外，如果 position 等于 0 那么条件

i != position - 1

将评估为真，您将再次遇到未定义的行为。

函数可以这样写

void InsertNodeAtPosition( node * &first , int x , size_t position )
{
    node **current = &first;

    while ( *current && position-- )
    {
        current = &( *current )->next;
    }

    *current = new node { x, *current };
}

在特定位置插入节点

Insert node at specific position

c++

recursion

pointers

linked-list

singly-linked-list