#ifndef NODE_H #define NODE_H /* An Implementation of the Node ADT * -written by

Question

#ifndef NODE_H
#define NODE_H

/* An Implementation of the Node ADT
*   -written by Brian P. Eddy
*/

//create a handle for nodes
typedef struct node* Node;

/* Create a new Node
* @param value the value stored in the Node
* @param next the node to point to from the current Node
* @return a newly created Node
*/
Node createNode(int value, Node next);

/* Return the value of the passed in Node
* @param Node the node to get the value from
* @return the value for the passed in Node
*/
int getValue(Node);

/* Return the next Node pointed to by the passed in Node
* @param Node the node to get the next Node from
* @return the next Node from the passed in Node
*/
Node getNext(Node);

/* Set the value of the passed in Node
* @param Node the node to set the value for
* @param value the new value to store in the Node
*/
void setValue(Node, int value);

/* Set the next Node of the passed in Node
* @param Node the Node to set the next node for
* @param next the Node to be pointed to by the given Node
*/
void setNext(Node, Node next);

/* Frees the memory allocated for the passed in Node
* @param Node the Node to free
*/
void freeNode(Node);

#endif

#include <stdlib.h>
#include "node.h"

struct node {
int value;
Node next;
};

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

int getValue(Node current){
return current->value;
}

Node getNext(Node current){
return current->next;
}

void setValue(Node current, int value){
current->value = value;
}

void setNext(Node current, Node next){
current->next = next;
}

void freeNode(Node current){
free(current);
}

#ifndef LIST_H
#define LIST_H

/* Wraps around Node to add important functions for a singly-linked list
*    - written by Brian P. Eddy
*/

//create a handle for lists
typedef struct list* List;

/* Creates a new non-circular singly-linked list
* @return returns a new empty list
*/
List createList();

/* Get the size of the linked list
* @param List the list we need the size of
* @return the size of the linked list
*/
int size(List);

/* Adds an element to the beginning of a linked list
* @param List the list to add elements to
* @param value the item to add to the beginning of the list
*/
void prepend(List,int value);

/* Adds an element to the end of a linked list
* @param List the list to add elements to
* @param value the item to add to the end of the list
*/
void append(List,int value);

/* Inserts an element into a position in the linked list
* @param List the list to insert elements into
* @param index where to insert the element
* @param value the item to insert into the list
*/
void insert(List, int index, int value);

/* Removes an element from a position in the linked list
* @param List the list to remove elements from
* @param index where to remove the element from
* @return the value of the element that was removed
*/
int removeAt(List, int index);

/* Gets an element from a position in the linked list without removing
* @param List the list to get the element from
* @param index where to get the element from
* @return the value of the element that was retrieved
*/
int get(List, int index);

/* Prints the elements in the list
* @param List the list to print out
*/
void printList(List);

/* Frees the memory allocated for the list
* @param List the list to free
*/
void freeList(List);

#endif

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

#include "list.h"
#include "node.h" //list is built upon nodes

struct list {
int size;
Node head;
Node tail;
};

List createList(){
List newList = malloc(sizeof *newList);
//no nodes yet, so set both head and tail to NULL
newList->head = NULL;
newList->tail = NULL;
newList->size = 0;

return newList;
}

int size(List currentList)
{
return currentList->size;
}

void prepend(List currentList, int value){
//create the new node that we are adding
//the new node will point to the old head
Node newNode = createNode(value, currentList->head);
//update the head to be the new node
currentList->head = newNode;

//if this is the first node we have added, then we also need
//to update the tail to be the new node
if(currentList->tail == NULL)
currentList->tail = currentList->head;

++currentList->size; //increment the size of the list
}

void append(List currentList, int value){
//create the new node that we are going to add
Node newNode = createNode(value, NULL);
++currentList->size; //we will be increasing the size of the list

//if no nodes have been added, then both the head and tail
//will need to point to this new node
if(currentList->tail == NULL){
currentList->head = newNode;
currentList->tail = newNode;
return;
}

//otherwise, the old tail will need to point to this new node
setNext(currentList->tail, newNode);
//update the tail so the new node is our new tail
currentList->tail = newNode;
}

