Java Code a doubly linked, sorted list (in ascending order). Each item of the li

Question

Java

Code a doubly linked, sorted list (in ascending order). Each item of the list will just store an int.

You will need to code three classes: Node, 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 ascending order.

It has two instance variables, both private:

an int, representing the number of items in the list.

a Node, representing the head node in the list.

The methods are:

insert: this method takes one parameter, an int; it has a void return value.

delete: this method takes one parameter, an int; it returns a boolean value. If we were successful in deleting the item (i.e., the value of the parameter was found in the list), then we return true; if we were not successful, then we want to output a message that the value was not found, and therefore, not deleted, and returned false.

toString: this method takes no parameters and returns a Stringrepresentation of the list.

Constructor (at least one), and accessors and mutators as appropriate.

All methods should keep the list sorted in ascending order.

The GroupProject class contains the main method; it should do the following:

create a SortedList object reference

insert successively the values 25, 17, 12, 21, 78, and 47 in the sorted list

output the contents of the sorted list using the toString method

delete from the sorted list the value 30, using the delete method (obviously, 30 will not be found)

output the contents of the sorted list using the toString method

delete from the sorted list the value 21, using the delete method

output the contents of the sorted list using the toString method

Your insert and delete methods should work properly in all possible scenarios: inserting in an empty list, inserting at the beginning of a list, inserting in the middle of a list, inserting at the end of a list, deleting from an empty list (cannot delete), deleting an item not in the list (cannot delete), deleting the first item in a list, deleting in the middle of a list, deleting the last item in a list.

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;
                }
        }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.