DSA-I 5: Doubly Linked List – Dynamic Implementation
Set A
a) Implement a list library (doublylist.h) for a doubly linked list with the above four operations. Write a menu driven driver program to call the operationsappend, insert, delete specific node, delete at position, search, display.
The User-defined header file:
#include<stdio.h>
#include<stdlib.h>
struct node
{
char data;
struct node *next,*prev;
}*start;
void create()
{
struct node *temp,*q;
temp=(struct node *)malloc(sizeof(struct node));
printf("\nEnter a character:");
scanf(" %c",&temp->data);
temp->next=NULL;
temp->prev=NULL;
if(start==NULL)
{
start=temp;
}
else
{
q=start;
while(q->next!=NULL)
{
q=q->next;
}
q->next=temp;
temp->prev=q;
}
}
void display()
{
struct node *temp;
if(start==NULL)
{
printf("\nLinked List is empty\n");
return;
}
printf("The Linked List:\n");
temp=start;
while(temp!=NULL)
{
printf("%d<-%c->%d->|",temp->prev,temp->data,temp->next);
temp=temp->next;
}
}
void delete()
{
struct node *temp,*p;
int pos,t;
printf("\nEnter the position:");
scanf("%d",&pos);
t=1;
temp=start;
if(start==NULL)
{
printf("\nLinked List is empty\n");
return;
}
if(start->next==NULL)
{
free(start);
start=NULL;
printf("\nNode Deleted Successfully\n");
return;
}
if(pos==1)
{
start=start->next;
start->prev=NULL;
free(temp);
printf("\nNode Deleted Successfully\n");
return;
}
while(t< pos)
{ temp=temp->next;
t++;
}
temp->prev->next=temp->next;
if(temp->next!=NULL)
{
temp->next->prev=temp->prev;
}
free(temp);
printf("\nNode deleted successfully\n");
}
#include<stdio.h>
#include "dll.h"
void main()
{
int c;
start=NULL;
while(1)
{
printf("\n1.Create\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Exit\n");
printf("Enter your choice: ");
scanf("%d",&c);
switch(c)
{
case 1:create(); break;
case 2:delete(); break;
case 3:display(); break;
case 4:exit(0);
}
}
}
Save this file as linkedlist.c and compile and run the linkedlist.c
b) Implement a list library (doublylist.h) for a doubly linked list. Create a linked list, reverse it and display reversed linked list.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;
void createList(int n);
void displayList();
void reverseList();
int main()
{
int n, data, choice=1;
head = NULL;
last = NULL;
while(choice != 0)
{
printf("============================================\n");
printf("DOUBLY LINKED LIST PROGRAM\n");
printf("============================================\n");
printf("1. Create List\n");
printf("2. Reverse List\n");
printf("3. Display list\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter the total number of nodes in list: ");
scanf("%d", &n);
createList(n);
break;
case 2:
reverseList();
break;
case 3:
displayList();
break;
case 0:
break;
default:
printf("Error! Invalid choice. Please choose between 0-3");
}
printf("\n\n\n\n\n");
}
return 0;
}
void createList(int n)
{
int i, data;
struct node *newNode;
if(n >= 1)
{
head = (struct node *)malloc(sizeof(struct node));
printf("Enter data of 1 node: ");
scanf("%d", &data);
head->data = data;
head->prev = NULL;
head->next = NULL;
last = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
printf("Enter data of %d node: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->prev = last; // Link new node with the previous node
newNode->next = NULL;
last->next = newNode; // Link previous node with the new node
last = newNode; // Make new node as last/previous node
}
printf("\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n");
}
}
void displayList()
{
struct node * temp;
int n = 1;
if(head == NULL)
{
printf("List is empty.\n");
}
else
{
temp = head;
printf("DATA IN THE LIST:\n");
while(temp != NULL)
{
printf("DATA of %d node = %d\n", n, temp->data);
n++;
temp = temp->next;
}
}
}
void reverseList()
{
struct node *current, *temp;
current = head;
while(current != NULL)
{
temp = current->next;
current->next = current->prev;
current->prev = temp;
current = temp;
}
temp = head;
head = last;
last = temp;
printf("LIST REVERSED SUCCESSFULLY.\n");
}
Set B
a)There are lists where insertion should ensure the ordering of data elements. Since the elements are in ascending order the search can terminate once equal or greater element is found. Implement a doubly linked list of ordered integers(ascending/descending) with insert, search and display operations.
#include<stdio.h>
#include<stdlib.h>
struct Node;
typedef struct Node * PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node
{
int e;
Position previous;
Position next;
};
void Insert(int x, List l, Position p)
{
Position TmpCell;
TmpCell = (struct Node*) malloc(sizeof(struct Node));
if(TmpCell == NULL)
printf("Memory out of space\n");
else
{
TmpCell->e = x;
TmpCell->previous = p;
TmpCell->next = p->next;
p->next = TmpCell;
}
}
int isLast(Position p)
{
return (p->next == NULL);
}
Position Find(int x, List l)
{
Position p = l->next;
while(p != NULL && p->e != x)
p = p->next;
return p;
}
void Delete(int x, List l)
{
Position p, p1, p2;
p = Find(x, l);
if(p != NULL)
{
p1 = p -> previous;
p2 = p -> next;
p1 -> next = p -> next;
if(p2 != NULL) // if the node is not the last node
p2 -> previous = p -> previous;
}
else
printf("Element does not exist!!!\n");
}
void Display(List l)
{
printf("The list element are :: ");
Position p = l->next;
while(p != NULL)
{
printf("%d -> ", p->e);
p = p->next;
}
}
void main()
{
int x, pos, ch, i;
List l, l1;
l = (struct Node *) malloc(sizeof(struct Node));
l->previous = NULL;
l->next = NULL;
List p = l;
printf("DOUBLY LINKED LIST IMPLEMENTATION OF LIST ADT\n\n");
do
{
printf("\n\n1. INSERT\t 2. DELETE\t 3. FIND\t 4. PRINT\t 5. QUIT\n\nEnter the choice :: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
p = l;
printf("Enter the element to be inserted :: ");
scanf("%d",&x);
printf("Enter the position of the element :: ");
scanf("%d",&pos);
for(i = 1; i < pos; i++)
{
p = p->next;
}
Insert(x,l,p);
break;
case 2:
p = l;
printf("Enter the element to be deleted :: ");
scanf("%d",&x);
Delete(x,p);
break;
case 3:
p = l;
printf("Enter the element to be searched :: ");
scanf("%d",&x);
p = Find(x,p);
if(p == NULL)
printf("Element does not exist!!!\n");
else
printf("Element exist!!!\n");
break;
case 4:
Display(l);
break;
}
}
while(ch<5);
}
b)There are lists where new elements are always appended at the end of the list. The list can be implemented as a circular list with the external pointer pointing to the last element of the list. Implement doubly linked circular list of integers with append and display operations. The operation append(L, n), appends to the end of the list, n integers either accepted from user or randomly generated.
No comments:
Post a Comment