在 C 的链表中的特定位置插入一个节点（仅限）

Question

任何人都可以帮助我哪里出错了！！！，我是编程的初学者，我是 DSA 的新手，我找不到我的错误，这是代码通过它：

This is the outline of my question, hope it is clear! :)


sample input : 3 16 13 7 1 2
3 is the number of elements to input into a linked list
so 16 13 7 are elements of the linked list initially
1 is the element I'm interested to insert
2 is the position where I want to insert the element 1
so the expected output will be:
sample output: 16 13 1 7

The problem I'm facing :


The output I'm getting is: 13 1 7
So the problem is not every element in the list is getting returned, please help !!!

This is the code I tried, any suggestions are encouraged, :)

   struct SinglyLinkedListNode 
  {
        int data;
        SinglyLinkedListNode* next;
  };

    SinglyLinkedListNode* insertNodeAtPosition(SinglyLinkedListNode* head, int data, int position) 
{
    int i = 0;
    SinglyLinkedListNode *pcurr, *pnew;

    pnew = (SinglyLinkedListNode*)malloc(sizeof(SinglyLinkedListNode));
    if(position == 0)
    {
        pnew->data = data;
        pnew->next = head->next;
        head = pnew;
        return head;
    }
    if(head == NULL)
    {
        pnew ->data = data;
        return pnew;
    }
    else
    {
        do 
        {
            pcurr = head;
            pcurr = pcurr->next;
            head = head->next;
            i++;
        }
        while (i != position-1);
        pnew->next = pcurr->next;
        pnew->data = data;
        pcurr->next = pnew;
        return head;
    }
}

如果有人建议一个好的可视化平台来逐行查看我们的代码，尤其是 c ，我会很高兴，就像 python.

Answer 1

 struct SinglyLinkedListNode 
  {
        int data;
        SinglyLinkedListNode* next;
  };

    SinglyLinkedListNode* insertNodeAtPosition(SinglyLinkedListNode* head, int data, int position) 
{
    int i = 0;
    SinglyLinkedListNode *temp1, *pcurr, *prev;
    temp1 = (SinglyLinkedListNode *)malloc(sizeof(SinglyLinkedListNode));
    prev = (SinglyLinkedListNode*)malloc(sizeof(SinglyLinkedListNode));
    if(position == 0&&head!=NULL)
    {
        temp1->data = data;
        temp1->next = head;     //new node's next will point to head and new node will become the new head
        head = temp1;          //since the insertion is made at start, new node(temp1) will becomes the new head.
        return head;
    }
    else if(head == NULL)      //if linked list is empty
    {
        temp1->data = data;    
        temp1->next = NULL;
        head = temp1;         //just set the new node as head of linked list and return the head node
        return head; 
    }
    else
    {
        int i=0;         //for iterating to the required position
        temp->data = data;

        //store 2 nodes, one node which will store prev node and another to store current node. The temp node will go between these 
        prev = head,pcurr = head->next; 
        while(i != position-1 && pcurr != NULL){  //traverse the linked list till you reached the insertion position
            i++;
            prev = pcurr;
            pcurr = pcurr->next;
        }
        if(i != position-1){
            return head;     //can't insert at the specified position
        }
        prev->next = temp;   //point the node preceding the insertion position to new node to be inserted
        temp->next = pcurr; //point the new node to the next node to maintain the linked list
        return head;
    }  
}

希望以上修改能解决您的问题。我在需要的地方添加了注释以帮助您理解代码。如果您发现任何错误，请评论，我会更正。

Answer 2

有一些问题，代码实际上要简单得多。

你做了 malloc 两次而不是一次，所以你在每次调用时都在泄漏内存。

不要投 malloc:。参见：Do I cast the result of malloc?

SinglyLinkedListNode有点长。当在很多地方使用时，这并不能很好地扩展。像 Node 或 SlNode

这样更短的东西怎么样

这是重构后的版本：

#include <stdio.h>
#include <stdlib.h>

typedef struct node Node;
struct node {
    int data;
    Node *next;
};

Node *
insertNodeAtPosition(Node *head, int data, int position)
{
    int i = 0;
    Node *prev;
    Node *pcurr;
    Node *pnew;

    pnew = malloc(sizeof(Node));
    pnew->data = data;

    // find the correct place to insert
    prev = NULL;
    for (pcurr = head;  pcurr != NULL;  pcurr = pcurr->next, i += 1) {
        if (i >= position)
            break;
        prev = pcurr;
    }

    // link up the element that will follow the new node
    pnew->next = pcurr;

    // insert into middle or end of list
    if (prev != NULL)
        prev->next = pnew;

    // insert into empty list or _before_ the first node
    else
        head = pnew;

    return head;
}

