在 C 中双向链表的严格上下文中，插入元素的正确方法是什么？

Question

下面的代码来自《Programming Interviews Exposed 4th》一书，现在，要解决这个问题，有两种可能的方法，

bool insertInFront( IntElement *head, int data ){
    IntElement *newElem = malloc( sizeof(IntElement) );
    if ( !newElem ) return false;

    newElem->data = data;
    newElem->next = head;
    head = newElem; // Incorrect! Updates only the local head pointer
    return true;
}

第一种方法是给出一个指向指针的指针，正如书中所建议的那样......

bool insertInFront( IntElement **head, int data ){
    IntElement *newElem = malloc( sizeof(IntElement) );
    if ( !newElem ) return false;

    newElem->data = data;
    newElem->next = *head;
    *head = newElem;
    return true;
}

第二种方法是我简单地取消引用 head 以通过分配从 newElem.

取消引用的值来更新它的值

bool insertInFront( IntElement *head, int data ){
    IntElement *newElem = malloc( sizeof(IntElement) );
    if ( !newElem ) return false;

    newElem->data = data;
    newElem->next = head;
    *head = *newElem; // <---------- check this line here!
    return true;
}

我的问题是，使用指向指针的指针或简单地更新指向的值之间有什么区别，严格在链表用例的上下文中。

Answer 1

In a strict context to doubly linked lists in C, which is the right way to insert an element?

对于初学者来说，您似乎指的是单链表而不是双向链表，因为所提供的代码都没有处理双向链表。

您需要更新第一个函数执行的指针 head，因为指针 head 通过引用（通过指向它的指针）传递给函数并取消引用接受参数的参数指向指针头的指针函数可以直接访问指针头。

至于这个功能

bool insertInFront( IntElement *head, int data ){
    IntElement *newElem = malloc( sizeof(IntElement) );
    if ( !newElem ) return false;

    newElem->data = data;
    newElem->next = head;
    *head = *newElem; // <---------- check this line here!
    return true;
}

然后它不这样做，它尝试将指针head指向的节点分配给指针newElem指向的动态分配节点。

注意表达式 *head 产生一个 IntElement 类型的对象，它是一个节点而不是指向节点的指针。

因此，由于取消引用空指针，当 head 等于 NULL 时，函数可以调用未定义的行为。而且它有内存泄漏，因为动态分配的内存没有被释放，它的地址在退出函数后会丢失。并且它不会插入新节点。相反，它会尝试更改指针 head.

指向的已经存在的节点

对于双向链表，如果没有更多声明的结构确实通过指向头节点和尾节点的指针来定义双向链表，则函数可以按以下方式查看。

bool insertInFront( IntElement **head, int data )
{
    IntElement *newElem = malloc( sizeof( IntElement ) );
    bool success = newElem != NULL;

    if ( success )
    {
        newElem->data = data;
        newElem->prev = NULL;
        newElem->next = *head;
        if ( *head ) ( *head )->prev = newElem;
        *head = newElem;
    }

    return success;
}

Answer 2

第三种方法——避免副作用。

IntElement *insertInFront( IntElement *head, int data )
{
    IntElement *newElem = malloc( sizeof( *newElem ) );
    bool success = newElem != NULL;

    if ( success )
    {
        newElem->data = data;
        newElem->prev = NULL;
        newElem->next = head;
        if(head) head -> prev = newElem;
    }
    return newElem;
}

并在调用函数中

IntElement *newHead = insertInFront(head, data);
if(newHead) head = newHead;
else {/* error handling*/}

还要注意在 sizeof 中使用对象而不是类型：

    IntElement *newElem = malloc( sizeof( *newElem ) );

它更安全 - 如果您更改类型，则不必更改代码中的所有 sizeof。

在 C 中双向链表的严格上下文中，插入元素的正确方法是什么？

In a strict context to doubly linked lists in C, which is the right way to insert an element?

c

linked-list

insert

singly-linked-list

function-definition