C Programming: Linked Lists

Linked Lists are data structures consisting of nodes that are linked together in sequence. Each node has it's data and a link to the next node. There are different types of linked lists. The basic ones are Singly Linked Lists and Doubly Linked Lists. We will tackle these in their most simple form to understand the concept quicker and better.

Singly Linked List
This list, at it's simplest form, contains data and a link to the next node. This is how it looks like visually:


Data structure:

Pointer next of type node is our pointer to the next node. Let it sink in... alright! If you don't understand, next is a pointer to another node which has data and another pointer next. This latter next, too, is a pointer to another node which has the same contents. Basically, you can think of it as a node inside a node inside a node inside a node, and so on.
Pointer start is a pointer to our FIRST node. And, data, is, of course, our data.
To indicate the end of the linked list, we will initialize the last next with a NULL value.

Here is a program for inserting at the End, inserting at the Front, and displaying the linked lists with a Singly Linked List.

Doubly Linked List
This list, at it's simplest form, contains data, a link to the next node, and a link to the previous node. This is how it looks like visually:


Data structure:

This is the same with Singly Linked List plus a pointer prev (previous). When we can only go from start to end with Singly Linked Lists, with Doubly Linked Lists, we can go from start to end, and end to start, as well.

Doubly Linked List program will come soon.

Study the images in order to understand better.