How to Create a Linked List in C

In C, a linked list allows you to create a list without deciding ahead of time how long it might be, and without wasting memory by allocating elements you don't have yet. The downside is that you have to do all the work of organizing and managing the list in memory.

Difficulty:

Easy

Instructions

Create the Data Structure

1. Choose a name, then use typedef to define it. Every linked list will need a structure, even if it only has one variable:
   

   typedef struct product_data PRODUCT_DATA;

2. Define the structure. The last element should be a pointer to the type you just defined, and named "next":
   

   struct product_data {
    int product_code;
    int product_size;
    PRODUCT_DATA *next;
   };

3. Allocate two pointers to this data structure, initializing them to NULL, to be the list "head" and "tail":
   

   PRODUCT_DATA *products_head = NULL;
   PRODUCT_DATA *products_tail = NULL;

Add to the List

1. Allocate a temporary variable that's a pointer to the data structure:
   

   PRODUCT_DATA *newproduct;

2. Use malloc() to create a new element, always checking for an error:
   

   if ((newproduct = malloc(sizeof(PRODUCT_DATA))) == NULL) { abort(); }

3. Populate the new element's fields. Set its "next" field to NULL:
   

   newproduct->product_code = newcode;
   newproduct->product_size = newsize;
   newproduct->next = NULL;

4. Set the head variable. If the head variable is NULL, this is the first element added to the list, so set the head variable to point to it:
   

   if (!products_head) products_head = newproduct;

5. Prepare for a different variable. In other cases, the tail variable points to the last item on the list, so set its next value to point to the new item:
   

   else products_tail->next = newproduct;

6. Update the tail to point to the new last element, in either case:
   

   products_tail = newproduct;

Access the List

1. Create another temporary variable pointing to the data structure:
   

   PRODUCT_DATA *product;

2. Set your temporary variable to the head variable:
   

   product = products_head;

3. Loop through the elements, checking each one and then setting the temporary variable to the next pointer to traverse to the next one:
   

   while (product) { if (product->product_code != 15) { product = product->next; } }

4. Check if the variable is NULL. If so, you never found the item:
   

   if (!product) return 0;

   . Otherwise, it points to the item you were looking for:
   

   return product->product_size;

Clean Up Your Work

1. Deallocate the list when your program ends, as not all operating systems will handle this automatically.

2. Loop as long as the head variable is not NULL:
   

   while (products_head) {

3. Store its next pointer in the tail variable temporarily:
   

    products_tail = products_head->next;

4. Deallocate the element:
   

    free(products_head);

5. Set the head pointer to the pointer you saved in step 4:
   

    products_head = products_tail;
   }

Tips & Warnings

• It's a good idea to create a C function to add to the linked list, then always use it instead of doing this directly.

• "Doubly linked lists" make deletes and some searches more efficient by using a "previous" pointer along with the "next" pointer, but they make adds less efficient.

• Deleting from the list is similar to adding to it, but you'll need to find its predecessor and change its next pointer to the deleted element's next pointer, bypassing it, before deallocating it. Deleting the first or last elements will require updating the head or tail variables instead.

• It's possible to sort a C linked list, and it can be very efficient to do so, since it's only pointers, not actual data, that you must move and copy. However, it's a complicated algorithm.