Связанный список в C - методы

Question

Предположим, мы дважды связанный список узлов

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

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

typedef struct LinkedList { 
    Node *first; 
    Node *last; 
} LinkedList; 

void initList(LinkedList* l) { 
    l->first = NULL; 
    l->last = NULL; 
} 

и я должен метод кода, который вставляет новый узел с заданным значением в конце списка и возвращает указатель на новый узел. Моя попытка следующим образом:

Node *insert(LinkedList *list, int value) { 

    Node node; 
    node.value = value; 
    node.prev = list->last; 
    node.next = NULL; 

    if (list->last != NULL){ 
     (list->last)->next = &node; 
    }else{ 
     list->first = &node; 
     list->last = &node; 
    } 

    return &node; 
} 

Кажется, что включение в пустой список работ, но не для не пустой.

(Существуют тесты внедрения, которые говорят мне, что вставка была успешной или нет. Я могу опубликовать их коды, но не думаю, что это важно).

Итак, пожалуйста, где ошибки?

Существует предупреждение в журнале (51-й линии является то, что с «вернуть & узел»)

C:\...\main.c|51|warning: function returns address of local variable [-Wreturn-local-addr]| 

Это серьезная проблема? И как его удалить?

---

Спасибо за ответы, но я думаю, что есть еще проблема с непустых списков, так как в соответствии с тестом, это не удается:

void test_insert_nonempty(){ 
    printf("Test 2: "); 

    LinkedList l; 
    initList(&l); 

    Node n; 
    n.value = 1; 
    n.next = NULL; 
    l.first = &n; 
    l.last = &n; 

    insert(&l, 2); 

    if (l.last == NULL) { 
     printf("FAIL\n"); 
     return; 
    } 
    if ((l.last->value == 2) && (l.last->prev != NULL)) { 
     printf("OK\n"); 
     free(l.last); 
    }else{ 
     printf("FAIL\n"); 
    } 
} 

Answer 1

Node node; является локальной переменной в вашем функция insert. Он «уничтожается», как только ваша функция заканчивается и больше не определена. Возвращением указателя на локальную переменную функции является неопределенное поведение. Вы должны выделить динамическую память. Динамически выделять память зарезервирована, пока вы free его:

Node *insert(LinkedList *list, int value) { 

    Node *node = malloc(sizeof(Node)); // allocate dynamic memory for one node 
    if (node == NULL) 
     return NULL; // faild to allocate dynamic memory 

    node->value = value; 
    node->prev = list->last; 
    node->next = NULL; 

    if (list->first == NULL) 
     list->first = node;  // new node is haed of list if list is empty 
    else // if (list->last != NULL) // if list->first != NULL then list->last != NULL 
     list->last->next = node; // successor of last node is new node 
    list->last = node;   // tail of list is new node 

    return node; 
} 

Примечания, чтобы избежать утечек памяти вы должны free каждый узел списка, когда вы уничтожите список.

Answer 2

Вы возвращаете адрес нестатической локальной переменной, которая будет исчезать при возврате из функции и разыменовывает адрес после возврата из функции вызывает неопределенное поведение.

Вы должны выделить буфер и вернуть его адрес.

Node *insert(LinkedList *list, int value) { 

    Node *node = malloc(sizeof(Node)); 
    if (node == NULL) return NULL; 
    node->value = value; 
    node->prev = list->last; 
    node->next = NULL; 

    if (list->last != NULL){ 
     (list->last)->next = node; 
    }else{ 
     list->first = node; 
     list->last = node; 
    } 

    return node; 
} 

Answer 3

Необходимо динамически назначать новый узел.

В противном случае переменная node в функции

Node *insert(LinkedList *list, int value) { 

    Node node; 
    //... 

является локальной переменной функции, которая не будет в живых после выхода из функции. В результате любой указатель на переменную, используемую для доступа к ней, будет недействительным.

Функция может выглядеть

Node * insert(LinkedList *list, int value) 
{ 
    Node *node = malloc(sizeof(Node)); 

    if (node != NULL) 
    { 
     node->value = value; 
     node->prev = list->last; 
     node->next = NULL; 

     if (list->last != NULL) 
     { 
      list->last->next = node; 
     } 
     else 
     { 
      list->first = node; 
     } 

     list->last = node; 
    } 

    return node; 
}