c - 更新链接列表顶部条目

Question

我面临着创建一个插入到链表顶部的算法的挑战。我设置了一个指针来跟踪列表的顶部。

#include "Entry.h"

int main(void)
{
    struct entry list;
    struct entry *listPtr = &list;

    list.value = 100;
    n1.value = 200;
    n2.value = 300;
    n3.value = 400;

    initList(&list);

    struct entry insert;
    insert.value = 1000;

    update(&insert, &n2);

    return 0;
}

练习表明我可以使用更新方法在列表的前面插入一个新条目。我怎样才能做到这一点？

#include <stdio.h>
#include <stdbool.h>

struct entry
{
    int value;
    struct entry *next;
}n1, n2, n3, end;

void initList(struct entry *list)
{
    list->next = &n1;
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &end;
    end.value = 0;
}

void update(struct entry *insert, struct entry *after)
{
    insert->next = after->next;
    after->next = insert;
}

Answer 1

您可以轻松地将更新函数更改为

struct entry *update(struct entry *insert, struct entry *before, struct entry *after)
{
    insert->next = after;
    if (before != NULL)
    {
        before->next = insert;
        return before;
    }
    return insert;
}

其中 insert 是要插入的条目，before 是插入的条目之前的节点，after 是插入的条目之后的节点。如果新条目作为第一个条目插入，则该函数返回新条目，否则返回 before。

要添加到列表前面，请使用

list_to_prepend_to = update(node_to_insert, NULL, list_to_prepend_to);

例如，在您的代码中，您可以使用

listPtr = update(&insert, NULL, &list);

while (listPtr)
{
    printf("%d\n", listPtr->value);
    listPtr = listPtr->next;
}

在列表中添加一个条目并打印列表。要插入到列表的中间，不需要返回值:

update(&insert, &list, &n1);

这将使插入列表中的第二个条目。