Prompting the user to input a data value into an element in a linked list

Question

I'm working through a practice problem that is having me build and modify a linked list over a series of steps. I am particularly interested in knowing if there's a more elegant way of prompting the user to input a data value for a new element in a linked list (see step 5 below).

I'd also like to know if there's a better way of counting and returning the number of elements in a linked list.

Practice Problem:

• Step 4: Add a function trav_and_print to your program that will traverse the linked list and print the values of all of the data members.
• Step 5: Add code to your program that will add another element to the end of the linked list. Prompt the user for the data value. Call your trav_and_print function, and also from main print the value of last -> data to make sure that the element was added correctly.
• Step 6: Add another function count_elems that will traverse the linked list, count how many elements there are, and return that count. Test this function by calling it in various places in main, including before there are any elements in the linked list.

My code thus far:

#include <stdio.h>
#include <stdlib.h>
typedef struct linked_list
{
 int data;
 struct linked_list *next;
} element;
typedef element * elementptr;
void trav_and_print(elementptr);
int count_elems(elementptr);
int main()
{
 elementptr first = NULL;
 elementptr last = NULL;
 int var = 0;
 int NumElems = 0;
 /* Create a linked list with one element */
 /* NOTE: the first element is always a special case */
 first = (elementptr) malloc(sizeof(element));
 last = first;
 last -> data = 5;
 last -> next = NULL;
 /* Add another element to the end of the list */
 last -> next = (elementptr) malloc(sizeof(element));
 last = last -> next;
 last -> data = 12;
 last -> next = NULL;
 /*Add another element to the end of the list;
 user generated number*/
 last -> next = (elementptr) malloc(sizeof(element));
 last = last -> next;
 printf("Enter the data value to add to the linked list: ");
 scanf("%d",&var);
 last -> data = var;
 last -> next = NULL;
 trav_and_print(first); //prints the linked list
 NumElems = count_elems(first); //traverses and counts the elements in the linked list
 printf("Number of elements in the linked list: %d",NumElems);
 free(first);
 free(last);
 return 0;
}
void trav_and_print(elementptr f)
{
 elementptr current;
 current = f;
 if(current == NULL)
 printf("There is no linked list!\n");
 else
 while (current != NULL)
 {
 printf("The data value is %d\n",current->data);
 current = current -> next;
 }
}
int count_elems(elementptr f)
{
 int count = 0;
 elementptr current;
 current = f;
 while(current != NULL)
 {
 current = current->next;
 count++;
 }
 return count;
}

• user3629249: OT: regarding: typedef element * elementptr; it is a poor programming practice to hide a pointer in a typedef.
• user3629249: OT: regarding: first = (elementptr) malloc(sizeof(element)); 1) the returned type (in c) is void* which can be assigned to any pointer. Casting just clutters the code, making it more difficult to understand, debug, etc 2) when calling any of the heap allocation functions: malloc() calloc() realloc() always check (!=NULL) the returned value to assure the operation was successful
• pacmaninbw: The current implementation of the program has a possible memory leak because it only deletes the head and the tail of the linked list. If an entire linked list needs to be deallocated or deleted, there should be a function that traverses the linked list and deletes each node.
• pacmaninbw: Always test the return value of malloc(size_t size) to make sure it isn't NULL. The function malloc() returns NULL if it fails and it can fail for a variety of reasons such as not enough memory to allocate. In object oriented languages the new operator or the constructor will throw an exception in this case.
• pacmaninbw: For procedural languages there is a design methodology called Top Down Design (also known as Step-wise Refinement) that breaks the problem into smaller and smaller parts until all the parts are atomic. With linked lists some basic operations are insert node, append node, delete node and perhaps find node. There might also be new node that creates the node from user input. en.wikipedia.org/wiki/Top-down_and_bottom-up_design

Answer 1

Here are some minor, general coding style suggestions.

UX

When Irun the code, I see this prompt:

Enter the data value to add to the linked list:

You could add to the prompt, specifying what type of data is expected.

When the code completes, the last line of output is merged with my shell prompt. You could change this line:

printf("Number of elements in the linked list: %d",NumElems);

adding a newline character:

printf("Number of elements in the linked list: %d\n", NumElems);

Naming

Some of the variable names could be improved.

elementptr is easier to read as element_ptr.

var is too generic for a variable name.

NumElems would be more consistent with your other variable names as num_elems.

Layout

The while loop in the trav_and_print function is not indented properly. This would be better:

while (current != NULL)
{
 printf("The data value is %d\n",current->data);
 current = current -> next;
}

