Implement the following specification of UnsortedType using

Implement the following specification of UnsortedType using circular linked list as the implementation structure.

*** I have seen this question answered here before but it is not a good answer. Can someone please give me a original answer.***

// Deliverables:
// - A listing of the specification and implementation files for UnsortedType
// - A listing of the driver program for your test plan
// - A listing of the test plan as input to the driver.
// - A listing of the output from the driver.

template
struct NodeType;

/* Assumption: ItemType is a type for which the operators
\"<\" and \"==\" are defined-either an appropriate built-in type or a
class that overloads these operators. */

template
class UnsortedType
{
public:
// Class constructor, destructor, and copy constructor
UnsortedType();
~UnsortedType();
UnsortedType(const UnsortedType&);

void operator=(UnsortedType);

bool IsFull() const;
// Determines whether list is full.
//Post: Function value = (list is full)

int GetLength() const;
// Determines the number of elements in list.
// Post: Function value = number of elements in list.

void RetrieveItem(ItemType& item, bool& found);
// Retrieves list element whose key matches item\'s key
// (if present).
// Pre: Key member of item is initialized.
// Post: If there is an element someItem whose key matches
// item\'s key, then found = true and item is a copy of
// someItem; otherwise found = false and item is unchanged.
// List is unchanged.

void InsertItem(ItemType item);
// Adds item to list.
// Pre: List is not full.
// Item is not in list.
// Post: item is in list.

void DeleteItem(ItemType item);
// Deletes the element whose key matches item\'s key
// Pre: Key member of item is initialized.
// One and only one element in list has a key matching
// item\'s key.
// Post: No element in list has a key matching item\'s key.

void ResetList();
// Initializes current position for an iteration through the list.
// Post: Current position is prior to list.

void GetNextItem(ItemType&);
// Gets the next element in list.
// Pre: Current position is defined.
// Element at current position is not last in list.
// Post: Current position is updated to next position.
// item is a copy of element at current position.

private:
NodeType* listData;
int length;
NodeType* currentPos;
};

Solution

#include<stdio.h>

#include<stdlib.h>

/* structure for a node */

struct node

{

  int data;

  struct node *next;

};

/* function to insert a new_node in a list in sorted way.

   Note that this function expects a pointer to head node

   as this can modify the head of the input linked list */

void sortedInsert(struct node** head_ref, struct node* new_node)

{

  struct node* current = *head_ref;

  // Case 1 of the above algo

  if (current == NULL)

  {

     new_node->next = new_node;

     *head_ref = new_node;

  }

  // Case 2 of the above algo

  else if (current->data >= new_node->data)

  {

    /* If value is smaller than head\'s value then

      we need to change next of last node */

    while(current->next != *head_ref)

        current = current->next;

    current->next = new_node;

    new_node->next = *head_ref;

    *head_ref = new_node;

  }

  // Case 3 of the above algo

  else

  {

    /* Locate the node before the point of insertion */

    while (current->next!= *head_ref &&

           current->next->data < new_node->data)

      current = current->next;

    new_node->next = current->next;

    current->next = new_node;

  }

}

/* Function to print nodes in a given linked list */

void printList(struct node *start)

{

  struct node *temp;

  if(start != NULL)

  {

    temp = start;

    printf(\"\ \");

    do {

      printf(\"%d \", temp->data);

      temp = temp->next;

    } while(temp != start);

  }

}

/* Driver program to test above functions */

int main()

{

  int arr[] = {12, 56, 2, 11, 1, 90};

  int list_size, i;

  /* start with empty linked list */

  struct node *start = NULL;

  struct node *temp;

  /* Create linked list from the array arr[].

    Created linked list will be 1->2->11->12->56->90 */

  for (i = 0; i< 6; i++)

  {

    temp = (struct node *)malloc(sizeof(struct node));

    temp->data = arr[i];

    sortedInsert(&start, temp);

  }

  printList(start);

  return 0;

}