C语言实现双向链表

Question

我想在链表的开头插入一个节点，每当调用 insertAtBeginning 方法时。我的代码构建良好，但没有得到所需的输出。

我得到以下输出：

0------>NULL

期望的输出是：

9------>8------>7------>6------>5------>4------>3------>2------>1------>0------>NULL

以下是我的代码：

#include<stdio.h>
#include<stdlib.h>

struct dll{
    int data;
    struct dll* previous;
    struct dll* next;
};


struct dll* insertAtBeginning(int a, struct dll* head){

    if(head == NULL){
        head->data = a;
        head->previous = NULL;
        head->next = NULL;
        return head;
    }
    else{
        struct dll *first;
        first = (struct dll*) malloc( sizeof(struct dll));
        first->data = a;
        first->next = head;
        head->previous = first;
        first->previous = NULL;
        head = first;
        free(first);
        return head;
    }
}


void display_from_first(struct dll* head){
    struct dll *temp;
    temp = head;

    printf("\nThe linked list contains: ");
    while(temp != NULL) {
        printf("%d------>",temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
    free(temp);
    }


int main(){
    int i = 0;
    struct dll *head1, *tail1;
    head1 = (struct dll*) malloc( sizeof(struct dll));
    head1->next = NULL;
    head1->previous = NULL;

    for(i=0; i<10; i++){
        insertAtBeginning(i, head1);
    }

    display_from_first(head1);

    return 0;
}

Answer 1

你不能在 insertAtBeginning() 中 free(first);。

代码here.

顺便说一句，当你有空列表时，你的 display_from_first() 打印 The linked list contains: 0------>NULL 因为

head1 = (struct dll*) malloc( sizeof(struct dll));
head1->next = NULL;
head1->previous = NULL;

在 main() 中。从 main 中删除它以获得正确的输出

Answer 2

你这里有几个错误。

1) 您的函数 insertAtBeginning returns 指向已更改列表的指针，但您没有在主函数中更新指向列表头部的指针。

2) 您正在释放刚刚分配的指向插入函数中新节点的指针。你以为你在释放指针，但实际上你说内存中的这个地方不再需要所以你的节点不能在那里。

Answer 3

这里主要有两个问题:

free(first) ：这不是必需的，因为您希望保存刚刚分配的内存，而不是删除它。
您的 insertAtBeginning() 函数 returns 指向 head 的指针，因此在 main() 中，您调用此函数的位置将其更改为 head1=insertAtBeginning(i, head1);这样你的脑袋也有救了

这是经过两次编辑的代码：

http://ideone.com/nXwc8z

Answer 4

如果您从一个包含两个节点的空列表开始，那么双向链表的代码会更简洁，如下所示。

这样您就不必处理像 if(head==NULL) 这样的特殊情况。插入（或删除）的节点之前和之后总是有一个节点，因此您只需将其连接起来即可。

#include <stdio.h>
#include <stdlib.h>

typedef struct s_node Node;
struct s_node
{
    Node *prev;
    Node *next;
    int  data;
};

Node *insertAtBeginning( Node *head, int value )
{
    // allocate memory for the new node
    Node *node = malloc( sizeof(Node) );
    if ( node == NULL )
        return NULL;

    // insert the node at the beginning of the list
    Node *temp = head->next;
    head->next = node;
    temp->prev = node;

    // fill in the fields of the node
    node->prev = head;
    node->next = temp;
    node->data = value;

    return node;
}

void showList( Node *head )
{
    Node *node;

    printf( "The list contains: " );
    for ( node = head->next; node->next != NULL; node = node->next )
        printf( "%d--->", node->data );
    printf( "NULL\n" );
}

int main( void )
{
    // create an empty list with two nodes
    Node head = { NULL , NULL, 0 };
    Node tail = { &head, NULL, 0 };
    head.next = &tail;

    // insert more nodes
    for ( int i = 0; i < 10; i++ )
        insertAtBeginning( &head, i );

    // display the list
    showList( &head );
}

C语言实现双向链表

Implement a doubly linked list in C

c

pointers

linked-list

doubly-linked-list