void insert(List currentList, int index, int value){

//prepend and append will properly update head and tail,
//use them if possible
if(index == 0) //if inserting at beginning, use prepend
{
prepend(currentList, value);
return;
}

if(index == currentList->size) //if inserting at end, use append
{
append(currentList, value);
return;
}

if(index > currentList->size) //make sure index is in range
{
printf("Index is out of range for insert. ");
exit(1);
}

//we can't directly index into a linked list, so we have to loop
//we will need to go until we are before where we want to insert
//this will enable us to update the next pointer for the node
//that will proceed our inserted node
//start looping at the head
Node currentNode = currentList->head;
//loop until we are before where we want to insert
int i;
for(i = 0; i < index-1; ++i)
currentNode = getNext(currentNode); //move to next node
//create a new node and point it to the current node's next
Node newNode = createNode(value, getNext(currentNode));
//update the current node to point to the new node
setNext(currentNode, newNode);
++currentList->size; //increase size of the list
}

int removeAt(List currentList, int index){
//don't remove anything from an empty list
//or if index is out of bounds
if(currentList->size == 0 || index >= currentList->size)
{
printf("Cannot remove element from the list. ");
exit(1);
}

//start at the beginning of the linked list
Node currentNode = currentList->head;
//we treat index 0 differently because we don't need to update
//a next pointer
--currentList->size; //go ahead and decrease size of list
if(index == 0)
{
currentList->head = getNext(currentNode);
int value = getValue(currentNode); //save our result value
free(currentNode); //FREE MEMORY
if(currentList->size == 0) //if we removed the only element
currentList->tail = NULL; //we need to update the tail
return value;
}
  
//loop until we are before where we want to remove
int i;
for(i = 0; i < index-1; ++i)
currentNode = getNext(currentNode); //move to next node
//we will need to temporarily store the node we are removing
Node removeNode = getNext(currentNode);
//next we point the current node to the next of the node we are removing
setNext(currentNode, getNext(removeNode));
//we will need to update the tail if we removed the last element
if(index == currentList->size)
currentList->tail = currentNode;

//now that nothing is pointing to the node we are removing,
//save the value from the removed node and free the memory for the node
int value = getValue(removeNode);
free(removeNode);//FREE MEMORY
return value;
}

int get(List currentList, int index){
if(currentList->size == 0 || index >= currentList->size)
{
printf("Cannot get a value from given index. ");
exit(1);
}

//start looping at the beginning
Node currentNode = currentList->head;
int i;
//we are actually going to the position passed in this time
for(i = 0; i < index; ++i)
currentNode = getNext(currentNode); //move to next node
return getValue(currentNode); //return the value of the current node
}

void printList(List currentList){
//we will display a linked list as [v1 v2 v3 v4]
//where each v# is an integer in the linked list
printf("[");//print the opening [
Node currentNode = currentList->head;
  
//let's use a while loop this time
//we will know when we have reached the end of the list
//when the currentNode is NULL
while(currentNode != NULL)
{
printf("%d",getValue(currentNode));
if(getNext(currentNode) != NULL)
printf(" ");
currentNode = getNext(currentNode);
}
printf("] "); //wrap things up
}

void freeList(List currentList){
//freeing may seem a little tricky, we will need
//to pass over the list and free each item
//before we can free the list
Node currentNode = currentList->head; //start at head
while(currentNode != NULL)
{
Node next = getNext(currentNode);//temporarily hold next
free(currentNode);//free current
currentNode = next;//set current to the next node
}
free(currentList);//finally, free the linked list
}

#include <stdio.h>

#include "node.h"

int main()
{
Node secondNode = createNode(0,NULL);//create the second node in the list
//create the first node in the list
//will point to the second node
Node firstNode = createNode(1, secondNode);
  
setValue(secondNode,2);//change the value of the secondNode
//print the value of each node individually
printf("First Node's value: %d ",getValue(firstNode));
printf("Second Node's value: %d ",getValue(secondNode));

//print the value of the second node by traversing through the first
//notice that we are nesting function calls
printf("Second Node's value by traversal: %d ",getValue(getNext(firstNode)));
  
//print the value of the second node after freeing memory
freeNode(secondNode);
printf("Second Node's value after free: %d ", getValue(secondNode));
return 0;
}

