Question

In: Computer Science

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;

//return length of list
int sizeList (struct node *pointer)
{
int length = 0;
struct node *temp;

if(pointer == head)
{
for (temp = head; temp != NULL; temp = temp-> next)
length++;
}
else
{
for (temp = tail; temp != NULL; temp = temp-> prev)
length++;
}
return length;
}

//insert element from last node
struct Node* insertLast (struct node *tail, int newelement)
{
struct node *temp = (struct node*) malloc(sizeof(struct node));
temp-> data = newelement;

if (tail == NULL){
head = temp;
tail = temp;
}
else
{
tail-> next = temp;
temp-> prev = tail;
}
//point last to new last node
tail = temp;

return tail;
};

void printList(struct node *pointer)
{
int length = 0;
struct node *temp;

//check if pointer is head and print head of node
if (pointer == head)
{
for (temp = head; temp != NULL; temp = temp-> next)
printf("%d ", temp-> data);
}
//check if pointer is tail and print the list from tail node using previous pointer
else
{
for (temp = tail; temp != NULL; temp = temp-> prev)
printf("%d ", temp-> data);
}

printf("\n");
}

int get (struct node *pointer, int position)
{
struct node *temp;
int length = sizeList(pointer);
int tempPosition = 0;

if (length < position)
{
printf("Enter the position with in %d.", length);
return -1;
}
//check if pointer is head and return the element from the position
if (pointer == head)
{
for (temp = head; temp != NULL; temp = temp-> next)
{
if(++tempPosition == position)
{
return temp-> data;
}
}
}
//check if pointer is tail and return the element from the position
else
{
for (temp = tail; temp != NULL; temp = tail-> prev)
{
if (++tempPosition == position)
{
return temp-> data;
}
}
}
return 0;
}

//delete node from position
struct node* removeEle(struct node *head, int position)
{
struct node *temp = head, *deleteNode = NULL;
int i;

//traverse list until we get each position
for (i=1; i<position && temp != NULL; i++)
{
temp = temp-> next;
}

//if position is 1, move the head pointer to next and free node and return to head
if (position ==1)
{
deleteNode = temp;
temp = temp-> next;
temp-> prev = NULL;
head = temp;

free (deleteNode);
return head;
}

//if deleteNode is last position move the tail to previous node and free last node
else if (temp == tail)
{
deleteNode = tail;
tail = tail-> prev;
tail-> next = NULL;

free(deleteNode);
return head;
}
//swap temp pointers to skip node
else if (temp != NULL)
{
temp-> prev-> next = temp-> next;
temp-> next-> prev = temp-> prev;

free(temp); //delete n node
return head;
}
else
{
printf("It's an invalid position..\n");
return head;
}
};

void reverseList(struct node *node)
{
//stop and return if node is null
if (!node)
return;

//swap next and prev pointer of node
struct node* temp = node-> next;
node-> next = node-> prev;
node-> prev = temp;

//node of prev is null stop and update head and tail pointer
if(!node-> prev)
{
head = node;
if(head-> next == NULL)
{
tail = head;
}
struct node *temp = head;
while(temp-> next != NULL)
{
temp = temp -> next;
}
tail = temp;
return;
}
//invoke recursive api
reverseList(node-> prev);
}

int main()
{
struct Node *tail = NULL;

//insert element at last
tail = insertLast(tail, 10);
tail = insertLast(tail, 20);
tail = insertLast(tail, 30);
tail = insertLast(tail, 40);
tail = insertLast(tail, 50);

printf("Printing from Head: ");
printList(head);
printf("\n");

printf("Printing from Tail: ");
printList(tail);
printf("\n");

printf("Size of list from Head: %d\n", sizeList(head));
printf("Size of list from Tail: %d\n", sizeList(tail));

//remove element from position 4
printf("Get the element from head at position 4: ");
int element = get(head, 4);

if(element != -1)
{
printf("%d\n", element);
}

//remove element from position 2
printf("Get the element from tail at position 2: ");
element = get(tail, 2);

if(element != -1)
{
printf("%d\n", element);
}

printf("Remove element from position 3\n");
head = removeEle(head, 3);

printf("Printing from Head after removal: ");
printList(head);
printf("\n");

//invoke reverse list
reverseList(head);

printf("Printing from Head after reverseList: ");
printList(head);
printf("\n");

printf("Printing from tail after reverseList: ");
printList(tail);
printf("\n");

return 0;
}

Solutions

Expert Solution

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;

