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

Question

Я следую учебнику Stan Library CS Ed Library по связанным спискам. Я пытаюсь добавить новый список в начало связанного списка, и он не работает на основе распечатки, которую я получаю из функции Length, определенной ниже.

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

//build new struct for node 
//node has value and points to next node 
struct node{ 
    int value; 
    struct node *next; 
}; 

//declare a new struct node that contains 3 nodes (head, middle, tail) 
struct node *Build123(){ 
    struct node *head, *middle, *tail = NULL; 

    head = malloc(sizeof(struct node)); 
    middle = malloc(sizeof(struct node)); 
    tail = malloc(sizeof(struct node)); 

    head->value = 3; 
    head->next = middle; 

    middle->value = 5; 
    middle->next = tail; 

    tail->value = 9; 
    tail->next = NULL; 

    return head; 
}; 

//declare a function Length and variable counter to calculate size of list 
int Length(struct node *head) { 
    int count = 0; 
    struct node *iterator = head; 
    while (iterator != NULL) { 
     count++; 
     iterator = iterator->next; 
    } 
    return count; 
} 

//declare function Push to add new lists that would be added to the front 
void Push (struct node **headRef, int value){ 
    struct node *newNode; 
    newNode = malloc(sizeof(struct node)); 
    newNode->value = value; 
    newNode->next = *headRef; 
} 

int main(){ 
    //instantiate the 3 element linked list named beast 
    struct node *beast = Build123(); 

    //add 2 elements to the front of the linked list via pass by reference 
    Push(&beast, 6); 
    Push(&beast, 12); 

    //calculate length of linked list after elements have been added 
    int len = Length(beast); 

    //print length of linked list to screen 
    printf("%d\n",len); 
    return 0; 
} 

Я получаю 3, когда я ожидаю получить 5. Не могли бы вы помочь мне найти ошибку в коде, которая мешает мне получить значение, которое я ожидаю? Я не мог понять, почему, несмотря на немало возиться. Спасибо!

Answer 1

Вы не изменяете headRef в своей функции Push, поэтому голова вашего списка никогда не изменяется. beast всегда указывает на исходный узел, на который он был создан, чтобы указать на. Добавьте эту строку:

*headRef = newNode; 

В Push(), и вы будете устанавливать.

Answer 2

Проблема в том, что когда вы делаете что-то вроде Push(&beast, 6);, то, что beast указывает на то, что функция не нажата. Несмотря на то, что Push добавляет больше элементов в связанный список, когда вы вызываете Length на beast позже, он вызывает его на том же узле, который первоначально был у зверя в начале, так что он полностью не знает дополнительных добавленных узлов.

В конце Пуш(), вам нужно сделать, это:

*headRef = newNode;

так что beast правильно указывают на новое начало списка.

Answer 3

В конце метода push(), вы должны добавить:

*headRef = newNode

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