How to Create a Linked List in C

Contributor

By eHow Contributing Writer

Article Rating:

(43 Ratings)

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

Step 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;
```
Step 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;
};
```
Step 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

Step 1

Allocate a temporary variable that's a pointer to the data structure:
```
PRODUCT_DATA *newproduct;
```
Step 2

Use malloc() to create a new element, always checking for an error:
```
if ((newproduct = malloc(sizeof(PRODUCT_DATA))) == NULL) { abort(); }
```

Step 3

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

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

Step 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;
```
Step 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;
```
Step 6

Update the tail to point to the new last element, in either case:
```
products_tail = newproduct;
```

Access the List

Step 1

Create another temporary variable pointing to the data structure:
```
PRODUCT_DATA *product;
```
Step 2

Set your temporary variable to the head variable:
```
product = products_head;
```
Step 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; } }
```
Step 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

Step 1

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

Loop as long as the head variable is not NULL:
```
while (products_head) {
```
Step 3

Store its next pointer in the tail variable temporarily:
```
 products_tail = products_head->next;
```
Step 4

Deallocate the element:
```
 free(products_head);
```
Step 5

Set the head pointer to the pointer you saved in step 4:
```
 products_head = products_tail;
}
```

Comments

zainka said

Flag This Comment

on 5/4/2009 I believe there is an error in Step3 under "Access the list". The if should have an else with the break; statement. Else you will never leave the loop...Else the tut. is simple to understand1