C - Linked List Practice

Question

Been studying data structures in C to get more grasp on the fundamentals as a freshman at uni. This is a coding-challenge that I've given to myself to understand Linked Lists better.

Basically, my aim was to create 2 nodes, along with the node.header that i've written, which has the functions to add nodes to the head, body, or tail of the list.

And another function in that header to combine these two linked lists together into one.

How can I get this code better, do you see any mistakes or improvements that can be done with the working code? I think I got a better grasp on pointers more after coding this and planning to go deeper.

The code is already working, though there are bugs that I still am working on understanding pointers more and memory allocation,

such as free() function when used in the header gets my program go wild and not setting nextptr as null, i've mentioned this because they are commented in the code, as not working.

Main.c

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

void modify_nodes(struct node *list,struct node **head);
void create_nodes(struct node **head);

int main(){
    struct node *head = NULL;
        create_nodes(&head);
        puts("You're modifying the First one");
        modify_nodes(head,&head);

    struct node *head2 = NULL;
        create_nodes(&head2);
        puts("You're modifying the Second one");
        modify_nodes(head2,&head2);

    concatenate_lists(&head2,&head);
    print_list(head); //head2 doesnt work out here because i can't check out if there is a previous node or not.
}

void modify_nodes(struct node *list,struct node **head){
    enum choose_menu menu;
    int input_value;

    printf("To Add a Node to the Head, Press 1\n"
           "To Add a Node to the Middle, Press 2\n"
           "To Add a Node to the End, Press 3\n"
           "To Finish the process, Press 0\n\n"
           );
    scanf("%d",&input_value);
    while(input_value != END_OPERATION){
        scanf("%d",&input_value);
        if(input_value == ADD_HEAD){
            add_node_head(&list);
        }else if(input_value == ADD_MIDDLE){
            puts("Please enter at which place you want your node to be...");
            scanf("%d",&input_value);
            add_node_middle(&list,input_value);
        }else if(input_value == ADD_LAST){
            add_node_last(&list);
        }
    }
    *head = list;
}

void create_nodes(struct node **head){
    (*head) = (struct node*)malloc(sizeof(struct node));
        (*head)->value = 'x';
        (*head)->nextPtr = NULL;
}

node.h

#ifndef NODE_H_INCLUDED
#define NODE_H_INCLUDED
enum choose_menu{ADD_HEAD = 1, ADD_MIDDLE = 2, ADD_LAST = 3, END_OPERATION = 0};
struct node{
    char value;
    struct node *nextPtr;
};

void print_list(struct node *firstNode){
    while(firstNode != NULL){
        printf("%c--->",firstNode->value);
        firstNode = firstNode->nextPtr;
    }
    printf("NULL");
}

void add_node_head(struct node **head){
    struct node *add = NULL;
    add = (struct node*)malloc(sizeof(struct node));
    add->value = 'a';
    add->nextPtr = *head;

    *head = add;
    //free(add);
}

void add_node_last(struct node **head){
    struct node *new_ = NULL;
    new_ = (struct node*)malloc(sizeof(struct node));
    new_->nextPtr=NULL;
    new_->value = 'b';

    struct node *temp;
    temp = (struct node*)malloc(sizeof(struct node));
    temp = *head;
    while(temp->nextPtr != NULL){
        temp = temp->nextPtr;
    }
    temp->nextPtr = new_;
   /* free(temp);
    free(new_);*/
}

void add_node_middle(struct node **head,int position){
    struct node *newNode;
    newNode = (struct node*)malloc(sizeof(struct node));
    newNode->value = 'c';

    struct node *temp = *head;
    for(int i=2; i<position; i++){
        if(temp->nextPtr != NULL){
        temp = temp->nextPtr;
        }
    }
    newNode->nextPtr = temp->nextPtr;
    temp->nextPtr = newNode;
    //free(newNode);
}

