DS - LINKED LISTS 3 (Doubly linked list)

Doubly Linked list

Doubly Linked list is data structure used for storing collections of data. It has following features.
* Each item in the list points to next item and previous item.
* One of the pointer of Last item of the list points to NULL.
* One of the pointer of First item of the list points to NULL.
* It can grow or shrink during execution of a program.
* There is no wastage of memory space.
* Can be made just as long as required.

Doubly Linked list::.

declaration:



struct trynode{
int data;
struct trynode *next;
struct trynode *back;
 };
typedef struct trynode* NODE;

one pointer (next) points to next item in the list.
another pointer (back) points to previous item.
data will hold the actual data of the each node.

Various operations that can be performed on the singly linked list:
1. Insert the node at the front end
2. Insert the node at rear end
3. Insert the node at specified position.
4. Delete the node from the front end
5. Delete the node from rear end
6. Delete the node from specified position.
7. Display the content of linked list.


1. Insert the node at the front end.
NODE insert_front(NODE first,int d)
{
    NODE temp;
    temp=(NODE)malloc(sizeof(struct student));
    temp->data=d;
        if(first==NULL){
    return temp;
}
    temp->back=NULL;
    temp->next=first;
    first->back=temp;
    return temp;
}

2. Insert the node at rear end

NODE insert_rear(NODE first,int d)
{
    NODE temp,cur;
    temp=(NODE)malloc(sizeof(struct student));
    temp->data=d;
    temp->next=NULL;
    temp->back=NULL;
    cur=first;
    while(cur->next!=NULL){
    cur=cur->next;}
    cur->next=temp;
    temp->back=cur;
    return first;
}

3. Insert the node at specified position.

NODE insert_pos(NODE first, int d,int pos)
{
    NODE temp,cur,prev;
    temp=(NODE)malloc(sizeof(struct student));
    temp->data=d;
    temp->next=NULL;
    temp->back=NULL;
    if(first==NULL)
        return temp;
    cur=first;
    for(i=1;i<pos;i++)
    {
        prev=cur;
        cur=cur->next;
    }
    prev->next=temp;
    temp->back=prev;
    temp->next=cur;
    cur->back=temp;
    return first;
}

4. Delete the node from the front end
5. Delete the node from rear end
6. Delete the node from specified position.
NODE delete(NODE first, int a)
{
    NODE temp,cur,prev;
    if(a==0)
    {
        cur=first;
        while(cur->next!=NULL){
        prev=cur;
        cur=cur->next;}
        prev->next=NULL;
        free(cur); return first;
    } else{
    cur=first;
    for(i=1;i<a;i++){
    prev=cur;
    cur=cur->next;}

    temp=cur->next;
    printf("\n ::: deleted is %d :: \n",cur->data);
    prev->next=temp;
    temp->back=prev;
    free(cur);
    return first;
}
}
7. Display the content of linked list.

void display(NODE first){
NODE temp;
  if(first==NULL)
    printf("\nList is empty");
else{
    temp=first;
    printf("\n content is :: \n");
 while(temp!=NULL)
      {
       printf("%d\n",temp->data);
       temp=temp->ptr_to_node;
      }
}
}


for complete program see DS - LINKED LISTS 4
http://dharmanath1244.blogspot.in/2015/08/ds-linked-lists-4-doubly-linked-list.html