This project will build upon your knowledge of linked lists. In this project, you will need to create an abstract data type for representing a doubly linked list with the added requirement that the list is circular. This data structure is similar in some ways to the deque that was created in the previous project. However, while the deque was of a set size, the list will be able to grow.
Problem Description:
You have been given an implementation for a singly linked list on eLearning. A singly linked list can be represented in the following way:
Note that this is the same linked list that we have been going over in class. We keep track of a head and a tail node for easy access to the beginning and the end of the linked list. Each node in the linked list contains a single pointer to the next node in the list. This list is noncircular as can be seen with the final node which points to NULL indicating the end of the linked list. In contrast, a circular, doubly-linked list can be represented in the following way:
Note a few of the changes that have been made. Now each node not only contains a link to the next node in the linked list, but it also points to the previous node. We no longer keep track of the tail node. The reason for this is that with the circular list, the last node’s next will be the head of the linked list, while the head’s previous will point to the tail of the list. You can traverse this list in both the forward direction using next and in the backwards direction using previous. Your project will be to implement this type of linked list using the code for the singly linked list as your initial starting point.
Your linked list should have the same functions as the previous implementation with the following changes:
You should update the list implementation to properly manage previous pointers for your nodes. This also includes correctly creating nodes that have previous pointers. A list with only a single node should have that node’s next and previous pointers point to itself. You should remove code relating to the tail of the list as our new list only keeps track of the head. This means making the appropriate changes to each function. You will need to determine what these changes are. Your insert, removeAt, and get functions should now work with negative indices. Negative indices mean to traverse the list in the reverse direction. As an example, get(list, -1) would get the last element in the linked list. The call get(list, -2) would get the element before the last element in the linked list. You may not use mod operations to do this. Your list must be circular. Your insert, removeAt, and get functions should now be able to handle indices that are greater than or equal to the size of the list. As an example, get(list, 4) for a list with only 4 elements would get the first element in the list while get(list, 5) would get the second element in the same list. You may not use mod operations to do this. Your list must be circular. As with the current implementation, inserting a value with insert(list, size, value) in a list with size number of elements should insert a value at the end of the linked list.
You should also add the following function to your linked list implementation: void printListFromEnd(List) – Will print the list in reverse order.
In addition to these changes that will need to be made to the list implementation, you will also need to make changes to the node ADT. You will need to add a pointer for the previous node to the node struct. Your createNode function will need to change accordingly. In addition, you will need to add the following functions: Node getPrevious(Node) – Will return the Node pointed to by the previous pointer for the given Node. void setNode(Node, Node previous) –Will set the previous Node for the Node given as the first argument.   
Creating Your Client
Write a program that displays a menu on the screen for the user to perform operations on your linked list. Each operation, except for createList and freeList, is a separate item in your menu. Your list should be initialized before the menu is shown. An Exit menu item will allow the user to exit from your program. At the time of the exit, the list must be deleted using the corresponding operation before the program terminates. Your menu should allow users to perform the following operations:   
1. Get the current size of the linked list. 2. Prepend an item to the linked list. 3. Append an item to the linked list. 4. Insert an item into the linked list. 5. Remove an item from the linked list. 6. Get an item at a specific position in the linked list. 7. Print the list in the forwards direction. 8. Print the list in the reverse direction. 9. Exit from the program.
For each of the above operations, the program should prompt for any additional arguments. As an example, option 2 will prompt for an integer to insert while option 4 will prompt for an index and then for a value. The menu should be redisplayed after every operation is performed. If any operation fails to be performed, you must print an appropriate message.

Explanation / Answer

Answer:

Note: Code has been modified as per user requirements:

#ifndef NODE_H
#define NODE_H

typedef struct node* Node;

Node createNode(int value);

int getValue(Node);

Node getNext(Node);
Node getPrevious(Node);

void setValue(Node, int value);

void setNode(Node, Node previous);
void setNext(Node, Node next);

void freeNode(Node);
#endif
#include <stdlib.h>
#include "node.h"
struct node {
int value;
Node next;
   Node previous;
};
Node createNode(int value){
Node newNode = malloc(sizeof *newNode);
newNode->value = value;
newNode->next = NULL;
   newNode->previous=NULL;
  
return newNode;
}
int getValue(Node current){
return current->value;
}
Node getNext(Node current){
return current->next;
}
Node getPrevious(Node current)
{
   return current->previous;
}

void setValue(Node current, int value){
current->value = value;
}
void setNode(Node current, Node previous){
current->previous = previous;
}
void setNext(Node current, Node next){
current->next = next;
}
void freeNode(Node current){
free(current);
}
#ifndef LIST_H
#define LIST_H
/* Wraps around Node to add important functions for a singly-linked list
* - written by Brian P. Eddy
*/
//create a handle for lists
typedef struct list* List;
/* Creates a new non-circular singly-linked list
* @return returns a new empty list
*/
List createList();
/* Get the size of the linked list
* @param List the list we need the size of
* @return the size of the linked list
*/
int size(List);

