Scribd
Upload
4 views15 pages

Ds Lab 4 Programs

The document provides implementations of a doubly linked list and a circular linked list in C, detailing various operations such as insertion, deletion, and traversal. It includes code snippets for creating nodes, inserting and deleting nodes at both ends, and displaying the lists in both forward and backward directions. The main function allows user interaction to perform these operations through a menu-driven interface.

Uploaded by

yugandharpowerofmind
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views15 pages

Ds Lab 4 Programs

The document provides implementations of a doubly linked list and a circular linked list in C, detailing various operations such as insertion, deletion, and traversal. It includes code snippets for creating nodes, inserting and deleting nodes at both ends, and displaying the lists in both forward and backward directions. The main function allows user interaction to perform these operations through a menu-driven interface.

Uploaded by

yugandharpowerofmind
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Week 4:

4.1 Implement a doubly linked list and perform various operations to


understand its properties and applications.
#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node *prev;
struct Node *next;
};

struct Node *head = NULL;

// Create new node


struct Node* createNode(int value)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}

// Insert at beginning
void insertBeginning(int value)
{
struct Node *newNode = createNode(value);

if (head == NULL) {
head = newNode;
return;
}
newNode->next = head;
head->prev = newNode;
head = newNode;
}
// Insert at end
void insertEnd(int value)
{
struct Node *newNode = createNode(value);

if (head == NULL)
{
head = newNode;
return;
}

struct Node *temp = head;


while(temp->next != NULL)
temp = temp->next;

temp->next = newNode;
newNode->prev = temp;
}

// Delete from beginning


void deleteBeginning( )
{
if (head == NULL) {
printf("List is empty\n");
return;
}

struct Node *temp = head;


head = head->next;

if(head != NULL)
head->prev = NULL;

printf("Deleted %d from beginning\n", temp->data);


free(temp);
}
// Delete from end
void deleteEnd( )
{
if(head == NULL)
{
printf("List is empty\n");
return;
}

struct Node *temp = head;


// only one node
if (temp->next == NULL)
{
printf("Deleted %d from end\n", temp->data);
free(temp);
head = NULL;
return;
}

while(temp->next != NULL)
temp = temp->next;

printf("Deleted %d from end\n", temp->data);


temp->prev->next = NULL;
free(temp);
}

// Display from head to tail