//return length of list
int sizeList (struct node *pointer)
{
        int length = 0;
        struct node *temp;
        
        if(pointer == head)
        {
                for (temp = head; temp != NULL; temp = temp-> next)
                length++;
        }
        else
        {
                for (temp = tail; temp != NULL; temp = temp-> prev)
                length++;
        }
        return length;
}

//insert element from last node
struct node* insertLast (struct node *tail, int newelement)
{
        struct node *temp = (struct node*) malloc(sizeof(struct node));
        temp-> data = newelement;
        //close link of new node
        temp->next = NULL;
        temp->prev = NULL;
        
        if (tail == NULL){
                head = temp;
                tail = temp;
        }
        else
        {
                tail-> next = temp;
                temp-> prev = tail;
        }
        //point last to new last node
        tail = temp;
        
        return tail;
}

void printList(struct node *pointer)
{
        int length = 0;
        struct node *temp;
        
        //check if pointer is head and print head of node
        if (pointer == head)
        {
                for (temp = head; temp != NULL; temp = temp-> next)
                printf("%d ", temp-> data);
        }
        //check if pointer is tail and print the list from tail node using previous pointer
        else
        {
                for (temp = tail; temp != NULL; temp = temp-> prev)
                printf("%d ", temp-> data);
        }
        
        printf("\n");
}

int get (struct node *pointer, int position)
{
        struct node *temp;
        int length = sizeList(pointer);
        int tempPosition = 0;
        
        if (length < position)
        {
                printf("Enter the position with in %d.", length);
                return -1;
        }
        //check if pointer is head and return the element from the position
        if (pointer == head)
        {
                for (temp = head; temp != NULL; temp = temp-> next)
                {
                        if(++tempPosition == position)
                        {
                                return temp-> data;
                        }
                }
        }
        //check if pointer is tail and return the element from the position
        else
        {
        for (temp = tail; temp != NULL; temp = tail-> prev)
        {
        if (++tempPosition == position)
        {
        return temp-> data;
        }
        }
        }
        return 0;
}

//delete node from position
struct node* removeEle(struct node *head, int position)
{
        struct node *temp = head, *deleteNode = NULL;
        int i;
        
        //traverse list until we get each position
        for (i=1; i<position && temp != NULL; i++)
        {
                temp = temp-> next;
        }
        
        //if position is 1, move the head pointer to next and free node and return to head
        if (position ==1)
        {
                deleteNode = temp;
                temp = temp-> next;
                temp-> prev = NULL;
                head = temp;
                
                free (deleteNode);
                return head;
        }
        
        //if deleteNode is last position move the tail to previous node and free last node
        else if (temp == tail)
        {
                deleteNode = tail;
                tail = tail-> prev;
                tail-> next = NULL;
                
                free(deleteNode);
                return head;
        }
        //swap temp pointers to skip node
        else if (temp != NULL)
        {
                temp-> prev-> next = temp-> next;
                temp-> next-> prev = temp-> prev;
                
                free(temp); //delete n node
                return head;
        }
        else
        {
                printf("It's an invalid position..\n");
                return head;
        }
};

void reverseList(struct node *node)
{
        //stop and return if node is null
        if (!node)
        return;
        
        //swap next and prev pointer of node
        struct node* temp = node-> next;
        node-> next = node-> prev;
        node-> prev = temp;
        
        //node of prev is null stop and update head and tail pointer
        if(!node-> prev)
        {
                head = node;
                if(head-> next == NULL)
                {
                        tail = head;
                }
                struct node *temp = head;
                while(temp-> next != NULL)
                {
                        temp = temp -> next;
                }
                tail = temp;
                return;
        }
        //invoke recursive api
        reverseList(node-> prev);
}

int main()
{
        //tail is already dedclared global varialbe
//      struct node *tail = NULL;
        
        //insert element at last
        tail = insertLast(tail, 10);
        tail = insertLast(tail, 20);
        tail = insertLast(tail, 30);
        tail = insertLast(tail, 40);
        tail = insertLast(tail, 50);
        
        printf("Printing from Head: ");
        printList(head);
        printf("\n");
        
        printf("Printing from Tail: ");
        printList(tail);
        printf("\n");
        
        printf("Size of list from Head: %d\n", sizeList(head));
        printf("Size of list from Tail: %d\n", sizeList(tail));
        
        //remove element from position 4
        printf("Get the element from head at position 4: ");
        int element = get(head, 4);
        
        if(element != -1)
        {
        printf("%d\n", element);
        }
        
        //remove element from position 2
        printf("Get the element from tail at position 2: ");
        element = get(tail, 2);
        
        if(element != -1)
        {
                printf("%d\n", element);
        }
        
        printf("Remove element from position 3\n");
        head = removeEle(head, 3);
        
        printf("Printing from Head after removal: ");
        printList(head);
        printf("\n");
        
        //invoke reverse list
        reverseList(head);
        
        printf("Printing from Head after reverseList: ");
        printList(head);
        printf("\n");
        
        printf("Printing from tail after reverseList: ");
        printList(tail);
        printf("\n");
        
        return 0;
}