/* Adds an element to the beginning of a linked list
* @param List the list to add elements to
* @param value the item to add to the beginning of the list
*/
void prepend(List,int value);
/* Adds an element to the end of a linked list
* @param List the list to add elements to
* @param value the item to add to the end of the list
*/
void append(List,int value);
/* Inserts an element into a position in the linked list
* @param List the list to insert elements into
* @param index where to insert the element
* @param value the item to insert into the list
*/
void insert(List, int index, int value);
/* Removes an element from a position in the linked list
* @param List the list to remove elements from
* @param index where to remove the element from
* @return the value of the element that was removed
*/
int removeAt(List, int index);
/* Gets an element from a position in the linked list without removing
* @param List the list to get the element from
* @param index where to get the element from
* @return the value of the element that was retrieved
*/
int get(List, int index);
/* Prints the elements in the list
* @param List the list to print out
*/
void printList(List);
/* Frees the memory allocated for the list
* @param List the list to free
*/
void freeList(List);
#endif
#include <stdlib.h>
#include <stdio.h>
#include "list.h"
#include "node.h" //list is built upon nodes
struct list {
int size;
Node head;
Node tail;
};
List createList(){
List newList = malloc(sizeof *List);
//no nodes yet, so set both head and tail to NULL
newList->head = NULL;
newList->tail = NULL;
newList->size = 0;
return newList;
}
int size(List currentList)
{
return currentList->size;
}
void prepend(List currentList, int value){
//create the new node that we are adding
//the new node will point to the old head
Node newNode = createNode(value);
++currentList->size;
if(currentList->head==NULL)
{
currentList->head =newNode;
currentList->tail= newNode;
return;
}
else
   {
       setNode(currentList->head,newNode);
       setNext(newNode, currentList->head);
       currentList->head=newNode;
   }
if(currentList->tail == NULL)
currentList->tail = currentList->head;
  
}
void append(List currentList, int value){
//create the new node that we are going to add
Node newNode = createNode(value);
++currentList->size; //we will be increasing the size of the list
//if no nodes have been added, then both the head and tail
//will need to point to this new node
if(currentList->tail == NULL){
currentList->head = newNode;
currentList->tail = newNode;
return;
}
//otherwise, the old tail will need to point to this new node
setNext(currentList->tail, newNode);
   setNode(newNode,currentList->tail);
//update the tail so the new node is our new tail
currentList->tail = newNode;
}
void insert(List currentList, int index, int value){
//prepend and append will properly update head and tail,
//use them if possible
if(index == 0) //if inserting at beginning, use prepend
{
prepend(currentList, value);
return;
}

if(index == currentList->size) //if inserting at end, use append
{
append(currentList, value);
return;
}
if(index > currentList->size) //make sure index is in range
{
printf("Index is out of range for insert. ");
exit(1);
}
//we can't directly index into a linked list, so we have to loop
//we will need to go until we are before where we want to insert
//this will enable us to update the next pointer for the node
//that will proceed our inserted node
//start looping at the head
Node currentNode = currentList->head;
//loop until we are before where we want to insert
int i;
for(i = 0; i < index-1; ++i)
currentNode = getNext(currentNode); //move to next node
//create a new node and point it to the current node's next
Node newNode = createNode(value);
if(currentNode==NULL)
{
setNext(getNext(currentNode),newNode);  
setNext(newNode,NULL);
setNode(newNode,currentNode);
}
else
{
setNext(newNode,getNext(currentNode));
setNode(getNext(newNode),newNode);
setNext(currentNode,newNode);
setNode(newNode, currentNode);
}
++currentList->size; //increase size of the list
}
int removeAt(List currentList, int index){
//don't remove anything from an empty list
//or if index is out of bounds
if(currentList->size == 0 || index >= currentList->size)
{
printf("Cannot remove element from the list. ");
exit(1);
}

//start at the beginning of the linked list
Node currentNode = currentList->head;
//we treat index 0 differently because we don't need to update
//a next pointer
--currentList->size; //go ahead and decrease size of list
  
  
//loop until we are before where we want to remove
int i;
for(i = 0; i < index; ++i)
currentNode = getNext(currentNode); //move to next node
if(getPrevious(currentNode)!=NULL)
   setNext(getPrevious(currentNode),getNext(currentNode));
   if(getNext(currentNode)!=NULL)
       setNode(getNext(currentNode),getPrevious(currentNode));
   if(currentList->head==currentNode)
       currentList->head=getNext(currentNode);
   if(currentList->tail==currentNode)
       currentList->tail=getPrevious(currentNode);
   int value=getValue(currentNode);
   delete(currentNode);
   return value;
}
int get(List currentList, int index){
if(currentList->size == 0 || index >= currentList->size)
{
printf("Cannot get a value from given index. ");
exit(1);
}
Node currentNode;
if(index>0)
//start looping at the beginning
{

currentNode= currentList->head;
int i;
//we are actually going to the position passed in this time
for(i = 0; i < index; i++)
currentNode = getNext(currentNode); //move to next node
return getValue(currentNode);
}
else
{
currentNode= currentList->tail;
int i;
//we are actually going to the position passed in this time
for(i = 1; i <abs(index); i++)
currentNode = getPrevious(currentNode); //move to next node
return getValue(currentNode);
}
}
void printList(List currentList){
//we will display a linked list as [v1 v2 v3 v4]
//where each v# is an integer in the linked list
printf("[");//print the opening [
Node currentNode = currentList->head;
  
//let's use a while loop this time
//we will know when we have reached the end of the list
//when the currentNode is NULL
while(currentNode != NULL)
{
printf("%d",getValue(currentNode));
if(getNext(currentNode) != NULL)
printf(" ");
currentNode = getNext(currentNode);
}
printf("] "); //wrap things up
}
void printListFromEnd(List currentList)
{
printf("[");
Node currentNode =currentList->tail;
while(currentNode != NULL)
{
printf("%d",getValue(currentNode));
if(getPrevious(currentNode) != NULL)
printf(" ");
currentNode = getPrevious(currentNode);
}
printf("] "); //wrap things up
}
void freeList(List currentList){
//freeing may seem a little tricky, we will need
//to pass over the list and free each item
//before we can free the list
Node currentNode = currentList->head; //start at head
while(currentNode != NULL)
{
Node next = getNext(currentNode);//temporarily hold next
free(currentNode);//free current
currentNode = next;//set current to the next node
}
free(currentList);//finally, free the linked list
}
void disp_MENU()
{
printf(" MENU ");
printf(" 1. Get the current size of the linked list.");
printf(" 2. Prepend an item to the linked list.");
printf(" 3. Append an item to the linked list. ");
printf(" 4. Insert an item into the linked list. ");
printf(" 5. Remove an item from the linked list. ");
printf(" 6. Get an item at a specific position in the linked list.");
printf(" 7. Print the list in the forwards direction. ");
printf(" 8. Print the list in the reverse direction. ");
printf(" 9. Exit from the program. ");
}
#include <stdio.h>
#include <stdlib.h>
#include "node.h"
int main()
{

List currentList=createList();
   int ce1,rCe1;
   int idxA,itmA;
do
{
   disp_MENU();
   printf(" Enter UR choice:");
   scanf("%d",&ce1);
   switch(ce1)
   {
   case 1:
       printf(" Current size of the list is :%d",size(currentList));
       break;
   case 2:
       printf(" Enter ITEM to INSERT at FRONT:");
       scanf("%d",&itmA);
        prepend(currentList, itmA);
       break;
   case 3:
       printf(" Enter ITEM to INSERT at LAST:");
       scanf("%d",&itmA);
        append(currentList, itmA);
       break;
   case 4:
       printf(" Enter ITEM to INSERT :");
       scanf("%d",&itmA);
       printf(" Enter INDEX:");
       scanf("%d",&idxA);
       insert(currentList,idxA,itmA);
       break;
   case 5:
       printf(" Enter INDEX:");
       scanf("%d",&idxA);
       printf(" ELEMENT REMOVED: %d",removeAt(currentList,idxA));
       break;
   case 6:
       printf(" Enter INDEX:");
       scanf("%d",&idxA);
       printf(" ELEMENT AT given INDEX: %d",get(currentList,idxA));
       break;
   case 7:
       printList(currentList);
       break;
   case 8:
       printListFromEnd(currentList);
       break;
   case 9:
       exit(1);
       break;
   default:
       printf(" INVALID");
   }
printf(" DO U WANT 2 CONTINUE(1/2)");
scanf("%d",&rCe1);
}while(rCe1==1);
  
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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