In: Computer Science
Can you make this singular linked list to doubly linked list
Create a Doubly Linked List.
Use this to create a Sorted Linked List,
Use this to create a prioritized list by use. Bring to front those links recently queried.
-----link.h------
#ifndef LINK_H
#define LINK_H
struct Link{
int data;
Link *lnkNxt;
};
#endif /* LINK_H */
----main.cpp----
//System Level Libraries
#include <iostream> //I/O Library
using namespace std; //Libraries compiled under std
#include"Link.h"
//Global Constants - Science/Math Related
//Conversions, Higher Dimensions
//Function Prototypes
void pop_front(Link *&front);
void pop_back(Link *&front);
void push_front(int data, Link *&front);
void push_back(int data, Link *&front);
void prntLst(Link *front);
void dstryLst(Link *&front);
void prntLst(Link* front);
Link *fillLnk(int); //Fill a Link
Link *fillLst(int); //Populate the List
//Execution Begins Here!
int main(int argc, char** argv) {
//Random Number Seed Set Here
//Variable Declarations
Link *lnk1;
//Variable Initialization
lnk1 = fillLst(5);
//Mapping Process Inputs to Outputs
//Display Outputs
cout << endl << "The Printed List" << endl;
prntLst(lnk1);
//Test new functions
pop_front(lnk1);
cout << endl << "The Printed List after popfront
function" << endl << endl;
prntLst(lnk1);
pop_back(lnk1);
cout << endl << "The Printed List after popback
function" << endl << endl;
prntLst(lnk1);
push_front(10, lnk1);
cout << endl << "The Printed List after pushfront
function" << endl << endl;
prntLst(lnk1);
push_back(20, lnk1);
cout << endl << "The Printed List after pushback
function" << endl << endl;
prntLst(lnk1);
//Clean Up, Delete all the elements in the list
delete (lnk1);
//Exit stage right!
return 0;
}
// function to remove the front element
void pop_front(Link *&front) {
if (front != NULL) { //if not the end of the list
Link *temp = front; // new pointer set equal to front
front = front->lnkNxt; //front points to the next node
delete(temp);
}
}
// function to remove the back element
void pop_back(Link *&front) {
if (front != NULL) {
Link *curr = front;
Link *prev = NULL;
while (curr->lnkNxt != NULL) {
prev = curr;
curr = curr->lnkNxt;
}
if (prev == NULL)
front = NULL;
else
prev->lnkNxt = curr->lnkNxt;
delete(curr);
}
}
// function to insert data at the front
void push_front(int data, Link *&front) {
Link *node = new Link;
node->data = data;
node->lnkNxt = front;
front = node;
}
// function to insert data at the end
void push_back(int data, Link *&front) {
Link *node = new Link;
node->data = data;
node->lnkNxt = NULL;
if (front == NULL)
front = node;
else {
Link *curr = front;
while (curr->lnkNxt != NULL)
curr = curr->lnkNxt;
curr->lnkNxt = node;
}
}
// function to print the list
void prntLst(Link *front) {
Link *curr = front;
while (curr != NULL) {
cout << curr->data << endl;
curr = curr->lnkNxt;
}
}
Link *fillLst(int nLinks) {
Link *front = fillLnk(1); //first Link
Link *next = front; // pointer to move thru the List
for (int i = 2; i <= nLinks; i++) {//attaches one link after
another
Link *newLnk = fillLnk(i);
next->lnkNxt = newLnk;
next = newLnk;
}
next->lnkNxt = NULL;
return front;
}
//fills the list
Link *fillLnk(int data) {
Link *lnk = new Link;
lnk->data = data;
return lnk;
}
// function to destroy the list
void dstryLst(Link *&front) {
while (front != NULL) {
Link *temp = front;
front = front->lnkNxt;
delete(temp);
}
}
Here created function void prntLstBackward(Link* ptr) is for backward traversing in doubly linked list
Modified link.h
#ifndef LINK_H
#define LINK_H
struct Link
{
int data;
Link *lnkNxt;
Link *lnkPrv;
};
#endif /* LINK_H */
Modified main.cpp
//System Level Libraries
#include <iostream.h> //I/O Library
//using namespace std; //Libraries compiled under std
#include"Link.h"
#include<stdlib.h>
//Global Constants - Science/Math Related
//Conversions, Higher Dimensions
//Function Prototypes
void pop_front(Link *&front);
void pop_back(Link *&front);
void push_front(int data, Link *&front);
void push_back(int data, Link *&front);
void prntLst(Link *front);
void dstryLst(Link *&front);
void prntLst(Link* front);
void prntLstBackward(Link* ptr);
Link *LastAddr(Link* front);
Link *fillLnk(int); //Fill a Link
Link *fillLst(int); //Populate the List
//Execution Begins Here!
int main(int argc, char** argv)
{
//Random Number Seed Set Here
//Variable Declarations
Link *lnk1,*ptr;
//Variable Initialization
lnk1 = fillLst(5);
//Mapping Process Inputs to Outputs
//Display Outputs
cout << endl << "The Printed List"
<< endl;
prntLst(lnk1);
cout <<endl<<" The list traversing from
last to first"<<endl;
ptr=LastAddr(lnk1);
prntLstBackward(ptr);
//Test new functions
pop_front(lnk1);
cout << endl << "The Printed List after
popfront function" << endl << endl;
prntLst(lnk1);
pop_back(lnk1);
cout << endl << "The Printed List after
popback function" << endl << endl;
prntLst(lnk1);
push_front(10, lnk1);
cout << endl << "The Printed List after
pushfront function" << endl << endl;
prntLst(lnk1);
push_back(20, lnk1);
cout << endl << "The Printed List after
pushback function" << endl << endl;
prntLst(lnk1);
//Clean Up, Delete all the elements in the list
delete (lnk1);
//Exit stage right!
return 0;
}
// function to remove the front element
void pop_front(Link *&front)
{
if (front != NULL)
{ //if not the end of the list
Link *temp = front; // new pointer
set equal to front
front = front->lnkNxt;
front->lnkPrv=NULL; //front
points to the next node
delete(temp);
}
}
// function to remove the back element
void pop_back(Link *&front)
{
if (front != NULL)
{
Link *curr = front;
Link *prev = NULL;
while (curr->lnkNxt !=
NULL)
{
prev =
curr;
curr =
curr->lnkNxt;
}
if (prev == NULL)
front =
NULL;
else
{
prev->lnkNxt = curr->lnkNxt;
curr->lnkNxt->lnkPrv=prev;
}
delete(curr);
}
getch();
}
// function to insert data at the front
void push_front(int data, Link *&front)
{
Link *node = new Link;
node->data = data;
node->lnkNxt = front;
node->lnkPrv=NULL;
front = node;
}
// function to insert data at the end
void push_back(int data, Link *&front)
{
Link *node = new Link;
node->data = data;
node->lnkNxt = NULL;
node->lnkPrv=NULL;
if (front == NULL)
front = node;
else
{
Link *curr = front;
while (curr->lnkNxt !=
NULL)
curr =
curr->lnkNxt;
curr->lnkNxt = node;
node->lnkPrv=curr;
}
}
// function to print the list
void prntLst(Link *front)
{
Link *curr = front;
while (curr != NULL)
{
cout << curr->data
<< endl;
curr = curr->lnkNxt;
}
}
void prntLstBackward(Link *ptr)
{
Link *curr = ptr;
while (curr != NULL)
{
cout << curr->data
<< endl;
curr = curr->lnkPrv;
}
}
Link *fillLst(int nLinks)
{
Link *front = fillLnk(1); //first Link
Link *next = front; // pointer to move thru the
List
for (int i = 2; i <= nLinks; i++)
{//attaches one link after another
Link *newLnk = fillLnk(i);
next->lnkNxt = newLnk;
newLnk->lnkPrv=next;
next = newLnk;
}
next->lnkNxt = NULL;
return front;
}
//fills the list
Link *fillLnk(int data)
{
Link *lnk = new Link;
lnk->data = data;
lnk->lnkNxt=NULL;
lnk->lnkPrv=NULL;
return lnk;
}
// function to destroy the list
void dstryLst(Link *&front)
{
while (front != NULL)
{
Link *temp = front;
front = front->lnkNxt;
delete(temp);
}
}
Link * LastAddr(Link *front)
{
Link *temp;
temp=front;
while(temp->lnkNxt!=NULL)
temp=temp->lnkNxt;
return temp;
}
Output