void concatenate_lists(struct node **adding,struct node **beginning){
    struct node *temp = NULL;
        temp = (struct node*)malloc(sizeof(struct node));
    struct node *head = NULL;
        head = (struct node*)malloc(sizeof(struct node));
        temp = *beginning;
        head = temp;
    while(temp->nextPtr != NULL){
        temp = temp->nextPtr;
    }
    temp->nextPtr = *adding;
    *beginning = head;
    /*free(temp);
    free(head);*/
}


#endif // NODE_H_INCLUDED

Answer 1

Overall design

Linked list are often used quite heavily in an application such that there may be many, millions, of your link lists. Many of these, maybe even most, will be empty lists. To that end, I would forego the head node and use a null pointer to indicate an empty list.

Adding: O(n) or O(1)

Instead of using a loop to find the end, consider a linked-list that points to the end. The end.next then points to the beginning. Then adding to the front or back, deleting from the front, are all O(1). To walk the list, rather than look for a final next that is NULL, look for a next that is the same as end.

Abstract data

Rather than code char value, "%c", use typedef char ll_data, #define LL_FORMAT "%c" so one can rapidly amend code for other types.

Add function to consume the first node

Add function to free the entire linked list

Simplify malloc() usage

Cast not needed. Allocate to the size of the referenced data, not the type. Easier to code right, review and maintain.

// add = (struct node*)malloc(sizeof(struct node));
add = malloc(sizeof *add);
// or 
add = malloc(sizeof add[0]);

Test for allocation success

On out-of-memory, do something. Do you want to return an error indication, quit, ...

add = malloc(sizeof add[0]);
if (add == NULL) {
  TBD_code();
}

Use const

When the pointed-to-data is not changed, use const. This adds info to the function declaration, allows for some optimizations, and increases use.

// void print_list(struct node *firstNode){
void print_list(const struct node *firstNode) {

Put functions in a .c file

Coordinate names

Code is about link lists, not about nodes. Consider ll.h, ll.c, struct ll, ll_print(), ll_add_head(), enum ll_choose_menu, ll_concatenate(), ...

Favorite idea: apply()

A bit advanced, but add a function to that accepts the link list, a function and state variable to apply to every node of the list.

int ll_apply(struct ll *list, int (f)(void *state, struct ll *list), void *state);

Then for each node, from first to last call f(state, node). If the function returns non-zero, return immediately with that value, else go on to the next node.

Think of how easy then to use this to print the list, search the list, count the list, update nodes of the list, ... Just create a supporting function that handles one node. No need to create yet another iterator.

Answer 2

OK a lot to say here. First some basics

Do not put c code in a .h file. If you want to use your linked list twice in the same app, ie in prog_part1.c and prog_part2.c then it wont link. You have to create a link_list.c

life gets simpler if you typedef struct node Node;

Your test 'main' has all sorts of issues, like what happens if I enter a character. Test the returns from scanf.

I am not sure why you have that create_nodes function. It is not needed, I can call add_head_node with an empty list. I commented out the 2 calls to it and all still works fine

Major issues,

• you dont store any values in the list, that makes it not very useful at all. I mean you should as me for a value to store and your methods should store them , like add_node(Node*head, char value);

• if you are putting up code for review you should test the returns of everything, malloc for example.

• You need a free_list function, this is how to release things, walk down the list calling free on each node;

• you need a function to walk the list - get_next_node. I mean imagine I store things in the list and want to read them back, what will I do? print_list should not be a function, instead the non list code should call the walk function and then print.

• add_node_last has a memory leak

  struct node* temp; temp = (struct node*)malloc(sizeof(struct node)); temp = *head;

you allocate memory then throw away the pointer to it. As far as I can see the malloc is not needed at all. just say

  Node*temp = head;

• add_node_middle. first I would call this add_node_at, since I could add at the beginning or the end. Why do you start at 2. This introduces 2 errors, a) if I say position 2 I actaully get position 4, and I cant add at the first two positions. Does pos = 0 mean this is the new head. (Once you have taken that 2 out)

• in add_node_middle, break out of the loop on a NULL next

• concatenate lists has the same leak, you malloc two new nodes that you dont need then immediately throw away the pointers