A linked list is a data structure which can change during execution.
Structure used for variable data set.
Unlike an array, stores data non-contiguously.
Each record of a linked list is often called an Element or Node.
Consists of a sequence of nodes each of which contains a reference (i.e., a link) to the next node in the sequence.
Linked lists allow insertion and removal of nodes at any point in the list.
Various types of linked lists:
Linked lists are the basis of advanced data structures.
The nodes of linked list contain two fields:
Topics covered in this snack-sized chapter:
- Data field: an abstract data type.
- Next Field: a link to the next node.
- Last node link in linked list is represented by NULL.
They can be used to implement:
Singly linked lists contain nodes which have a data field as well as a next field, which points to the next node in the linked list.
In a doubly linked list, each node contains, besides the next-node link, a second link field pointing to the previous node in the sequence. The two links may be called forward(s) and backwards, or next and previous.
In the last node
of a list, the link field often contains a null reference, a special value used to indicate the lack of further nodes.
A less common convention is to make it point to the first node of the list; in that case the list is said to be circular or circularly linked; otherwise it is said to be open or linear.
In a multiply linked list, each node contains two or more link fields, each field being used to connect the same set of data records in a different order (e.g., by name, by department, by date of birth, etc.).
/*c program for creating singly linked list*/
struct single_link_list *next;
typedef struct single_link_list node;
node *makenode(int );
node *start,*last,*nn; //nn=new node
printf("Enter your age and if you want to exit, press 0 : ");
start = nn;
last = nn;
last->next = nn;
last = nn;
printf("\n\t****Single linked list****\n\n");
for(; start!=NULL; start=start->next)
/*creation of node*/
node *makenode(int tmp)
nn = (node *)malloc(sizeof(node));
nn->age = tmp;
nn->next = NULL;
Enter your age and if you want to exit, press 0 : 25
Enter your age and if you want to exit, press 0 : 0
****Single linked list****
While doubly linked lists can be seen as special cases of multiply linked list, the fact that the two orders are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a separate case.