Create a doubly connected linkedlist class. Each node should store two pointers,
ID: 3718698 • Letter: C
Question
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 nodes.
Create iterator for your linkedlist. Explain why you need iterator for encapsulated linkedlist (As a comment on top of your main.cpp file)
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.
**Please write the code in c++
Explanation / Answer
#include<iostream>
using namespace std;
struct node
{
int info;
struct node *next;
struct node *prev;
}*list;
class linkedlist {
private:
node * head;
public:
linkedlist() {
head = NULL;
}
void push(int new_data) {
struct node* new_node = (struct node*) malloc(sizeof(node));
struct node *last = head;
new_node->info = new_data;
new_node->next = NULL;
if (head == NULL)
{
new_node->prev = NULL;
head = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
new_node->prev = last;
return;
}
void iterate()
{
struct node *curr = head;
printf(" Traversal in forward direction ");
while (curr != NULL)
{
printf(" %d ", curr->info);
curr = curr->next;
}
}
};
class priority_linkedlist {
private:
node * head;
node *front = NULL, *rear = NULL;
public:
priority_linkedlist() {
head = NULL;
}
void push(int n) {
node* news = (node*)malloc(sizeof(node));
news->info = n;
// If linked list is empty
if (front == NULL) {
front = news;
rear = news;
news->next = NULL;
}
else {
// If p is less than or equal front
// node's priority, then insert at
// the front.
if (n <= (front)->info) {
news->next = front;
(front)->prev = news->next;
front = news;
}
// If p is more rear node's priority,
// then insert after the rear.
else if (n > (rear)->info) {
news->next = NULL;
(rear)->next = news;
news->prev = (rear)->next;
rear = news;
}
// Handle other cases
else {
// Find position where we need to
// insert.
node* start = (front)->next;
while (start->info > n)
start = start->next;
(start->prev)->next = news;
news->next = start->prev;
news->prev = (start->prev)->next;
start->prev = news->next;
}
}
}
void iterate()
{
struct node *curr = head;
printf(" Traversal in forward direction ");
while (curr != NULL)
{
printf(" %d ", curr->info);
curr = curr->next;
}
}
};
//As node head node is private we can not access this from main so make an encasulated Iterate to print the list
int main()
{
linkedlist *list = new linkedlist();
list->push(3);
list->push(5);
list->push(1);
list->push(9);
list->push(99);
list->iterate();
priority_linkedlist *plist = new priority_linkedlist();
plist->push(3);
plist->push(5);
plist->push(1);
plist->push(9);
plist->push(99);
plist->iterate();
system("pause");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.