2. (5 points) C++ Implement doubly linked list data structure that stores a list
ID: 3699790 • Letter: 2
Question
2. (5 points) C++ Implement doubly linked list data structure that stores a list of integers.
class Node{
int data;
Node *next;
Node *prev;
public: Node() {
data = 0; next = 0; prev = 0;}
void setData(int d) {data = d;}
void setNext(Node *n) {next = n;}
void setPrev(Node *p) {prev = p;}
int getData(){return data;}
Node* getNext(){return next;}
Node* getPrev(){return prev;}
};
class DList{
Node *head;
Node *tail;
public:
DList(){ head = 0; tail = 0;}
void printDList(); // prints all elements of the list
void InsertHead(int d); // inserts a new integer d in the list at the starting
void InsertTail(int d); // inserts a new integer d in the list at the end
void Delete(int d); // deletes all element whose value is d from the list
};
Demonstrate the class in the main program as follows:
DList list1;
for(int i=0; i<5; i++){
list1.InsertHead(i);
list1.InsertTail(3); }
list1.printDList();
list1.Delete(3);
list1.printDList();
Explanation / Answer
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
int d;
struct node *next;
struct node *prev;
}*head;
/*
Class Declaration
*/
class dList
{
public:
void createList(int value);
void InsertHead(int value);
void putAfter(int value, int position);
void Delete(int value);
void InsertTail(int value);
void printDList();
dList()
{
head = NULL;
}
};
int main()
{
dList list1;
for(int i=0; i<5; i++){
list1.InsertHead(i);
list1.InsertTail(3); }
list1.printDList();
list1.Delete(3);
list1.printDList();
}
void dList::createList(int value)
{
struct node *s, *temp;
temp = new(struct node);
temp->d = value;
temp->next = NULL;
if (head == NULL)
{
temp->prev = NULL;
head = temp;
}
else
{
s = head;
while (s->next != NULL)
s = s->next;
s->next = temp;
temp->prev = s;
}
}
/*
* Insertion at the beginning
*/
void dList::InsertHead(int value)
{
if (head == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp;
temp = new(struct node);
temp->prev = NULL;
temp->d = value;
temp->next = head;
head->prev = temp;
head = temp;
cout<<"Element Inserted"<<endl;
}
/*
* Insertion of element at a particular position
*/
void dList::putAfter(int value, int pos)
{
if (head == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *tmp, *q;
int i;
q = head;
for (i = 0;i < pos - 1;i++)
{
q = q->next;
if (q == NULL)
{
cout<<"There are less than ";
cout<<pos<<" elements."<<endl;
return;
}
}
tmp = new(struct node);
tmp->d = value;
if (q->next == NULL)
{
q->next = tmp;
tmp->next = NULL;
tmp->prev = q;
}
else
{
tmp->next = q->next;
tmp->next->prev = tmp;
q->next = tmp;
tmp->prev = q;
}
cout<<"Element Inserted"<<endl;
}
/*
* Deletion of element from the list
*/
void dList::Delete(int value)
{
struct node *tmp, *q;
/*first element deletion*/
if (head->d == value)
{
tmp = head;
head = head->next;
head->prev = NULL;
cout<<"Element Deleted"<<endl;
free(tmp);
return;
}
q = head;
while (q->next->next != NULL)
{
/*Element deleted in between*/
if (q->next->d == value)
{
tmp = q->next;
q->next = tmp->next;
tmp->next->prev = q;
cout<<"Element Deleted"<<endl;
free(tmp);
return;
}
q = q->next;
}
/*last element deleted*/
if (q->next->d == value)
{
tmp = q->next;
free(tmp);
q->next = NULL;
cout<<"Element Deleted"<<endl;
return;
}
cout<<"Element "<<value<<" not found"<<endl;
}
/*
* printDList elements of Doubly Link List
*/
void dList::printDList()
{
struct node *q;
if (head == NULL)
{
cout<<"List empty,nothing to printDList"<<endl;
return;
}
q = head;
cout<<"The Doubly Link List is :"<<endl;
while (q != NULL)
{
cout<<q->d<<" "<<" <-> ";
q = q->next;
}
cout<<"NULL"<<endl;
}
void dList::InsertTail( int new_data)
{
/* 1. allocate node */
struct node* new_node = (struct node*) malloc(sizeof(struct node));
struct node *last = head; /* used in step 5*/
/* 2. put in the data */
new_node->d = new_data;
/* 3. This new node is going to be the last node, so
make next of it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new
node as head */
if (head == NULL)
{
new_node->prev = NULL;
head = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
/* 7. Make last node as previous of new node */
new_node->prev = last;
}
Output:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.