c - 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

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

这样你就不必处理像 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 );
}