0

The following code tries to add a node to the beginning of a linked list. Can anyone explain to me why my insert function doesn't work? The program passed in a pointer nodePtr and modified it inside insert function. Since the program declared nodePtr in the main, the pointer should change but it didn't.

/* Copyright 2017 linkedList.c */
#include <stdlib.h>
#include <stdio.h>
#include <cs50.h>
#include <ctype.h>

// Linked list structure
typedef struct llnode {
  int val;
  struct llnode* node;
} llnode;

// Fill a linked list and create a pointer that points to it
void create(llnode* head);

// Print all values in a linked list
void printVal(llnode* head);

// Delete an entire linkedList
void delete(llnode* head);

// Insert a node (val) at the beginning of a linked List
void insert(llnode* head, int n);

int main(void) {
  // Create a pointer that points to a linked list
  llnode* nodePtr = malloc(sizeof(llnode));
  if (nodePtr == NULL)
    printf("Not enough space can be allocated.\n");
  create(nodePtr);
  printVal(nodePtr);

  insert(nodePtr, 3);
  printf("New List: \n");
  printVal(nodePtr);

  delete(nodePtr);

  return 0;
}


/**
 * Add integers to an existed linkedList and create a new linkedList
 */
void create(llnode* head) {
  // temp node
  llnode* temp = head;

  // Fill in a linkedList
  while (true) {
    // Input a number
    printf("Input a number: ");
    char* line = GetString();

    int n;
    // if not a digit, terminate the head and break
    if (sscanf(line, " %d ", &n) == 0) {
      free(line);
      temp -> node = NULL;
      break;
    }
    // if a digit, allocate space and check if NULL
    // Assign value and node
    free(line);
    temp -> val = n;
    temp -> node = malloc(sizeof(llnode));
    if (temp -> node == NULL)
      printf("Not enough space can be allocated.\n");

    // Update temp to point to next node
    temp = temp -> node;
  }
}

/**
 * Print all interger value in a linkedList in order
 */
void printVal(llnode* head) {
  llnode* temp = head;
  int i = 0;  // The ith element of a linked head

  // Check if next node is NULL
  while (temp -> node != NULL) {
    printf("The %d integer is %d.\n", i, temp->val);

    // Update i and node
    temp = temp -> node;
    i++;
  }
}

/**
 * Delete an entire linkedList
 */
void delete(llnode* head) {
  // temp is used for traversing
  llnode* temp = head;

  /* Nullify every node */
  while (temp != NULL) {
    temp = temp -> node;  // Traverse to next node
    free(head);  // Free memory of previous node
    head = temp;  // Update list to next node
  }
}

/**
 * Insert a node with integer n at the beginning of a linked list
 */
void insert(llnode* head, int n) {
  /* Declare another node for insertion */
  llnode* temp = malloc(sizeof(llnode));
  if (temp == NULL)
    printf("Not enough space can be allocated.\n");

  /* Assign values */
  temp -> val = n;
  // temp > node needs to store the address of head's first node
  temp -> node = head;

  /* Reassign head */
  head = temp;
}
2

head is passed per value, therefore it's a copy of the pointer you try to update. For updating the original value, either return the new head and update global head by assignment, or pass a reference (& in front of variable name in function signature, I would not recommend that), or pass a pointer to the head pointer instead.

[edit] One possible implementation using a pointer to the head pointer would look like

/**
 * Insert a node with integer n at the beginning of a linked list
 */
void insert(llnode** head, int n) {
  /* Declare another node for insertion */
  llnode* temp = malloc(sizeof(llnode));

  // this action will not prevent segfault in temp->val if temp is NULL!
  if (temp == NULL)
    printf("Not enough space can be allocated.\n");

  /* Assign values */
  temp -> val = n;
  // temp > node needs to store the address of head's first node
  temp -> node = *head;

  /* Reassign head */
  *head = temp;
}

and would be called with the address of the list head instead of the list head itself. Other functions would need to be changed accordingly.

With those modifications you could avoid creating a dummy node for the head in main.

| improve this answer | |
  • I don't think the program insert function passes head by value. The argument type is a pointer, which points to the first node' address. Can you explain your thoughts a little bit more? Or if you can show how to pass a pointer to the head pointer? So, insert should have modified the head inside the function. Yes, returning the new head works. – tea Jan 16 '17 at 20:09
  • Function's head parameter lives in the scope of the function and contains a copy of the passed pointer. Assigning to that one does not change the variable outside. – Blauelf Jan 17 '17 at 8:51
  • Can you explain why function delete works and can actually delete nodes even though it passes the same argument as my old insert function does? By your reasoning, it shouldn't work because it passes a copy of head value not its address, right? – tea Jan 18 '17 at 22:31
  • It also does not change the list head, though you now have a pointer to some freed memory block. – Blauelf Jan 19 '17 at 12:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .