How to modularize a Linked List?

Question

I have the following Linked List:

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

struct Node
{
    int data; // Linked List type of data.
    struct Node *next; // Pointer to the next Node.
};

void printfList(struct Node *head)
{
    while(head != NULL)
    {
        printf(" %d\n", head -> data);
        head = head -> next;
    }
}


int main()
{
    struct Node *head   = NULL;
    struct Node *second = NULL;
    struct Node *third  = NULL;

    head   = (struct Node*) malloc(sizeof(struct Node));
    second = (struct Node*) malloc(sizeof(struct Node));
    third  = (struct Node*) malloc(sizeof(struct Node));

    head -> data = 1;
    head -> next = second;

    second -> data = 2;
    second -> next = third;

    third -> data = 3;
    third -> next = NULL;

    printfList(head);

    return 0;
}

How can I modularize this example to get something more professional? node type and separated from the others and function separately?

Answer 1

I think by "modularize" here you mean more kinda professional, clean looking code, I came up with following :

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

struct Node
{
    int data; // Linked List type of data.
    struct Node *next; // Pointer to the next Node.
};
struct Node * makeNode(int data){
    struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}
void printfList(struct Node *head)
{
    while(head != NULL)
    {
        printf(" %d\n", head -> data);
        head = head -> next;
    }
}


int main()
{
    struct Node *head, *prev;
    int i, n;
    printf("How many values you want to insert ?");
    scanf("%d", &n);
    printf("\nNow enter values :\n");
    for(i = 0; i < n; i++){
        int val;
        scanf("%d", &val);
        if(i == 0){
            head = makeNode(val);
            prev = head;
        }
        else{
            struct Node *temp = makeNode(val);
            prev->next = temp;
            prev = temp;
        }
    }

    printfList(head);

    return 0;
}

Hope it helps.

Answer 2

I'm not sure what you're looking to do, but I think you should start by reviewing the question: should a "node" be a property of an object (a struct data type) or should a "node" be an accessor to a data type...?

Both work and I've used both.

When I need to link existing objects together, than a node will contain a reference data type... but unlike your list, the data is always accessed using a pointer (not containing the actual data type, but only using a reference).

This allows one (object) to many (lists) relationships.

However, many times the data type itself will need to be "chained" (in a single list - one to one relationship), in which case the "node" is a property of the data type and can be re-used in many different types.

A list to link existing types

Here's an example code where I used a linked list to link existing objects using a void pointer.

I'm not sure this implementation adds anything to your initial concept, but it does show the "modularization" for a "one (objet) to many (lists)" approach.

/* *****************************************************************************
Simple List
***************************************************************************** */

typedef struct fio_ls_s {
  struct fio_ls_s *prev;
  struct fio_ls_s *next;
  void *obj;
} fio_ls_s;

#define FIO_LS_INIT(name)                                                      \
  { .next = &(name), .prev = &(name) }

/** Adds an object to the list's head. */
static inline __attribute__((unused)) void fio_ls_push(fio_ls_s *pos,
                                                       void *obj) {
  /* prepare item */
  fio_ls_s *item = (fio_ls_s *)malloc(sizeof(*item));
  if (!item)
    perror("ERROR: fiobj list couldn't allocate memory"), exit(errno);
  *item = (fio_ls_s){.prev = pos, .next = pos->next, .obj = obj};
  /* inject item */
  pos->next->prev = item;
  pos->next = item;
}

/** Adds an object to the list's tail. */
static inline __attribute__((unused)) void fio_ls_unshift(fio_ls_s *pos,
                                                          void *obj) {
  pos = pos->prev;
  fio_ls_push(pos, obj);
}

/** Removes an object from the list's head. */
static inline __attribute__((unused)) void *fio_ls_pop(fio_ls_s *list) {
  if (list->next == list)
    return NULL;
  fio_ls_s *item = list->next;
  void *ret = item->obj;
  list->next = item->next;
  list->next->prev = list;
  free(item);
  return ret;
}

/** Removes an object from the list's tail. */
static inline __attribute__((unused)) void *fio_ls_shift(fio_ls_s *list) {
  if (list->prev == list)
    return NULL;
  fio_ls_s *item = list->prev;
  void *ret = item->obj;
  list->prev = item->prev;
  list->prev->next = list;
  free(item);
  return ret;
}

/** Removes an object from the containing node. */
static inline __attribute__((unused)) void *fio_ls_remove(fio_ls_s *node) {
  void *ret = node->obj;
  node->next->prev = node->prev->next;
  node->prev->next = node->next->prev;
  free(node);
  return ret;
}

A list that is integrated in the data-type

Often I have objects that I know I will link together and that by nature will only belong to a single list ("one to one").

In these cases, placing the node struct data within the data-type allows better locality and improved performance through a single allocation for both the data and the node information.

A good enough example for such a situation can be examined is this SO answer.