Concept of Linked List

Concept of Linked List

• Definition: A linked list is a set of nodes where each node has two fields 'data' and a 'link'. Where data field stores the actual piece of information and 'link' field is used to point to next node. Basically link field is nothing but the address only.

• Note that the link field of last node consists of 'NULL' which indicates end of linked list.

'C' Representation of Linked List

'C' structure

typedef struct node

{

int data; /* data field */0

struct node * next; /* link field */

} SLL;

• while declaring C structure for a linked list -

• Declare a structure in which two members are there i.e. data member and next pointer member.

• The data member can be character or integer or real kind of data depending upon the type of the information that the linked list is having.

• The 'next' member is essentially of a pointer type. And the pointer should be of structure type. Because the 'next' field holds the address of next node. And each node is basically a structure consisting of 'data' and 'next'.

Types of Linked List

There are various types of linked lists such as,

• Singly linear linked list

• Singly circular linked list

• Doubly linear linked list

• Doubly circular linked list.

Let us see each of the above one by one.

• Singly linear linked list (SLL):

It is called singly because this list consists of only one link, to point to next node or element. This is also called linear list because the last element points to nothing it is linear is nature. The last field of last node is NULL which means that there is no further list. The very first node is called head or first.

• Singly circular linked list :

In this type of linked list only one link is used to point to next element and this list is circular means that the last node's link field points to the first or head node. That means according to example after 40 the next number will be 10. So the list is circular in nature.

Doubly linear linked list :

This list called doubly because each node has two pointers previous and next pointers. The previous pointer points to previous node and next pointer points to next node. Only in

case of head node the previous pointer is obviously NULL and last node's next pointer points to NULL. This list is a linear one.

• Doubly circular linked list :

In circular doubly linked list the previous pointer of first node and the next pointer of last node is pointed to head node. Head node is a special node which may have any dummy data or it may have some useful information such as total number of nodes in the list which may be used to simplify the algorithms carrying various operations on the list.