Linked List with C

• Linked lists are the most basic self-referential structures. Linked lists allow you to have a chain of structs with related data.
• So how would you go about declaring a linked list? It would involve a struct and a pointer:
  

  struct llnode {
   data;
  struct llnode *next;
  };
  

  The signifies data of any type. This is typically a pointer to something, usually another struct. The next line is the next pointer to another llnode struct. Another more convenient way using typedef:
  

  typedef struct list_node {
   data;
  struct list_node *next;
  } llnode;
  
  llnode *head = NULL;
  

  Note that even the typedef is specified, the next pointer within the struct must still have the struct tag!
  
• There are two ways to create the root node of the linked list. One method is to create a head pointer and the other way is to create a dummy node. It's usually easier to create a head pointer.
• Now that we have a node declaration down, how do we add or remove from our linked list? Simple! Create functions to do additions, removals, and traversals.
  
  • Additions: A sample Linked list addition function:
    

    void add(llnode **head,  data_in) {
    llnode *tmp;
    
    if ((tmp = malloc(sizeof(*tmp))) == NULL) {
    ERR_MSG(malloc);
    (void)exit(EXIT_FAILURE);
    }
    tmp->data = data_in;
    tmp->next = *head;
    *head = tmp;
    }
    
    /* ... inside some function ... */
    llnode *head = NULL;
     *some_data;
    /* ... initialize some_data ... */
    
    add(&head, some_data);
    

    What's happening here? We created a head pointer, and then sent the address-of the head pointer into the add function which is expecting a pointer to a pointer. We send in the address-of head. Inside add, a tmp pointer is allocated on the heap. The data pointer on tmp is moved to point to the data_in. The next pointer is moved to point to the head pointer (*head). Then the head pointer is moved to point to tmp. Thus we have added to the beginning of the list.
  • Removals: You traverse the list, querying the next struct in the list for the target. If you get a match, set the current target next's pointer to the pointer of the next pointer of the target. Don't forget to free the node you are removing (or you'll get a memory leak)! You need to take into consideration if the target is the first node in the list. There are many ways to do this (i.e. recursively). Think about it!
  • Traversals: Traversing list is simple, just query the data part of the node for pertinent information as you move from next to next. There are different methods for traversing trees (see Trees).
• What about freeing the whole list? You can't just free the head pointer! You have to free the list. A sample function to free a complete list:
  

  void freelist(llnode *head) {
  llnode *tmp;
  
  while (head != NULL) {
  free(head->data);     /* Don't forget to free memory within the list! */
  tmp = head->next;
  free(head);
  head = tmp;
  }
  }
  

  Now we can rest easy at night because we won't have memory leaks in our lists!