void
printlist(Node *head)
{
    Node *pcurr;

    printf("List:");

    for (pcurr = head;  pcurr != NULL;  pcurr = pcurr->next)
        printf(" %d",pcurr->data);

    printf("\n");
}

int
main(void)
{
    FILE *fi;
    Node *head = NULL;
    int count;
    int newval;
    int pos;

    fi = fopen("input.txt","r");
    if (fi == NULL) {
        perror("input.txt");
        exit(1);
    }

    fscanf(fi," %d",&count);

    for (int i = 0;  i < count;  ++i) {
        fscanf(fi," %d",&newval);
        printf("new: %d\n",newval);
        head = insertNodeAtPosition(head,newval,count + 10);
    }
    printlist(head);

    while (1) {
        if (fscanf(fi," %d %d",&newval,&pos) != 2)
            break;
        printf("insert: %d at %d\n",newval,pos);
        head = insertNodeAtPosition(head,newval,pos);
    }
    printlist(head);

    fclose(fi);

    return 0;
}

这是测试文件：input.txt:

程序输出如下：

new: 16
new: 13
new: 7
List: 16 13 7
insert: 1 at 2
insert: 9 at 0
insert: 8 at 0
List: 8 9 16 13 1 7

更新：

can you also tell me why we have to use a pointer *prev? why only pcurr and pnew are not sufficient? It would help me in learning this new concept being a beginner.

当然可以。如果我们在列表的头部插入是因为列表是空的，或者我们想在头部插入（即我们想要一个新的头部，即使我们在列表中有其他节点），我们调整 head。

但是，如果我们在列表的中间插入或追加到列表的末尾，我们需要知道前一个节点是什么。

假设我们正在尝试追加到列表的末尾。我们需要知道列表的 existing/prior 尾部 [最后一个元素]。如果我们有：

head | node1 | node2 | node3

那么，node3就是列表的尾部。 node3->next 将是 NULL。为了追加，我们创建了新节点 (pnew) 并且我们必须设置 node3->next = pnew，所以我们得到：

head | node1 | node2 | node3 | pnew
                       prev

这里，prev最终会得到node3的值，所以设置prev->next = pnew就像设置node3->next = pnew一样。请注意，追加到末尾时，pcurr 将是 NULL.

我们称它为prev，因为它（前一个节点）也可以是我们希望插入after的any节点]，即使 prev 位于列表的中间（例如 node2）。这看起来像 (before 插入):

head | node1 | node2 | node3
               prev    pcurr

插入后，我们要：

head | node1 | node2 | pnew | node3
               prev           pcurr

在这种情况下，pcurr 将是 node3（即 prev->next）。

因此，prev 指向 之前的节点 我们要插入的位置 pnew 和 pcurr 指向节点after 我们要插入的地方 pnew.

换句话说，插入后，prev是pnew左边的节点（即在之前的节点）。 pcurr 是 pnew 右侧的节点（即跟随的节点）。如果 pcurr 为空，则有 no 节点，但设置 pnew->next = pcurr 在 all 情况下有效， 不管 head 或 prev 的值中的 是否为空。

如果 prev 最终成为 NULL，这意味着列表为空或者我们希望在列表的 head/front 处插入 pnew。在那种情况下，我们不能尝试取消引用 [a null] prev，所以我们只需将 head 设置为 pnew。然后，我们返回一个 updated head 指针。

有几种可能的列表状态和插入操作：

列表为空（调整头部）
我们要插入新节点before[非空]列表的头部（调整头部）
我们想在列表中间的某处插入新节点
我们想在列表的末尾追加新节点（如果 tail 为 null，则调整 tail 或 head）

我认为使用铅笔和纸对每个单独的案例进行图示会对您有所帮助。然后，手动验证代码是否处理了这些情况中的每一种，即使列表具有优先元素或为空。

关于上面的代码需要注意的重要一点是它使用适用于几种不同情况的变量，使用相同的代码路径，最大限度地减少 if/else 子句的数量来处理统一方式。

我所做的简化类型在编码时反复出现。彻底了解所做的事情以及原因将对您的未来有不可估量的帮助。

一个人编写的任何一个函数，就其本身而言，可能看起来并不多。但是，将其放大到数百或数千个函数中，它所带来的收益将远远超过最初的额外工作。

格言：需要的就简单——不要再简单了

代码越简单（即越简洁），它就越有可能是正确的、完整的，并且越容易检查正确性。与流行的看法相反，我还发现更简单的代码往往也更快。

在 C 的链表中的特定位置插入一个节点（仅限）

Insert a node at specific position in a linked list in C (only)

c

data-structures

singly-linked-list