For this project we are going to use a linked list to implement a new data struc

Question

For this project we are going to use a linked list to implement a new data structure that we have not covered in class but are similar to ones that we have covered in detail. Before you begin, you must write yourself a LinkedList class and a Node class (please name your classes exactly as I did here). Please follow the below specifications for the two classes.

Node.cpp

This must be a generic class.

Should contain a generic member variable that holds the nodes value.

Should contain a next and prev Node* as denoted here.

All member variables should be private.

Use public and private member functions as you deem fit.

LinkedList.cpp

This class should be the only class creating and manipulating Node objects.

This class must be able to handle (1) singly, (2) doubly, (3) singly-circularly, and (4) doubly-circularly linked list. When the list is created, it must be given input to which type of list it will be.

This class must also have generic functions that are able to properly handle the generic node values.

Your class must at least have the following public prototypes implemented.

bool perform_operation(int op_code, T value);

Your class must at least have the following private prototypes implemented.

void append(Node** head, Node* n);

void remove_tail(Node** head);

void push(Node** head, Node* n);

Node* pop(Node** head); void remove_i(Node** head, int i);

Node* get_i(Node** head, int i); void add_i(Node** head, int i);

void print(Node** head); void delete(Node** head);

void reverse(Node** head); void rotate(Node** head, int rotations);

void random_shuffle(Node** head); int size(Node** head);

I am not specifying all the little details in the error checking, but remember we would like to write code that does not behave unexpectedly without informing the user of error.

The perform_opertation function should be the only function the uses the private member functions of the class. It will also be responsible for creating the nodes in memory.

Using the LinkedList class you just created, you will need to implement a priority stack through the creation of the PriorityStack class. A priority stack is similar to a stack but as in the priority queue we will pop the higher priority items first. You will need to write a main function that will test the functionality of all of your classes.

Explanation / Answer

The major problem with the stack implemented using array .it works only for fixed number of data values. That means the amount of data must be specified at the beginning of the implementation itself.

A stack data structure can be implemented by using linked list data structure. The stack implemented using linked list can work for unlimited number of values.

Stack implemented using array is not suitable, when we don't know the size of data which we are going to use Stack implemented using linked list works for variable size of data.

There is no need to fix the size at the beginning of the implementation. The Stack implemented using linked list can organize as many data values.

In linked list implementation of a stack, every new element is inserted as 'top' element. That means every newly inserted element is pointed by 'top'.

We want to remove an element from the stack, simply remove the node which is pointed by 'top' by moving 'top' to its next node in the list.

We can use the following steps to insert a new node into the stack.

Step 1: Create a newNode with given value.

Step 2: Check whether stack is Empty (top == NULL)

Step 3: If it is Empty, then set newNode next = NULL.

Step 4: If it is Not Empty, then set newNode next = top.

Step 5: Finally, set top = newNode.

pop() - Deleting an Element from a Stack

We can use the following steps to delete a node from the stack...

Step 1: Check whether stack is Empty (top == NULL).

Step 2: If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the function

Step 3: If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.

Step 4: Then set 'top = top next'.

Step 7: Finally, delete 'temp' (free(temp)).

display() - Displaying stack of elements

We can use the following steps to display the elements (nodes) of a stack...

Step 1: Check whether stack is Empty (top == NULL).

Step 2: If it is Empty, then display 'Stack is Empty!!!' and terminate the function.

Step 3: If it is Not Empty, then define a Node pointer 'temp' and initialize with top.

Step 4: Display 'temp data --->' and move it to the next node. Repeat the same until temp reaches to the first node in the stack (temp next != NULL).

Step 4: Finally! Display 'temp data ---> NULL'.

Program for Stack Using Linked List

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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