A linked list is a way to store a collection of elements. Like an array these can be character or integers. Each element in a linked list is stored in the form of a node.
Node:
A node is a collection of two sub-elements or parts. A data part that stores the element and a next part that stores the link to the next node.
Linked List:
A linked list is formed when many such nodes are linked together to form a chain. Each node points to the next node present in the order. The first node is always used as a reference to traverse the list and is called HEAD. The last node points to NULL.
Declaring a Linked list :
In C language, a linked list can be implemented using structure and pointers .
struct LinkedList{ int data; struct LinkedList *next; };The above definition is used to create every node in the list. The data field stores the element and the next is a pointer to store the address of the next node.
Noticed something unusual with next?
In place of a data type, struct LinkedList is written before next. That's because its a self-referencing pointer. It means a pointer that points to whatever it is a part of. Here next is a part of a node and it will point to the next node.
Creating a Node:
Let's define a data type of struct LinkedListto make code cleaner.
typedef is used to define a data type in C.
malloc[] is used to dynamically allocate a single block of memory in C, it is available in the header file stdlib.h.
sizeof[] is used to determine size in bytes of an element in C. Here it is used to determine size of each node and sent as a parameter to malloc.
The above code will create a node with data as value and next pointing to NULL.
Let's see how to add a node to the linked list:
node addNode[node head, int value]{ node temp,p;// declare two nodes temp and p temp = createNode[];//createNode will return a new node with data = value and next pointing to NULL. temp->data = value; // add element's value to data part of node if[head == NULL]{ head = temp; //when linked list is empty } else{ p = head;//assign head to p while[p->next != NULL]{ p = p->next;//traverse the list until p is the last node.The last node always points to NULL. } p->next = temp;//Point the previous last node to the new node created. } return head; }Here the new node will always be added after the last node. This is known as inserting a node at the rear end.
Food for thought
This type of linked list is known as simple or singly linked list. A simple linked list can be traversed in only one direction from head to the last node.
The last node is checked by the condition :
p->next = NULL;Here -> is used to access next sub element of node p. NULL denotes no node exists after the current node , i.e. its the end of the list.
Traversing the list:
The linked list can be traversed in a while loop by using the head node as a starting reference:
node p; p = head; while[p != NULL]{ p = p->next; }Contributed by: Mohd Sanad Zaki Rizvi