# C - Linked List

A linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains two sub-elements. A data part that stores the value of the element and next part that stores the pointer to the next node as shown in the below image:

The first node also known as HEAD is always used as a reference to traverse the list. The last node points to NULL. Linked list can be visualized as a chain of nodes, where every node points to the next node.

## Types of Linked List

The types of linked list are mentioned below:

**Singly Linked List**: can be traversed only in forward direction.**Doubly Linked List**: can be traversed in forward and backward directions.**Circular Singly Linked List**: Last element contains link to the first element as next.**Circular Doubly Linked List**: Last element contains link to the first element as next and the first element contains link of the last element as previous.

## Implementation of Singly Linked List

### Representation:

In C, a node can be created using structure as shown below:

//node structure struct Node { int data; struct Node* next; };

### Create a Singly Linked List

Let us create a simple singly linked list which contains three data nodes.

#include <stdio.h> #include <stdlib.h> //node structure struct Node { int data; struct Node* next; }; // test the code int main() { //create the head node with name MyList struct Node* MyList = NULL; //Add first node. struct Node* first; //allocate second node in the heap first = (struct Node*)malloc(sizeof(struct Node)); first->data = 10; first->next = NULL; //linking with head node MyList = first; //Add second node. struct Node* second; //allocate second node in the heap second = (struct Node*)malloc(sizeof(struct Node)); second->data = 20; second->next = NULL; //linking with first node first->next = second; //Add third node. struct Node* third; //allocate third node in the heap third = (struct Node*)malloc(sizeof(struct Node)); third->data = 30; third->next = NULL; //linking with second node second->next = third; return 0; }

### Traverse a Singly Linked List

A singly linked list can be traversed using a temp node. Keep on moving the temp node to the next one and displaying its content. At the end of the list, the temp node will become NULL.

#include <stdio.h> #include <stdlib.h> //node structure struct Node { int data; struct Node* next; }; //display the content of the list void PrintList(struct Node* head_ref) { struct Node* temp = head_ref; if(head_ref != NULL) { printf("\nThe list contains: "); while (temp->next != NULL) { printf("%i ",temp->data); temp = temp->next; } printf("%i ",temp->data); } else { printf("\nThe list is empty."); } } // test the code int main() { //create the head node with name MyList struct Node* MyList = NULL; //Add first node. struct Node* first; //allocate second node in the heap first = (struct Node*)malloc(sizeof(struct Node)); first->data = 10; first->next = NULL; //linking with head node MyList = first; //Add second node. struct Node* second; //allocate second node in the heap second = (struct Node*)malloc(sizeof(struct Node)); second->data = 20; second->next = NULL; //linking with first node first->next = second; //Add third node. struct Node* third; //allocate third node in the heap third = (struct Node*)malloc(sizeof(struct Node)); third->data = 30; third->next = NULL; //linking with second node second->next = third; //print the content of list PrintList(MyList); return 0; }

The above code will give the following output:

The list contains: 10 20 30