Question

In: Computer Science

This much like the single linked list assignment. I am giving you the majority of the...

This much like the single linked list assignment. I am giving you the majority of the code and left a couple of functions for you to complete. I had intended to try to do some video clips of my own lecture but I am not going to have time to get those completed (at least not at a quality I want).   You might take a look at these sites for more help outside just zyBooks.
#include <stdio.h>
#include <stdlib.h>

struct node
{
        struct node *prev;
        int info;
        struct node *next;
};

struct node *createList(struct node *start);
void displayList(struct node *start);
struct node *insertInEmptyList(struct node *start, int data);
struct node *insertInBeginning(struct node *start, int data);
void insertAtEnd(struct node *start, int data);
void insertAfter(struct node *start, int data, int x);
struct node *insertBefore(struct node *start, int data, int x);
struct node *deleteNode(struct node *start, int data);
struct node *reverseList(struct node *start);

main()
{
        int choice, data, x;
        struct node *start=NULL;

        start=createList(start);

        while(1)
        {
                printf("\n");
                printf("1.Display List\n");
                printf("2.Insert in empty list\n");
                printf("3.Insert a node in beginning of the list\n");
                printf("4.Insert a node at the end of the list\n");
                printf("5.Insert a node after a specified node\n");
                printf("6.Insert a node before a specified node\n");
                printf("7.Delete a node\n");
                printf("8.Reverse the list\n");
                printf("9.Quit\n");
                printf("Enter your choice : ");
                scanf("%d", &choice);

        if (choice == 9)
                break;

        switch(choice)
        {
                case 1:
                        displayList(start);
                        break;
                case 2:
                        printf("Enter the element to be inserted : ");
                        scanf("%d", &data);
                        start=insertInEmptyList(start,data);
                        break;
                case 3:
                        printf("Enter the element to be inserted : ");
                        scanf("%d", &data);
                        start=insertInBeginning(start, data);
                        break;
                case 4:
                        printf("Enter the element to be inserted : ");
                        scanf("%d", &data);
                        insertAtEnd(start, data);
                        break;
                case 5:
                        printf("Enter the element to be insert : ");
                        scanf("%d", &data);
                        printf("Enter the element after which to insert : ");
                        scanf("%d", &x);
                        insertAfter(start, data, x);
                        break;
                case 6:
                        printf("Enter the element to be inserted : ");
                        scanf("%d", &data);
                        printf("Enter the element before which to insrt : ");
                        scanf("%d", &x);
                        start=insertBefore(start, data, x);
                        break;
                case 7:
                        printf("Enter the element to be deleted : ");
                        scanf("%d", &data);
                        start=deleteNode(start, data);
                        break;
                case 8:
                        start=reverseList(start);
                        break;
                default:
                        printf("Wrong choice\n");

                }       //end of switch
        } //end of while
} //end of main


struct node *createList(struct node *start)
{
        int i, n, data;
        printf("Enter the number of nodes : ");
        scanf("%d", &n);
        start=NULL;

        if (n==0)
                return start;

        printf("Enter the first element to be inserted : ");
        scanf("%d", &data);
        start=insertInEmptyList(start, data);

        for (i=2; i<=n; i++)
        {
                printf("Enter the next element to be inserted : ");
                scanf("%d", &data);
                insertAtEnd(start, data);
        }
        return start;
}//End of createList()


void displayList(struct node *start)
{
        struct node *p;
        if (start==NULL)
        {
                printf("List is empty\n");
                return;
        }

        p=start;
        printf("List is :\n");
        while(p!=NULL)
        {
                printf("%d ", p->info);
                p=p->next;
        }
        printf("\n");
} //End of displayList()

struct node *insertInEmptyList(struct node *start, int data)
{
        **********************************
        *** COMPLETE THE REQUIRED CODE ***
        **********************************
}//End of insertInEmptyList()

struct node *insertInBeginning(struct node *start, int data)
{
        struct node *temp;
        temp = (struct node *)malloc(sizeof(struct node));
        temp->info=data;

        temp->prev=NULL;
        temp->next=start;
        start->prev=temp;
        start=temp;
}//End of insertInBeginng()

void insertAtEnd(struct node *start, int data)
{
        **********************************
        *** COMPLETE THE REQUIRED CODE ***
        **********************************
}//End of insertAtEnd()


