Добавление в начало связанного списка в C

Question

У меня возникли проблемы с пониманием связанных списков в целом. Я понимаю, как они работают на бумаге, но как только я получу их кодирование, я никогда ничего не добился.

Вот мой код:

заголовочный файл: файл

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

typedef struct List { 

    int data; 
    struct List * next; 
} List; 

реализация:

#include "test.h" 

void addToFront(int data, List * head); 

int main(void) { 
    List * list; 
    list = malloc(sizeof(List)); 
    list->next = NULL; 

    List * head; 
    head = NULL; 

    addToFront(5,head); 

    printf("%d",head->data); //print first element 
    printf("%d",list->data); //print first element 

} 

void addToFront(int data, List * head) { 
    if(head == NULL) { 
     List * newNode = malloc(sizeof(List)); 
     newNode->data = data; 
     head = newNode; 
    } 
    else { 
     List * newNode = malloc(sizeof(List)); 
     newNode->data = data; 
     newNode->next = head; 
     head = newNode; 
    } 

} 

Я знаю, что связанный список будет пустым, заголовок NULL, так что я проверили там. Проблема возникает, поскольку я получаю segfault, говорящий, что заголовок не инициализирован, но очевидно, что это не так, если я инициализирую, я не могу отслеживать, является ли список пустым или нет, поэтому использование узла заголовка.

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

Я думал об этом без узла заголовка. Таким образом, я мог бы иметь счетчик, который отслеживает элементы в списке, проверяет, равен ли он его нулю, а затем просто добавляет базовый элемент в начало, в противном случае делает то же самое, что я делаю в инструкции else?

Answer 1

Проблема заключается в функции addFront, вы только передать указатель на голову, чтобы изменить то, что точки головы вам нужно передать адрес главы:

void addToFront(int data, List ** head) 

затем

*head = newHead 

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

Аналогичные по своей концепции:

void f(int n) 
{ 
    n = 53; 
} 

Чтобы избежать двойного указателя вы можете вернуть новую голову:

List* addToFront(int data, List* head) 
{ 
    ... 
    return newNode; 
} 

... 

head = addToFront(data, head); 

... 

Answer 2

Если вы не хотите использовать двойной указатель, вы можете использовать заголовок узел как узел-дозор, который действует исключительно как заполнитель, так что первый элемент связан head->next, и чтобы проверить, пуст ли список, отметьте head->next == NULL. Попробуйте следующее:

int main(void) { 
    List *head = malloc(sizeof(List)); 
    head->data = 0; 
    head->next = NULL; 

    addToFront(5, head); 

    List *first = head->next; 
    if (first) { // safe guard for first element 
     printf("%d", first->data); //print first element 
     printf("%d", first->data); //print first element 
    } 
} 

void addToFront(int data, List * head) { 
    List * newNode = malloc(sizeof(List)); 
    newNode->data = data; 
    newNode->next = head->next; 
    head->next = newNode; 
}