Code a doubly linked, sorted list (in ascending order). Each item of the list wi
ID: 3559711 • Letter: C
Question
Code a doubly linked, sorted list (in ascending order). Each item of the list will just store an int. You need to code three classes: Nade, SortedList, and GroupProject. The Node class has three instance variables, all private: an int representing the value stored inside the Node, a Node (next), another Node (previous).
The methods to code are: constructor (at least one), accessors, mutators.
The SortedList class is a doubly linked list, sorted in a ascending order. It has two instance bariables, both private:
an int representing the number of items in the list
a Node, representing the head node in the list
The mthods to code are
insert, delete, toString, constructor.
All methods should keep the list sorted in ascending order .
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
struct dllNode {
int data;
struct dllNode *previous, *next;
};
struct dllNode *head = NULL;
static int totNodes = 0;
struct dllNode *createNode(int);
void insertNode(int);
void deleteNode(int);
void insertionSort();
void traverseList();
/* creating a new node */
struct dllNode* createNode(int data) {
struct dllNode *nPtr = (struct dllNode *)malloc(sizeof (struct dllNode));
nPtr->data = data;
nPtr->previous = NULL;
nPtr->next = NULL;
return (nPtr);
}
/* Insert a newnode at the end of the list */
void insertNode(int data) {
struct dllNode *tmp, *nPtr = createNode(data);
if (!head) {
head = nPtr;
totNodes++;
return;
} else {
tmp = head;
while (tmp) {
if (tmp->next == NULL) {
tmp->next = nPtr;
nPtr->previous = tmp;
totNodes++;
return;
}
tmp=tmp->next;
}
}
}
/* delete the node with given data */
void deleteNode(int data) {
struct dllNode *nPtr, *tmp = head;
if (head == NULL) {
printf("Data unavailable ");
return;
} else if (tmp->data == data) {
nPtr = tmp->next;
tmp->next = NULL;
free(tmp);
head = nPtr;
totNodes--;
} else {
while (tmp->next != NULL && tmp->data != data) {
nPtr = tmp;
tmp = tmp->next;
}
if (tmp->next == NULL && tmp->data != data) {
printf("Given data unvavailable in list ");
return;
} else if (tmp->next != NULL && tmp->data == data) {
nPtr->next = tmp->next;
tmp->next->previous = tmp->previous;
tmp->next = NULL;
tmp->previous = NULL;
free(tmp);
printf("Data deleted successfully ");
totNodes--;
} else if (tmp->next == NULL && tmp->data == data) {
nPtr->next = NULL;
tmp->next = tmp->previous = NULL;
free(tmp);
printf("Data deleted successfully ");
totNodes--;
}
}
}
/* sort the given list - insertNode sort*/
void insertionSort() {
struct dllNode *nPtr1, *nPtr2;
int i, j, tmp;
nPtr1 = nPtr2 = head;
for (i = 0; i < totNodes; i++) {
tmp = nPtr1->data;
for (j = 0; j < i; j++)
nPtr2 = nPtr2->next;
for (j = i; j > 0 && nPtr2->previous->data < tmp; j--) {
nPtr2->data = nPtr2->previous->data;
nPtr2 = nPtr2->previous;
}
nPtr2->data = tmp;
nPtr2 = head;
nPtr1 = nPtr1->next;
}
}
/* traverse the doubly linked list and print data in each node */
void traverseList() {
struct dllNode *nPtr = head;
int i = 0;
while (nPtr) {
printf("%d ", nPtr->data);
nPtr = nPtr->next;
i++;
}
}
int main() {
int ch, data;
while (1) {
printf("1.Insertion 2.Delete Operation ");
printf("3.Sort List 4.Display ");
printf("5.Exit Enter ur choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter data to insert:");
scanf("%d", &data);
insertNode(data);
break;
case 2:
printf("Enter data to delete:");
scanf("%d", &data);
deleteNode(data);
break;
case 3:
insertionSort();
break;
case 4:
traverseList();
printf(" ");
break;
case 5:
exit(0);
default:
printf("Wrong Option!! ");
break;
}
}
}