91 % 12:37 AM Assignement 4 Create a doubly connected linkedlist class. Each nod

Question

91 % 12:37 AM Assignement 4 Create a doubly connected linkedlist class. Each node should store two pointers, next and prev. Encapsulate your class such that client does not have access to Create iterator for your linkedlist. Explain why you need iterator for encapsulated linkedlist (As a comment on top of your main.cpp Create a priority linkedlist class. Data of each node becomes priority of that node. You should have only one insert function (Call it push) that inserts the item based on its priority The highest priority item is the head of the list The pop function removes the highest priority item and return its value. The top function is the same as pop but does not remove the item Explain why you should not have iterator for the priority_linkedlist Calculate the running time of all three functions of priority_linkedlist **Your implementation should have all the requirements and it should work correct and safe. Knowing what is needed to make your implementation safe and valid is part of this question and will not be explained.

Explanation / Answer

// File Name: DoubleLinkedList.cpp
#include<stdlib.h>
#include<iostream>
using namespace std;

// Defines a class DLNode
class DLNode
{
// Data member to store data
int data;
// Pointer to next node in DLL
DLNode *nextNode;
// Pointer to previous node in DLL
DLNode *prevNode;

public:
// Prototype of member function
void printList(DLNode *);
void appendNode(DLNode** , int);
};// End of class

// Function prints contents of linked list starting from the given node
void DLNode::printList(DLNode *current)
{
// Declares a temporary node
DLNode *last;
cout<<" Traversal in forward direction ";

// Loops till current node is not null
while (current != NULL)
{
// Displays the current node data
cout<<current->data<<" ";
// Node last points to current
last = current;
// Move next
current = current->nextNode;
}// End of while loop

cout<<" Traversal in reverse direction ";
// Loops till last node is not null
while (last != NULL)
{
// Displays the last node data
cout<<last->data<<" ";
// Move previous
last = last->prevNode;
}// End of while loop
}// End of function

// Function to appends a new node at the end
void DLNode::appendNode(DLNode** head, int newData)
{
// Dynamically creates a new node
DLNode *newNode = new DLNode();

// Temporary pointer points to head
DLNode *last = *head;

// Assigns parameter data to new node
newNode->data = newData;

// Assigns NULL to new node next
newNode->nextNode = NULL;

// Checks if the linked list is empty, then make the new node as head
if (*head == NULL)
{
// Assigns new node previous to NULL
newNode->prevNode = NULL;
// head points to new node
*head = newNode;
return;
}// End of if condition

// Otherwise

// Loop till end of the linked list
while (last->nextNode != NULL)
// Move next
last = last->nextNode;

// Change the next of last node
last->nextNode = newNode;

// Make last node as previous of new node
newNode->prevNode = last;

return;
}// End of function

**********************************************************************

// File Name: DoubleLinkedListMain.cpp
#include<iostream>
#include "DoubleLinkedList.cpp"
using namespace std;

// main function definition
int main()
{
// Creates a head pointer assigns NULL to it
DLNode* head = NULL;
// Displays heading
cout<<" **********************************************";
cout<<" Double Linked List ";
cout<<" **********************************************";
// Calls the function to append node
head->appendNode(&head, 6);
head->appendNode(&head, 12);
head->appendNode(&head, 3);
head->appendNode(&head, 89);
// Calls the function to display linked list data
head->printList(head);
return 0;
}// End of main function

Sample Output:

**********************************************
Double Linked List
**********************************************
Traversal in forward direction
6 12 3 89
Traversal in reverse direction
89 3 12 6

----------------------------------------------------------------------------------------------------------------------------------

// File Name: PriorityLinkedList.cpp
#include<stdlib.h>
#include<iostream>
using namespace std;

class PRNode
{
int data;
// Lower values indicate higher priority
int priority;
PRNode* next;
public:
PRNode* newNode(int d, int p);
int peek(PRNode** head);
void pop(PRNode** head);
void push(PRNode** head, int d, int p);
int isEmpty(PRNode** head);
};

// Function to Create A New Node
PRNode* PRNode::newNode(int d, int p)
{
PRNode* temp = new PRNode();
temp->data = d;
temp->priority = p;
temp->next = NULL;

return temp;
}

// Return the value at head
int PRNode::peek(PRNode** head)
{
return (*head)->data;
}

// Removes the element with the
// highest priority form the list
void PRNode::pop(PRNode** head)
{
PRNode* temp = *head;
(*head) = (*head)->next;
free(temp);
}

// Function to push according to priority
void PRNode::push(PRNode** head, int d, int p)
{
PRNode* start = (*head);

// Create new Node
PRNode* temp = newNode(d, p);

// Special Case: The head of list has lesser
// priority than new node. So insert new
// node before head node and change head node.
if ((*head)->priority > p) {

// Insert New Node before head
temp->next = *head;
(*head) = temp;
}
else {

// Traverse the list and find a
// position to insert new node
while (start->next != NULL &&
start->next->priority < p) {
start = start->next;
}

// Either at the ends of the list
// or at required position
temp->next = start->next;
start->next = temp;
}
}

// Function to check is list is empty
int PRNode::isEmpty(PRNode** head)
{
return (*head) == NULL;
}

----------------------------------------------------------------------------

// File Name: PriorityLinkedListMain.cpp
#include<iostream>
#include "PriorityLinkedList.cpp"
using namespace std;

// main function definition
int main()
{
// Creates a head pointer assigns NULL to it
PRNode* head = head->newNode(4, 1);
// Displays heading
cout<<" **********************************************";
cout<<" Priority Linked List ";
cout<<" **********************************************";
// Calls the function to push a node
head->push(&head, 5, 2);
head->push(&head, 6, 3);
head->push(&head, 7, 0);
cout<<endl;
// Loops till queue is empty
while (!head->isEmpty(&head))
{
// Calls the function to peek the data from queue and displays it
cout<<head->peek(&head)<<endl;
// Calls the function to pop the data
head->pop(&head);
}// End of while loop
return 0;
}// End of main function

Sample Output:

**********************************************
Priority Linked List
**********************************************
7
4
5
6

Related Questions

Navigate

• Browse (All)
• Browse 9
• Subjects

---

---

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