双向链表中的注入函数在调用 pop() 后任意指向头部元素

Question

编辑：我认为我的问题与提议的重复问题完全不同。它询问的是一般情况，而我的问题是询问一个非常具体的情况，在这种情况下，奇怪行为的原因应该是可追溯的，因为它是多么具体。

我的双重 LL 实现中有一些非常奇怪的行为。基本上，如果我 pop() （从头开始）一个元素和然后 inject() （在尾部添加）一些其他元素，最后一个尾元素现在指向列表的头部似乎没有任何原因（我想默认情况下不是 NULL 或至少是一个随机地址）。

我想出了解决问题的方法。注入时，我没有将新节点的 "next" 指向 NULL。

不过，我还是很想明白为什么注入的节点会选择指向头部，而没有具体的指向方向。

效果是，如果我从头部开始遍历列表（但不是从尾部开始），我会一直循环下去，因为最后一个尾部元素指向列表的头部。

编辑： 所以我尝试在 inject() 中调用 malloc 之后打印出指针指向的地址，并且出于某种疯狂的原因指针创建时已经指向头部地址；但这只有在我调用 inject() 之前调用 pop() 时才会发生。难以置信的奇怪...

int pop()
{
    node* temp = head;
    int value = temp->value;    
    head = temp->next;
    free(temp);
    head->previous = NULL;
    size--;
    return value;
}

void inject(int value)
{
    if (tail == NULL)
    {               
        tail = malloc(sizeof(node));
        tail->value = value;
        tail->next = NULL;
        tail->previous = NULL;
        head = tail;
        size++;
    }
    else
    {
        node* new_node = malloc(sizeof(node));
        printf("pointing to: %p\n", new_node->next);// points to head after pop() call
        new_node->value = value;
        tail->next = new_node;
        new_node->previous = tail;
        tail = new_node;
        //new_node->next = NULL;
        size++;
    }
}

inject() 中注释掉的行解决了问题，但仍然没有解释为什么如果我在 pop 后注入尾巴会指向头部。

以下是 main() 之前的代码，以防：

typedef struct node{
    int value;      
    struct node* next;
    struct node* previous;      
}node;

node* head = NULL;
node* tail = NULL;

int head_value();
int tail_value();
void push(int);
int pop();
void inject(int);
int eject();

int size = 0;

Answer 1

    node* new_node = malloc(sizeof(node));
    printf("pointing to: %p\n", new_node->next);// points to head after pop() call

new_node->next 将包含 malloc 想要放入其中的任何垃圾。它可能发生指向头部，但你从未初始化它，因此 printf 试图在垃圾中寻找意义。

您的代码将内存管理分散到各处。与其尝试修复它，不如使用我关于结构的常用建议重写它：总是编写函数来初始化和销毁它们。总是，即使它看起来很愚蠢和琐碎。它避免了将代码分散到各处，每次都略有不同。它允许您在尝试使用之前对结构的基本功能进行单元测试 it.It 让您专注于算法，而不是内存管理。

首先，让我们调整一下您的结构。 node 是一个非常糟糕的类型名称。您（或其他人）可能想要调用变量 node 并导致冲突。我将其命名为 Node，大写以避免与变量和内置函数混淆。

typedef struct Node {
    int value;      
    struct Node* next;
    struct Node* previous;      
} Node;

现在我们可以写 Node_new 和 Node_destroy。

Node *Node_new() {
    Node *node = malloc(sizeof(Node));
    node->value = 0;
    node->next = NULL;
    node->previous = NULL;

    return node;
}

void Node_destroy( Node *node ) {
    free(node);
}

Node_destroy 可能看起来很愚蠢，但它使您（或其他任何人）不必记住如何销毁 Node。它允许您更改 Node 的内部结构而不更改其余代码（在编写此代码时发生）。

您正在使用全局变量。全局变量使一切变得更加复杂，并限制了您可以对代码执行的操作。相反，将 head、tail 和 size 之类的东西包装到它自己的结构中并传递它。

typedef struct {
    Node *head;
    Node *tail;
    size_t size;
} LinkedList;

并且它需要自己的创建和销毁函数。

LinkedList *LinkedList_new() {
    LinkedList *list = malloc(sizeof(LinkedList));
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;

    return list;
}

void LinkedList_destroy( LinkedList *list ) {
    for( Node *node = list->head; node != NULL; node = node->next ) {
        Node_destroy(list->head);
    }

    free(list);
}

请注意，LinkedList_destroy 负责清理其所有节点，这让 LinkedList 的用户少了一件担心和可能搞砸的事情。

LinkedList_destroy 可以在不知道 Node 是如何工作的情况下调用 Node_destroy。这就是我们如何立即受益于 Node 的封装和抽象。但是不要使用递归，列表可以任意长，递归有堆栈溢出的风险。

现在我们可以编写 push 和 pop 以确保正确创建和销毁事物。请注意，他们采用 LinkedList 而不是使用全局变量。

void LinkedList_push(LinkedList *list, int value)
{
    Node *node = Node_new();
    node->value = value;

    switch( list->size ) {
        /* The list is empty, this is the first node */
        case 0:
            list->head = list->tail = node;
            break;
        default:
            list->tail->next = node;
            node->previous = list->tail;
            list->tail = node;
            break;
    }

    list->size++;
}

int LinkedList_pop( LinkedList *list ) {
    Node *popped = list->tail;

    switch( list->size ) {
        /* The list is empty, nothing to pop */
        case 0:
            fprintf(stderr, "LinkedList was empty when popped.\n");
            exit(1);
            break;
        /* Popped the last node */
        case 1:
            list->head = list->tail = NULL;
            break;
        /* Only one node left, it's both the head and tail */
        case 2:
            list->tail = list->head;
            list->tail->previous = list->tail->next = NULL;
            break;
        default: 
            list->tail = popped->previous;
            list->tail->next = NULL;
            break;
    }

    /* Have to do this at the end because size_t is unsigned
       it can't go negative */
    list->size--;

    int value = popped->value;
    Node_destroy(popped);

    return value;
}

我用了switch所以我可以清楚地划分所有的特殊情况。

我并不是说这是 push 和 pop 的最佳实现，或者它甚至没有错误，但可以在编写它们时不必担心结构是否已正确初始化或释放。您可以专注于逻辑，而不是内存管理。

然后演示一切正常...

void LinkedList_print( LinkedList *list ) {
    for( Node *node = list->head; node != NULL; node = node->next) {
        printf("%d\n", node->value);
    }
}

int main() {
    LinkedList *list = LinkedList_new();

    for( int i = 0; i < 3; i++ ) {
        LinkedList_push(list, i);
    }

    while( list->size != 0 ) {
        printf("list->size: %zu\n", list->size);
        LinkedList_print(list);
        LinkedList_pop(list);
    }

    LinkedList_destroy(list);
}

$ ./test
list->size: 3
0
1
2
list->size: 2
0
1
list->size: 1
0

双向链表中的注入函数在调用 pop() 后任意指向头部元素

Inject function in doubly linked list arbitrarily points back to head element after call to pop()

c

pointers

linked-list

doubly-linked-list