void insertAfter(struct node *start, int data, int x)
{
        struct node *temp, *p;
        temp=(struct node*)malloc(sizeof(struct node));
        temp->info=data;

        p=start;
        while(p!=NULL)
        {
                if(p->info==x)
                        break;
                p=p->next;
        }

        if(p==NULL)
                printf("%d not present in the list\n", x);
        else
        {
                temp->prev=p;
                temp->next=p->next;
                if(p->next!=NULL)
                        p->next->prev=temp; //should not be done when p points to last node
                p->next=temp;
        }
}//End of insertAfter()

struct node *insertBefore(struct node *start, int data, int x)
{
        struct node *temp, *p;
        if(start==NULL)
        {
                printf("List is empty\n");
                return start;
        }

        if(start->info==x)
        {
                temp = (struct node *)malloc(sizeof(struct node));
                temp->info=data;

                temp->prev=NULL;
                temp->next=start;
                start->prev=temp;
                start=temp;
                return start;
        }

        p=start;
        while(p!=NULL)
        {
                if(p->info==x)
                        break;
                p=p->next;
        }

        if(p==NULL)
                printf("%d not present in the list\n", x);
        else
        {
                        temp=(struct node *)malloc(sizeof(struct node));
                        temp->info=data;

                        temp->prev=p->prev;
                        temp->next = p;
                        p->prev->next=temp;
                        p->prev=temp;
        }
        return start;
}//End of insertBefore()

struct node *deleteNode(struct node *start, int x)
{
        struct node *temp;

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

        if(start->next==NULL) //only one node in the list
        {
                if(start->info==x)
                {
                        temp=start;
                        start=NULL;
                        free(temp);
                }
                else
                        printf("Element %d not found\n", x);
                return start;
        }

        //Deletion of first node
        if(start->info==x)
        {
                temp=start;
                start=start->next;
                start->prev=NULL;
                free(temp);
                return start;
        }

        temp=start->next;
        while(temp->next!=NULL)
        {
                if(temp->info==x)
                        break;
                temp=temp->next;
        }

        if(temp->next!=NULL) //node to be deleted is in between
        {
                temp->prev->next=temp->next;
                temp->next->prev=temp->next;
                free(temp);
        }
        else //temp points to last node
        {
                if(temp->info==x) //node to be deleted is last node
                {
                        temp->prev->next=NULL;
                        free(temp);
                }
                else
                                printf("Element %d not fount\n", x);
        }

return start;
}

struct node *reverseList(struct node*start)
{
        struct node *p1, *p2;

        if(start==NULL)
                return;

        p1=start;
        p2=p1->next;
        p1->next=NULL;
        p1->prev=p2;
        while(p2!=NULL)
        {
                p2->prev=p2->next;
                p2->next=p1;
                p1=p2;
                p2=p2->prev;
        }
        start=p1;
        return start;
} //End of reverseList()

Solutions

Expert Solution

The completed code is given below

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

struct node
{
struct node *prev;
int info;
struct node *next;
};

struct node *createList(struct node *start);
void displayList(struct node *start);
struct node *insertInEmptyList(struct node *start, int data);
struct node *insertInBeginning(struct node *start, int data);
void insertAtEnd(struct node *start, int data);
void insertAfter(struct node *start, int data, int x);
struct node *insertBefore(struct node *start, int data, int x);
struct node *deleteNode(struct node *start, int data);
struct node *reverseList(struct node *start);

int main()
{
int choice, data, x;
struct node *start=NULL;

start=createList(start);

while(1)
{
printf("\n");
printf("1.Display List\n");
printf("2.Insert in empty list\n");
printf("3.Insert a node in beginning of the list\n");
printf("4.Insert a node at the end of the list\n");
printf("5.Insert a node after a specified node\n");
printf("6.Insert a node before a specified node\n");
printf("7.Delete a node\n");
printf("8.Reverse the list\n");
printf("9.Quit\n");
printf("Enter your choice : ");
scanf("%d", &choice);

if (choice == 9)
break;

switch(choice)
{
case 1:
displayList(start);
break;
case 2:
printf("Enter the element to be inserted : ");
scanf("%d", &data);
start=insertInEmptyList(start,data);
break;
case 3:
printf("Enter the element to be inserted : ");
scanf("%d", &data);
start=insertInBeginning(start, data);
break;
case 4:
printf("Enter the element to be inserted : ");
scanf("%d", &data);
insertAtEnd(start, data);
break;
case 5:
printf("Enter the element to be insert : ");
scanf("%d", &data);
printf("Enter the element after which to insert : ");
scanf("%d", &x);
insertAfter(start, data, x);
break;
case 6:
printf("Enter the element to be inserted : ");
scanf("%d", &data);
printf("Enter the element before which to insrt : ");
scanf("%d", &x);
start=insertBefore(start, data, x);
break;
case 7:
printf("Enter the element to be deleted : ");
scanf("%d", &data);
start=deleteNode(start, data);
break;
case 8:
start=reverseList(start);
break;
default:
printf("Wrong choice\n");

} //end of switch
} //end of while
} //end of main