output:

venereology answered 6 months ago

Next > < Previous

Related Solutions

HI i will write user's manual for a doubly/singly linked list , How can i write...

HI i will write user's manual for a doubly/singly linked list , How can i write User's manual ?

Using the singly linked list code as a base, create a class that implements a doubly...

Using the singly linked list code as a base, create a class that implements a doubly linked list. A doubly linked list has a Previous link so you can move backwards in the list. Be sure the class is a template class so the user can create a list with any data type. Be sure to test all the member functions in your test program. c++

1. Answer “True” or “False”. (a) A doubly linked list structure is worse than a singly...

1. Answer “True” or “False”. (a) A doubly linked list structure is worse than a singly linked list if we plan to do a lot of insertions. (b) A doubly linked list structure is worse than a singly linked list if we plan to do a lot of deletions. (c) A doubly linked list structure is worse than a singly linked list if we plan to print the entire list frequently. (d) An array implementation of a queue is more...

Can you make this singular linked list to doubly linked list Create a Doubly Linked List....

Can you make this singular linked list to doubly linked list Create a Doubly Linked List. Use this to create a Sorted Linked List, Use this to create a prioritized list by use. Bring to front those links recently queried. -----link.h------ #ifndef LINK_H #define LINK_H struct Link{ int data; Link *lnkNxt; }; #endif /* LINK_H */ ----main.cpp---- //System Level Libraries #include <iostream> //I/O Library using namespace std; //Libraries compiled under std #include"Link.h" //Global Constants - Science/Math Related //Conversions, Higher Dimensions...

A circular doubly-linked list .(a) In a circular doubly-linked list, there is no front or end;...

A circular doubly-linked list .(a) In a circular doubly-linked list, there is no front or end; the nodes form a full circle. Instead of keeping track of the node at the front, we keep track of a current node instead. Write a class for a circular doubly-linked list using the attached Job class as your node objects. It should have: • A private instance variable for the current node • A getCurrent() method that returns a reference to the current...

I know this code takes in a set of numbers into a doubly linked list and...

I know this code takes in a set of numbers into a doubly linked list and sorts it using insertion sort. Could you explain exactly how this code is working? main.c Source Code: #include #include #include "node.h" int main() { struct mynode *head=NULL; int value; printf("Give first value: \n"); scanf("%d",&value); printf("Give next values, and input 0 to end list: \n"); do{ if(value>0){ head = pushNode(head, value); scanf("%d",&value); } }while (value>0); printf("Before insertion sort: "); printlist(head); head=insertsort(head); printf("After insertion...

This is the code what I have for doubly linked list for STACK. This is Python...

This is the code what I have for doubly linked list for STACK. This is Python language and I want anyone to help me with the following questions. Can you check for me if it is good Doubly Linked List? ####THIS IS THE ENTIRE ASSIGNMENT#### ADD the Following feature: Include a class attribute in the container class called name. In the implementation - Pod: You should ask the user to enter the name of the container and the program should...

TITLE Updating Accounts Using Doubly Linked List TOPICS Doubly Linked List DESCRIPTION General Write a program...

TITLE Updating Accounts Using Doubly Linked List TOPICS Doubly Linked List DESCRIPTION General Write a program that will update bank accounts stored in a master file using updates from a transaction file. The program will maintain accounts using a doubly linked list. The input data will consist of two text files: a master file and a transaction file. See data in Test section below. The master file will contain only the current account data. For each account, it will contain account...

I need an example of how to swap and index within a doubly linked list with...

I need an example of how to swap and index within a doubly linked list with index + 1. This is written in java. public class A3DoubleLL<E> { /* * Grading: * Swapped nodes without modifying values - 2pt * Works for all special cases - 1pt */ public void swap(int index) { //swap the nodes at index and index+1 //change the next/prev connections, do not modify the values ...

Given a doubly linked list in c++, how do I create a function that returns the...

Given a doubly linked list in c++, how do I create a function that returns the pointer to first node in the given pattern, For example, given mainList (a -> b -> c -> d) and sublist (b -> c), our function should return a Node pointer that points to first node of the sublist in the mainList. If the pattern doesn't exist in the mainList, we should return a nullptr, there are multiple of the same sublist in the mainList,...

Subjects