Add blank lines between the functions:

}
void trav_and_print(elementptr f)
{

There is other inconsistent whitespace usage around operators:

current = current -> next;

and:

current = current->next;

It would be worth running your code through a code prettifier.

Answer 2

Advice I (data structures)

I suggest you roll your own linked list data type:

typedef struct linked_list_node_t {
 int data;
 struct linked_list_node_t* p_next;
 struct linked_list_node_t* p_prev;
} linked_list_node_t;
typedef struct linked_list_t {
 size_t size;
 linked_list_node_t* p_head;
 linked_list_node_t* p_tail;
} linked_list_t;

Advice II (linkage)

I suggest also that you opt to doubly-linked lists. This way, you may benefit from nearest neighbor optimization: if the access element is closer to the tail of the list, scan backwards starting from the tail node of the list. Otherwise, scan forward as normally. On average, this speeds up search by the factor of two.

Advice III (alternative implementation)

I suggest the following as a rewrite of your program:

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef struct linked_list_node_t {
 int data;
 struct linked_list_node_t* p_next;
 struct linked_list_node_t* p_prev;
} linked_list_node_t;
typedef struct linked_list_t {
 size_t size;
 linked_list_node_t* p_head;
 linked_list_node_t* p_tail;
} linked_list_t;
void linked_list_t_init(linked_list_t* const p_list) {
 p_list->size = 0;
 p_list->p_head = NULL;
 p_list->p_tail = NULL;
}
size_t linked_list_t_size(const linked_list_t* const p_list) {
 return p_list->size;
}
int linked_list_t_push_front(linked_list_t* const p_list, const int value) {
 if (!p_list) {
 return FALSE;
 }
 linked_list_node_t* p_node = malloc(sizeof * p_node);
 if (!p_node) {
 return FALSE;
 }
 if (p_list->size == 0) {
 p_node->p_next = NULL;
 p_node->p_prev = NULL;
 p_list->p_head = p_node;
 p_list->p_tail = p_node;
 p_list->size = 1;
 } else {
 p_node->p_prev = NULL;
 p_node->p_next = p_list->p_head;
 p_list->p_head->p_prev = p_node;
 p_list->p_head = p_node;
 p_list->size++;
 }
 p_node->data = value;
 return TRUE;
}
int linked_list_t_push_back(linked_list_t* const p_list, const int value) {
 linked_list_node_t* p_node = malloc(sizeof * p_node);
 if (!p_node) {
 return FALSE;
 }
 if (p_list->size == 0) {
 p_node->p_next = NULL;
 p_node->p_prev = NULL;
 p_list->p_head = p_node;
 p_list->p_tail = p_node;
 p_list->size = 1;
 } else {
 p_node->p_next = NULL;
 p_node->p_prev = p_list->p_tail;
 p_list->p_tail->p_next = p_node;
 p_list->p_tail = p_node;
 p_list->size++;
 }
 p_node->data = value;
 return TRUE;
}
int linked_list_t_update(const linked_list_t* const p_list, size_t index, int value) {
 if (!p_list) {
 return FALSE;
 }
 if (index >= p_list->size) {
 return FALSE;
 }
 size_t i = 0;
 for (linked_list_node_t* node = p_list->p_head; node; node = node->p_next) {
 if (i++ == index) {
 node->data = value;
 return TRUE;
 }
 }
 abort(); // Should not get here like NEVER!
 return FALSE;
}
int linked_list_t_print(const linked_list_t* const p_list) {
 if (!p_list) {
 return FALSE;
 }
 for (linked_list_node_t* node = p_list->p_head; node; node = node->p_next) {
 printf("%d ", node->data);
 }
 puts("");
 return TRUE;
}
int main()
{
 linked_list_t lst;
 linked_list_t_init(&lst);
 for (int i = 0; i < 5; ++i) {
 linked_list_t_push_back(&lst, i);
 }
 for (int i = 0; i < 5; ++i) {
 linked_list_t_push_front(&lst, i);
 }
 linked_list_t_print(&lst);
 linked_list_t_update(&lst, 3, 666);
 linked_list_t_print(&lst);
 return EXIT_SUCCESS;
}

• Chris: I would suggest not defining your own boolean type but rather using <stdbool.h>. Also, you return true or false from your functions, but a pointer to the linked list is something else you could return. In that case, NULL would suffice to indicate failure, and returning the list itself would indicate success.

Answer 3

This is C, so you need to check return values for errors. In particular, malloc() returns a null pointer when no more memory can be allocated, so this code

 first = (elementptr) malloc(sizeof(element));

needs to be something like

 first = malloc(sizeof *first);
 if (!first) {
 fprintf(stderr, "Out of memory\n");
 return EXIT_FAILURE;
 }

Note also that there's no need to cast the result from malloc() as it's a void*, which means it can be assigned to any object pointer type. And prefer sizeof *first to sizeof (element) as that saves the reader having to search for first's definition to confirm its correctness.

The other function that really must be checked is scanf(), because users can (and will) enter unexpected text into your programs.

if (scanf("%d", &last->data) != 1) {
 /* error handling here */
}

Note there's no need for the intermediate variable var that was immediately copied from - just read directly into the destination.