在严格的上下文中，在C中双重链表，这是正确的方式来插入一个元素?

Question

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

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;
}

第二种方法是通过分配从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

在严格的上下文中对C中的双链表，这是正确的如何插入元素?

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

你需要更新第一个函数执行的指针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:

中使用的是object而不是type

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

这样更安全——如果你改变了类型，你不必改变代码中所有的sizeof。