Introduction to Linked List

In computer system, we have a situation that we want to add elements into the list at run time so for that we have to use a concept known as linked list. The list grows when elements are added and shrinks when elements are deleted. When list grows we need to allocate the memory space to the list to accommodate additional data items. Such situations can be handled by the dynamic data structure known as linked list. It provides the flexibility in adding, deleting or rearranging data items at run time. Through this technique we optimize the use of storage space.

Linked list is a way to store the elements into the list. It is a dynamic data structure or a linear collection of data element in which each data element points to the next element. A node is a basic element of the linked list. Each node is divided into two parts. The first part contains the data or information and second part contains a pointer which is used to link one node to the next node. There are four types of pointers in linked list

1.       start pointer: It contains the address of first node. If starting pointer is NULL then there is no element in list.

2.       NULL pointer: In linked list, the link field of the last node contains the NULL value so it is called NULL pointer.

3.       next pointer: It contains the address of the next node in the linked list.

4.       prev pointer: It contains the address of the prev node in the doubly linked list.

Representation of Linked List

In linked list, there are nodes and each node consists of two fields, one containing the information or data part and the other containing the address of the next node. The structure for the linked list is represented as follows:

struct node

{

int data;

struct node *next;

}*start;

The first member is an integer data and the second a pointer to a next node in the list. Remember, the data is an integer here only for simplicity and could be of any complex data type. Such structure, which contain a member field that points to the same structure type are called self-referential structure.