In a doubly linked list, also called a two-way list, each node is divided into three parts:
- The first part, called the previous pointer field, contains the address of the preceding element in the list.
- The second part contains the information of the list.
- The third part, called the next pointer field, contains the address of the succeeding element in the list.
In addition, two pointer variables, named head and tail, are used that contain the address of first element and the address of last element of the list.
Implementation of a Doubly Linked List in C
Suppose we want to store list of integers. Then, we define the following self-referential structure:
.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }
typedef struct nodetype
{
struct nodetype *prev;
int info;
struct nodetype *next;
}node;
node *head,*tail;
The above declaration defines a new data type called "struct nodetype" with a typedef of "node". Two node pointers are also declared: head and tail.
Creating an Empty List
- In the previous declaration, the variables head and tail are each declared as a pointer to a "node".
- These variables are not yet initialized.
- "head" is used to point to the first element of the list and "tail" is used to point to the last element of the list.
- Since the list will be empty in the beginning, the variables head and tail should be assigned a sentinel value to indicate the list is empty.
void createemptylist(node **head, node **tail)
{
*head=*tail=NULL;
}
A call to the above function will need to pass the addresses of head and tail (as double pointers) as follows: createemptylist(&head, &tail);
Operations on Doubly Linked Lists
The following operations can be performed on doubly linked lists:
Doubly Linked List – Sample Program
/*
* Doubly Linked List
* https://www.tech-faq.com
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct node
{
struct node *prev;
int data;
struct node *next;
} Node;
/*MakeNode: Make a newnode inserting data into it .
Return the newnode's address*/
Node *MakeNode(int data)
{
Node *p=malloc(sizeof (Node));
p->data = data;
return p;
}
/*Insert: Insert new data in the list at position specified by pos, beginning from 1
pos is invalid if < 1. If pos>length of list, insert at end*/
void Insert(int pos, int data, Node **start)
{
if (pos<1)
{
puts("Invalid position");
return;
}
if (*start == NULL)
{
*start = MakeNode(data);
(*start)->prev = NULL;
(*start)->next = NULL;
}
else
{
Node *curr=*start;
for (;curr->next && pos>1; pos--)
curr = curr->next;
if (pos > 1 ) /*insert at end*/
{
Node *newnode = MakeNode(data);
newnode->prev = curr;
newnode->next = curr->next;
curr->next = newnode;
}
else if (curr==*start) /*insert at beginning*/
{
Node *newnode = MakeNode(data);
newnode->prev = curr->prev;
newnode->next = curr;
curr->prev = newnode;
*start = newnode;
}
else
{
Node *newnode = MakeNode(data);
newnode->prev = curr->prev;
newnode->next = curr;
curr->prev->next = newnode;
curr->prev = newnode;
}
}
}
void DeleteByPosition(int pos, Node **start)
{
if (pos<1 || *start==NULL)
puts("Invalid position");
else if (pos==1) /*delete first node*/
{
Node *temp = *start;
*start = (*start)->next;
free(temp);
}
else /*find the position*/
{
Node *temp = *start;
for (;temp && pos>1; pos--)
temp = temp->next;
if (temp==NULL)
puts("Invalid position");
else
{
temp->prev->next = temp->next;
if (temp->next)
temp->next->prev = temp->prev;
free(temp);
}
}
}
void DeleteByValue(int value, Node **start)
{
if ((*start)->data == value) /*delete first node*/
{
Node *temp = *start;
*start = (*start)->next;
free(temp);
}
else /*find the node*/
{
Node *temp = (*start)->next;
for (; temp && temp->data!=value; temp=temp->next)
;
if (temp==NULL)
puts("Element not found");
else
{
temp->prev->next = temp->next;
if (temp->next)
temp->next->prev = temp->prev;
free(temp);
}
}
}
void Traverse(Node *x)
{
int cnt=1;
while (x)
{
printf("%d: %dn", cnt++, x->data);
x = x->next;
}
}
void TraverseInReverse(Node *x)
{
int cnt=1;
if (x)
{
while (x->next) /*Go to the end*/
{
x = x->next;
cnt++;
}
while (x)
{
printf("%d: %dn", cnt--, x->data);
x = x->prev;
}
}
}
int menu(void)
{
int choice;
puts("1-Insert data at end");
puts("2-Insert at beginning");
puts("3-Insert at position");
puts("4-Delete by position");
puts("5-Delete by element");
puts("6-Display");
puts("7-Display in reverse");
puts("8-Exit");
printf("Enter choice: ");
scanf("%d", &choice);
while (getchar()!='n')
;
return choice;
}
/* Test driver. Note: gets() is unsafe and
* should not be used in production environments.
* Its use here is only for illustration.
*/
int main(void)
{
Node *start = NULL;
char input[10];
int pos;
while(1)
{
switch(menu())
{
case 1:
puts("Enter numbers, blank line to stop");
while (gets(input)[0])
Insert(INT_MAX, atoi(input), &start);
break;
case 2:
printf("Enter number: ");
Insert(1, atoi(gets(input)), &start);
break;
case 3:
printf("Enter position: ");
pos = atoi(gets(input));
printf("Enter number: ");
Insert(pos, atoi(gets(input)), &start);
break;
case 4:
printf("Enter position: ");
DeleteByPosition(atoi(gets(input)), &start);
break;
case 5:
printf("Enter value: ");
DeleteByValue(atoi(gets(input)), &start);
break;
case 6:
Traverse(start);
&nsp; break;
case 7:
TraverseInReverse(start);
break;
case 8:
exit(0);
}
}
}
Follow Us!