void displayForward( )
{
struct Node *temp = head;
if(temp == NULL)
{
printf("List is empty\n");
return;
}

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

// Display from tail to head


void displayBackward( )
{
if (head == NULL)
{
printf("List is empty\n");
return;
}

struct Node *temp = head;


while(temp->next != NULL)
temp = temp->next; // go to last node

printf("Backward: NULL");
while(temp != NULL)
{
printf(" <-> %d", temp->data);
temp = temp->prev;
}
printf("\n");
}

int main( )
{
int choice, value;

while (1) {
printf("\n1. Insert at beginning\n");
printf("2. Insert at end\n");
printf("3. Delete from beginning\n");
printf("4. Delete from end\n");
printf("5. Display forward\n");
printf("6. Display backward\n");
printf("7. Exit\n");
printf("Enter choice: ");
scanf("%d", &choice);

switch (choice)
{
case 1:
printf("Enter value: ");
scanf("%d", &value);
insertBeginning(value);
break;
case 2:
printf("Enter value: ");
scanf("%d", &value);
insertEnd(value);
break;
case 3:
deleteBeginning();
break;
case 4:
deleteEnd();
break;
case 5:
displayForward();
break;
case 6:
displayBackward();
break;
case 7:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
} Output:
1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Display forward
6. Display backward
7. Exit
Enter choice: 1
Enter value: 5

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Display forward
6. Display backward
7. Exit
Enter choice: 2
Enter value: 10

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Display forward
6. Display backward
7. Exit
Enter choice: 2
Enter value: 15

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Display forward
6. Display backward
7. Exit
Enter choice: 2
Enter value: 20

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Display forward
6. Display backward
7. Exit
Enter choice: 3
Deleted 5 from beginning

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Display forward
6. Display backward
7. Exit
Enter choice: 5
Forward: 10 <-> 15 <-> 20 <-> NULL

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Display forward
6. Display backward
7. Exit
Enter choice: 6
Backward: NULL <-> 20 <-> 15 <-> 10

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Display forward
6. Display backward
7. Exit
Enter choice: 7

4.2 Implement a circular linked list and perform insertion, deletion, and
traversal.

#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node *next;
};

struct Node *head = NULL;

// Create new node


struct Node* createNode(int value)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

// Insert at beginning
void insertBeginning(int value)
{
struct Node *newNode = createNode(value);

if (head == NULL)
{
head = newNode;
newNode->next = head; // points to itself
return;
}

struct Node *temp = head;


while(temp->next != head) // go to last node
temp = temp->next;

newNode->next = head;
temp->next = newNode;
head = newNode;
}

// Insert at end
void insertEnd(int value)
{
struct Node *newNode = createNode(value);
if(head == NULL)
{
head = newNode;
newNode->next = head;
return;
}

struct Node *temp = head;


while(temp->next != head)
temp = temp->next;

temp->next = newNode;
newNode->next = head;
}

// Delete from beginning


void deleteBeginning( )
{
if (head == NULL)
{
printf("List is empty\n");
return;
}

struct Node *temp = head;

// only one node


if(head->next == head)
{
printf("Deleted %d\n", head->data);
free(head);
head = NULL;
return;
}

struct Node *last = head;


while(last->next != head)
last = last->next;

head = head->next;
last->next = head;
printf("Deleted %d\n", temp->data);
free(temp);
}

// Delete from end


void deleteEnd( )
{
if (head == NULL) {
printf("List is empty\n");
return;
}

struct Node *temp = head;


// only one node
if(head->next == head)
{
printf("Deleted %d\n", head->data);
free(head);
head = NULL;
return;
}

struct Node *prev = NULL;


while (temp->next != head)
{
prev = temp;
temp = temp->next;
}

prev->next = head;
printf("Deleted %d\n", temp->data);
free(temp);
}

// Traverse / display
void traverse( )
{
if(head == NULL)
{
printf("List is empty\n");
return;
}

struct Node *temp = head;


printf("Circular list: ");
do{
printf("%d -> ", temp->data);
temp = temp->next;
}while (temp != head);
printf("(back to head)\n");
}

int main( )
{
int choice, value;
while (1) {
printf("\n1. Insert at beginning\n");
printf("2. Insert at end\n");
printf("3. Delete from beginning\n");
printf("4. Delete from end\n");
printf("5. Traverse\n");
printf("6. Exit\n");
printf("Enter choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter value: ");
scanf("%d", &value);
insertBeginning(value);
break;
case 2:
printf("Enter value: ");
scanf("%d", &value);
insertEnd(value);
break;
case 3:
deleteBeginning();
break;
case 4:
deleteEnd();
break;
case 5:
traverse();
break;
case 6:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
}

Output:
1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Traverse
6. Exit
Enter choice: 1
Enter value: 51

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Traverse
6. Exit
Enter choice: 2
Enter value: 52

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Traverse
6. Exit
Enter choice: 2
Enter value: 53

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Traverse
6. Exit
Enter choice: 2
Enter value: 54

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Traverse
6. Exit
Enter choice: 1
Enter value: 55

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Traverse
6. Exit
Enter choice: 4
Deleted 54

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Traverse
6. Exit
Enter choice: 3
Deleted 55

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Traverse
6. Exit
Enter choice: 5
Circular list: 51 -> 52 -> 53 -> (back to head)

1. Insert at beginning
2. Insert at end
3. Delete from beginning
4. Delete from end
5. Traverse
6. Exit
Enter choice: 6

You might also like