C Programming - Linked Lists

In this tutorial you will learn about C Programming - Linked Lists, Structure, Advantages of Linked List, and Types of linked list and Applications of linked lists.

Linked lists are a type of data structure for storing information as a list. They are a memory efficient alternative to arrays because the size of the list is only ever as large as the data. Plus they do not have to shift data and recopy when resizing as dynamic arrays do.

They do have the extra overhead of 1 or 2 pointers per data node, so they make sense only with larger records. You would not want to store a list of integers in a linked list because it would actually double your memory overhead over the same list in an array.

There are three different types of linked lists, but the other two are just variations of the basic singly linked list. If you understand this linked list then you will be able to handle other two types of lists.

Advantages of Linked Lists

A linked list is a dynamic data structure and therefore the size of the linked list can grow or shrink in size during execution of the program. A linked list does not require any extra space therefore it does not waste extra memory. It provides flexibility in rearranging the items efficiently.

The limitation of linked list is that it consumes extra space when compared to a array since each node must also contain the address of the next item in the list to search for a single item in a linked list is cumbersome and time consuming process.

Linked lists Types

There are 4 different kinds of linked lists:

1. Linear singly linked list
2. Circular singly linked list
3. Two way or doubly linked list
4. Circular doubly linked list.

Linked List Nodes

A linked list gets their name from the fact that each list node is "linked" by a pointer. A linked list node is comparable to an array element. A node contains a data portion and a pointer portion, and is declared as structs in C.

As an example, we can implement a list of high scores for a game as a linked list.

Let us now declare a node:

We have two variables that make up the data portion of the node, and then the pointer to the next node in the list.

Creating Linked Lists

A linked list always has a base node that is most commonly called a head, but some call it as a root. An empty linked list will have this node and will be set to NULL. This goes for all three types of linked lists. The last node in a linked list always points to NULL.

Let us declare our linked list for implementing high scores list.

struct llnode *head = NULL;

Here we just declared a regular pointer variable of the node struct we declared, and then set the head to NULL to indicate the list is empty.

Traversing a Linked List

Moving through a linked list and visiting all the nodes is called traversing the linked list. There is more than one way to encounter segmentation faults when traversing a linked list, but if you are careful and follow 2 basic checks you will be able to handle segmentation faults.

To traverse a singly linked list you create a pointer and set it to head. Often called the current node as a reminder that it is keeping track of the current node. Always make sure to check that head is not NULL before trying to traverse the list or you will get a segmentation fault. You may also need to check that the next pointer of the current node is not NULL, if not, you will go past the end of the list and create a segmentation fault.

Here is a failsafe way of traversing a singly linked list:

We first check that the head is not NULL and if so, as long as the current pointer's next is not NULL, we set current equal to the next node effectively moving through the entire list until we do encounter a next pointer that is NULL.

If you follow that formula, you will have no problems with segmentation faults during traversal.