struct node *createList(struct node *start)
{
int i, n, data;
printf("Enter the number of nodes : ");
scanf("%d", &n);
start=NULL;

if (n==0)
return start;

printf("Enter the first element to be inserted : ");
scanf("%d", &data);
start=insertInEmptyList(start, data);

for (i=2; i<=n; i++)
{
printf("Enter the next element to be inserted : ");
scanf("%d", &data);
insertAtEnd(start, data);
}
return start;
}//End of createList()

void displayList(struct node *start)
{
struct node *p;
if (start==NULL)
{
printf("List is empty\n");
return;
}

p=start;
printf("List is :\n");
while(p!=NULL)
{
printf("%d ", p->info);
p=p->next;
}
printf("\n");
} //End of displayList()

struct node *insertInEmptyList(struct node *start, int data)
{
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
temp->info=data;
return temp;
}//End of insertInEmptyList()

struct node *insertInBeginning(struct node *start, int data)
{
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
temp->info=data;

temp->prev=NULL;
temp->next=start;
start->prev=temp;
start=temp;
}//End of insertInBeginng()

void insertAtEnd(struct node *start, int data)
{
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
temp->info=data;
struct node* temp1=start;
while(temp1!=NULL && temp1->next!=NULL){
temp1=temp1->next;
}
if(temp1){
temp1->next=temp;
}
else if(start==NULL){
start=temp;
}
}//End of insertAtEnd()

void insertAfter(struct node *start, int data, int x)
{
struct node *temp, *p;
temp=(struct node*)malloc(sizeof(struct node));
temp->info=data;

p=start;
while(p!=NULL)
{
if(p->info==x)
break;
p=p->next;
}

if(p==NULL)
printf("%d not present in the list\n", x);
else
{
temp->prev=p;
temp->next=p->next;
if(p->next!=NULL)
p->next->prev=temp; //should not be done when p points to last node
p->next=temp;
}
}//End of insertAfter()

struct node *insertBefore(struct node *start, int data, int x)
{
struct node *temp, *p;
if(start==NULL)
{
printf("List is empty\n");
return start;
}

if(start->info==x)
{
temp = (struct node *)malloc(sizeof(struct node));
temp->info=data;

temp->prev=NULL;
temp->next=start;
start->prev=temp;
start=temp;
return start;
}

p=start;
while(p!=NULL)
{
if(p->info==x)
break;
p=p->next;
}

if(p==NULL)
printf("%d not present in the list\n", x);
else
{
temp=(struct node *)malloc(sizeof(struct node));
temp->info=data;

temp->prev=p->prev;
temp->next = p;
p->prev->next=temp;
p->prev=temp;
}
return start;
}//End of insertBefore()

struct node *deleteNode(struct node *start, int x)
{
struct node *temp;

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

if(start->next==NULL) //only one node in the list
{
if(start->info==x)
{
temp=start;
start=NULL;
free(temp);
}
else
printf("Element %d not found\n", x);
return start;
}

//Deletion of first node
if(start->info==x)
{
temp=start;
start=start->next;
start->prev=NULL;
free(temp);
return start;
}

temp=start->next;
while(temp->next!=NULL)
{
if(temp->info==x)
break;
temp=temp->next;
}

if(temp->next!=NULL) //node to be deleted is in between
{
temp->prev->next=temp->next;
temp->next->prev=temp->next;
free(temp);
}
else //temp points to last node
{
if(temp->info==x) //node to be deleted is last node
{
temp->prev->next=NULL;
free(temp);
}
else
printf("Element %d not fount\n", x);
}

return start;
}

