A double linked list is a two-way list in which all nodes will have two links - one to the next node and another to the previous node.
Each node consists of three parts
- A pointer to the previous Node ( PREV )
- Data
- A pointer to the next Node ( NEXT )
The PREV field is uses to store the address of the predecessor node, which enables us to traverse the list in the backward direction. The NEXT field is uses to store the address of the successor node , which enables us to traverse the list in the forward direction.
The PREV field of the first node and the NEXT field of the last node will contain NULL
The main advantage of using a doubly linked list is that it makes searching twice as efficient and provides bi-directional traversing.
Structure of a doubly linked list
struct DLL
{
struct DLL *prev;
int data;
struct DLL *next;
};
typedef struct DLL node;
node *start = NULL;
Creating a node for Double Linked List
node* createnode()
{
node* newnode;
newnode = (node *) malloc(sizeof(node));
printf("\n Enter the data: ");
scanf("%d", &newnode -> data);
newnode -> prev = NULL;
newnode -> next = NULL;
return newnode;
}
Creating a Double Linked List with 'N' number of nodes
Step 1: CREATE THE NEW NODE USING createnode()
NEW_NODE = createnode();
Step 2: If the linked list is empthy (START == NULL)
START = NEW_NODE
Step 3: If the linked list is not empthy
PTR = START
while(PTR -> NEXT != NULL)
{
PTR = PTR -> NEXT
}
PTR -> NEXT = NEW_NODE
NEW_NODE -> PREV = PTR
Step 4 : Repeat Steps 1,2,3 'N' times.
Step 5 : EXIT
0 Comment to "Doubly Linked List - data structures and algorithm"
Post a Comment