Linear data structures – Lists – Doubly Linked List

This is a very simple implementation of linked list. We used a sentinel node (Header node).

First we define structure of a node and give it name of doublylinkedlist.


typedef struct _node{
    int data;
    struct _node *next;
    struct _node *prev;
} node;

typedef node doublyLinkedList;

We decide what are the operation we will perform and write the main function first. We will initiate the List, Insert elements (We insert in front and in end, just for fun!) and Delete elements.


int main(){

doublyLinkedList L;
int i;

Init(&L);

for(i=1; i < 10; i++)
    InsertInEND(i, &L);

for(i=10; i < 20; i++)
    Insert(i, &L);

for(i=1; i < 10; i += 2)
    Delete(i,&L);
}

First we write Init function, where we add a header node to the list.


void Init(doublyLinkedList * L){
L->next=NULL;
L->prev=NULL;
}

Now, we have a linked list ready. We insert 1 to 9 elements in it, using Insert function like below:

//this inserts in front
void Insert(int X, doublyLinkedList * L){

node * temp, * Q;
temp = (node *)malloc(sizeof(node));
if(temp!=NULL){
temp->data = X;
Q = L->next;

L->next = temp;
temp->prev = L;

temp->next = Q;
if(Q!=NULL)
Q->prev = temp;
}

printList(L);
}

//this inserts in end
void InsertInEND(int X, doublyLinkedList * L){

node * temp, *Q;

Q = L;

temp = (node *)malloc(sizeof(node));
temp->data = X;
temp->next = NULL;
temp->prev = NULL;

while(Q->next!=NULL){
Q = Q->next;
}

Q->next=temp;
temp->prev=Q;

printList(L);
}

And a method to Delete element X. Directly find the node which has X.


void Delete(int X, doublyLinkedList * L){

node * P;
node * temp;
P = L;

while(P!=NULL && P->data!=X)
P = P->next;

temp = P->prev;
temp->next = P->next;
if(P->next!=NULL)
(P->next)->prev = temp;
free(P);

printList(L);

}

Function to print list.


void printList(linearLinkedList * L){

node * P;
P=L->next;

while(P!=NULL){
printf("%d ",P->data);
P=P->next;
}
printf("\n");
}

Find method is not given here, but in Delete function itself we almost found the node which has element X.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s