c中的双链表实现

Question

我正在努力提高我的c编程技能，因此开始尝试编写双链表。

这是我到目前为止想出的。

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//forward definition
typedef struct Node node_t;

//Define the structures needed for double linked list
//Each node
typedef struct Node 
{
        int data;
        node_t *next;
        node_t *prev;
}node_t;


void initList(node_t** first , node_t** last)
{
    //Allocate memory for the first and the last node
    *first = (node_t*) malloc(sizeof(node_t));
    *last =  (node_t*) malloc(sizeof(node_t));
    (*first)->data = 1;
    (*last)->data = 2;
    (*first)->prev = NULL;
    (*last)->next = NULL;
    (*first)->next = (*last)->prev;
    return;
}
void destroyList(node_t** first)
{
    node_t* temp;
    temp = *first;
    free((*first)->next);
    free((*first));
    temp = NULL;

    return;
}

int main()
{
    node_t *first =NULL, *last = NULL;
    printf("Initalizing the Listn");
    initList(&first,&last);
    printf(" 1st element is %dn",first->data);
    printf(" 2nd element is %dn",last->data);
    printf("Destroying the Listn");


    destroyList(&first) ;

    return 0;
}

我

实际上在网上查找了一些代码，我看到大多数实现都有

1） 节点有 1 个结构

，列表本身有 1 个结构（有头和尾）。 我的问题是，这是强制性的吗？我不能只用 1 个结构来实现它吗？

2）我的想法是将这个文件制作成一个库，并从应用程序中调用它。喜欢
InitList（）， DestroyList（）， AddNode， DeleteNode 等

这就是为什么我对 INit 和销毁使用双指针的原因。我在销毁列表时遇到了一些麻烦。我知道我做错了，我会继续纠正它。

3）我发现节点指针

 temp = first

指向某个地址。如果我做临时++。为什么它不指向下一个节点？

4）我们可以传递第一个或最后一个节点指针来删除整个列表，对吗？（即遍历和dleete sequentialluy？

谢谢！

Answer 1

1）节点的1个结构和List本身的1个结构当然不是强制性的。 它通常以 1 个结构完成。

2）好主意InitList（），DestroyList（），AddNode，DeleteNode等。

您的初始化可能需要

(*first)->next = *last;
(*last)->prev = *first;
//  rather than
(*first)->next = (*last)->prev;

3）作为@Jamil海杜恩，不要做temp++，而是temp = temp->next。

4）您可以通过任何一端。 经典问题是在free()之前没有获取下一个指针

// bad code
free(temp);
temp = temp->next;
// good code
next = temp->next;
free(temp);
temp = next;

---

随笔

范式转变。 考虑一个没有 NULL 指针的双链接列表。 而是做一个完整的圆圈。 Last->next = First . First->prev = Last . 然后，而不是直到p->next == NULL的while循环，循环直到p->next == first。 该列表仅指向第一个节点（如果为空，则为 NULL）。 我发现这种样式更灵活，*NULL 的变化更少。

第二次范式转变。 有时，双链接列表的唯一原因是允许在开头或结尾添加节点。 这可以通过一个绕圈的next场来实现。 在这种情况下，列表指针不指向第一个节点，而是指向最后一个节点。 （注：先是后>下） 在开头或结尾插入是相同的，在最后一个之后和第一个之前添加一个节点。 区别在于我们是保持列表指针原样，还是前进它。

Answer 2

1）没有必要有一个列表结构，但如果结构跟踪某些元数据（例如列表的长度，否则为了获得长度，你必须每次迭代你的列表，这对于大型列表来说可能是昂贵的），它可以更快地执行某些操作。

3）我假设你的意思是

temp = *first

并且 temp++ 不指向下一个节点，因为它不能保证您的节点位于连续的内存地址中（另一方面，数组可以）。

4）您可以使用第一个或最后一个来删除列表，但您必须确保标头之前的某个属性也指向NULL，否则您可能会陷入无限循环