Using C++ Goals Build double linked lists using pointers Learn how to manipulate

Question

Using C++

Goals

Build double linked lists using pointers

Learn how to manipulate linked lists

In this lab, you will create a simple double linked structures consisting of Node objects. Each node will have a pointer to the next node and a pointer to the previous node. You will use a head pointer to keep track of the first node in the linked list, and a tail pointer to keep track of the last node in the linked list. Set both head and tail to NULL when the list is empty. You will store an integer in each node. You can assume all the integers are positive numbers. You will create the list dynamically by user input.

Implement following functions in the linked list:

Add a new node to the head;

Add a new node to the tail;

Delete from head (the first node in the list);

Delete from tail (the last node in the list);

Traverse the list reversely, that is to print the node from back to the forth.

When user tries to add a new node (functions 1&2), your program will prompt the user to enter a number and validate the input, create a new node in the list, store the value properly, change the head/tail pointers and print the current whole list from head to the tail.

When user tries to delete a node (functions 3&4), your program should check whether the list is empty, if so, give a warning message, and if not, delete the node properly and free the memory, then point the head/tail pointers to the new position, and print out the whole list.

When user tries to print the list from tail to the head (functions 5), your program will print the value from the last node to the first node. If the list is empty, print a message to indicate that.

You need to add one more option in your menu to exit the program.

For this lab, you will not implement the linked list operations using functions/methods that from an outside source. That means you need to write all the functions by yourself.

Additionally:

Task 1 : add two more options to print the head or the tail node value.

Task 2 : create a linked list from reading a text file. You can create your own text file with some numbers in it, and your program should have an option to create the list from the text file at the very beginning. Then users will continue to manipulate on the existing list.

Explanation / Answer

/*NOTE:

create a text file named "textFile" to initialise value from text file

*/

#include<bits/stdc++.h>
#include<string>
#include<fstream>
/*
* Node Declaration
*/
using namespace std;
struct node
{
int info;
struct node *next;
struct node *prev;
}*head=nullptr,*tail=nullptr;

/*
Class Declaration
*/
class double_llist
{
public:
void add_head(int value);
void add_tail(int value);
void delete_head();
void delete_tail();
void display_dlist();
void printHeadNodeValue();
void printTailNodeValue();

};

/*
* Main: Conatins Menu
*/
int main()
{
int choice, element;
double_llist dl;
int elem;
ifstream file;
file.open("textFile.txt");
int nod;
while(file>>nod){
dl.add_tail(nod);
}
file.close();
while (1)
{
cout<<endl<<"----------------------------"<<endl;
cout<<endl<<"Operations on Doubly linked list"<<endl;
cout<<endl<<"----------------------------"<<endl;
cout<<"1.Add a node at Head"<<endl;
cout<<"2.Add a node at tail"<<endl;
cout<<"3.Delete from head"<<endl;
cout<<"4.Delete from tail"<<endl;
cout<<"5.Print the node from back to forth"<<endl;
cout<<"6.Print the head node value"<<endl;
cout<<"7.Print the tail node value"<<endl;
cout<<"8.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch ( choice )
{
case 1:
cout<<"Enter the element: ";
cin>>element;
dl.add_head(element);
cout<<endl;
break;
case 2:
cout<<"Enter the element: ";
cin>>element;
dl.add_tail(element);
cout<<endl;
break;
case 3:
if (head == NULL)
{
cout<<"List empty,nothing to delete"<<endl;
break;
}
dl.delete_head();
cout<<endl;
break;
case 4:
if (tail == NULL)
{
cout<<"List empty,nothing to delete"<<endl;
break;
}
dl.delete_tail();
cout<<endl;
break;
case 5:
dl.display_dlist();
cout<<endl;
break;
case 6:
dl.printHeadNodeValue();
break;
case 7:
dl.printTailNodeValue();
break;
case 8:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
return 0;
}

void double_llist::add_head(int value)
{
struct node *temp;
temp = new(struct node);
temp->next = nullptr;
temp->info = value;
temp->prev = nullptr;
if (head == nullptr)
{
head = tail = temp;
}
else{
head->prev = temp;
temp->next = head;
head = temp;
}
}

void double_llist::add_tail(int value){
struct node *temp;
temp = new(struct node);
temp->prev = nullptr;
temp->info = value;
temp->next = nullptr;
if(tail == nullptr){
head = tail = temp;
}
else{
temp->prev = tail;
tail->next = temp;
tail = temp;
}
}

void double_llist::delete_head(){
if(head = nullptr)
cout<<"linked list is empty"<<endl;
else{
struct node *temp;
if(head->next == nullptr){
temp = head;
head = nullptr;
free(temp);
}
else{
temp = head;
head = head->next;
head->prev = nullptr;
free(temp);
}
}
}

void double_llist::delete_tail(){
if(tail = nullptr)
cout<<"linked list is empty"<<endl;
else{
struct node *temp;
if(tail->prev == nullptr){
temp = tail;
tail = nullptr;
free(temp);
}
else{
temp = tail;
tail = tail->prev;
tail->next = nullptr;
free(temp);
}
}
}
/*
* Display elements of Doubly Link List
*/
void double_llist::display_dlist()
{
struct node *q;
if (tail == NULL)
{
cout<<"List empty,nothing to display"<<endl;
return;
}
q = tail;
cout<<"The Doubly Link List is :"<<endl;
while (q != NULL)
{
cout<<q->info<<" <-> ";
q = q->prev;
}
cout<<"NULL"<<endl;
}

void double_llist::printHeadNodeValue(){
if(head == nullptr)
cout<<"There is no element to print"<<endl;
else
cout<<"Head node value is : "<<head->info<<endl;
}

void double_llist::printTailNodeValue(){
if(tail == nullptr)
cout<<"There is no element to print"<<endl;
else
cout<<"Tail node value is : "<<tail->info<<endl;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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