struct node *reverseList(struct node*start)
{
struct node *p1, *p2;

if(start==NULL)
return;

p1=start;
p2=p1->next;
p1->next=NULL;
p1->prev=p2;
while(p2!=NULL)
{
p2->prev=p2->next;
p2->next=p1;
p1=p2;
p2=p2->prev;
}
start=p1;
return start;
} //End of reverseList()

The output is

venereology answered 1 week ago

Next > < Previous

Related Solutions

I am trying to add two linked-list based integers, but the program keeps giving me the...

I am trying to add two linked-list based integers, but the program keeps giving me the incorrect result. I am trying to add (List 1: 43135) + (List 2: 172). I have pasted the code below #include <iostream> using namespace std; //Linked list node class Node { public: int num; Node* next; }; //Function to create a new node with given numbers Node *new_Node(int num) { Node *newNode = new Node(); newNode->num = num; ...

Hi, I would like to test a java program. I am learning linked list and going...

Hi, I would like to test a java program. I am learning linked list and going to make a linked lists for integer nodes. For instance, I am going to add the numbers 12, 13, and 16 to the list and then display the list contents and add 15 to the list again and display the list contents and delete 13 from the list and display the list contents and lastly delete 12 from the list and display the list...

(using single linkedlist c++)In this assignment, you will implement a Polynomial linked list(using single linkedlist only),...

(using single linkedlist c++)In this assignment, you will implement a Polynomial linked list(using single linkedlist only), the coefficients and exponents of the polynomial are defined as a node. The following 2 classes should be defined. p1=23x 9 + 18x 7+3 1. Class Node ● Private member variables: coefficient (double), exponents (integer), and next pointer. ● Setter and getter functions to set and get all member variables ● constructor 2. Class PolynomialLinkedList ● Private member variable to represent linked list (head)...

Hi, I am working on an assignment in C-Programming language dealing with LInked lists, in the...

Hi, I am working on an assignment in C-Programming language dealing with LInked lists, in the code there is instructions on where to write the code. I do not know how to write Linked Lists. Has to be in the C-language, Any help is greatly appreciated //agelink.c //maintains list of agents //uses linked list #include <stdio.h> #include <stdlib.h> #define TRUE 1 void listall(void); void newname(void); void delink(void); void memexit(void); void wfile(void); /********************************************************************* this is the structure to hold a agent...

In this homework, you will implement a single linked list to store a list of employees...

In this homework, you will implement a single linked list to store a list of employees in a company. Every employee has an ID, name, department, and salary. You will create 2 classes: Employee and EmployeeList. Employee class should have all information about an employee and also a “next” pointer. See below: Employee Type Attribute int ID string name string department int salary Employee* next Return Type Function (constructor) Employee(int ID, string name, string department, int salary) EmployeeList class should...

Hi I would like to see an example in c++ of Stack As Linked List I...

Hi I would like to see an example in c++ of Stack As Linked List I need a seek() function which receives a double number X and which returns in which position in the stack is X. If the value X is not in the stack, the function should return -1

how do you add two matrices linked list in java? (am using linked list because 2D...

how do you add two matrices linked list in java? (am using linked list because 2D arrays are not allowed.) ex [1st matrix] 1 3 2 4 2 1 3 2 4 + [2nd matrix] 3 2 3 2 1 4 5 2 3 = [3rd matrix] 4 5 5 6 3 5 8 4 7

In this assignment, you will implement a Polynomial linked list, the coefficients and exponents of the...

In this assignment, you will implement a Polynomial linked list, the coefficients and exponents of the polynomial are defined as a node. The following 2 classes should be defined.

Objective: Learning linked list. Problem Specification: An employer would like to maintain a linked list...

Objective: Learning linked list. Problem Specification: An employer would like to maintain a linked list for employees, the data stored is ·An employee number (a positive integer) ·A yearly salary (a float). ·Number of dependents (a short positive integer) The employer would like you as the programmer to design and implement a linked list using classes. For each class two files are needed, one to define the class, the other to implement the methods. In addition, the client uses...

I was supposed to conver a singly linked list to a doubly linked list and everytime...

I was supposed to conver a singly linked list to a doubly linked list and everytime I run my program the output prints a bunch of random numbers constantly until I close the console. Here is the code. #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> struct node { int data; struct node *next; struct node *prev; }; //this always points to first link struct node *head = NULL; //this always points to last link struct node *tail = NULL;...

Subjects