Question

inserting a node after given node.

DLL::DLL(int x){ // constructor, initializes a list with one new node with data x
   DNode *n = new DNode (x);
   first = n;
   last = n;
   size=1;
}

DNode::DNode( int x){
   data = x;
   next = NULL;
   prev = NULL;
}

void DLL::addFirst(int x) {
   DNode* tmp = new DNode(x);
   first = tmp;
   last = first;
}

void DLL::insertAt(int ind, int x) {
   int i = 0;
   DNode *tmp = first;
   DNode *tmp2;
   while(i < ind && tmp != NULL) {
       i += 1;
       tmp2 = tmp;
       tmp = tmp->next;
   }

   if (tmp != NULL) {
       DNode *tmp3 = new DNode(x);
       tmp3->next = tmp;
       tmp->prev = tmp3;
       tmp2->next = tmp3;
       tmp3->prev = tmp2;
   }

}

command to get out put:

codelist.addFirst(0);
    codelist.printList();
    codelist.insertAt(1,1);
    codelist.printList();
    codelist.insertAt(2,3);
    codelist.printList();
    codelist.insertAt(2,2);
    codelist.printList();
    codelist.push(4);
    codelist.printList();
    codelist.insertAt(2,42);
    codelist.printList();

desired output:

0,

0, 1,

0, 1, 3,

0, 1, 2, 3,

0, 1, 2, 3, 4,

0, 1, 42, 2, 3, 4,

actual output:

0,
0,
0,
0,
0, 4,
0, 4,

Answer 1

Please find the following answer for the given program in CPP.

Note:

1. The reason for your incorrect output is, you are inserting the value in index 1 but the index is not a valid element in the double linked list because you have insert 1 first element as 0, then inserting the element 1 in index 1 but the DLL doesnt have index 1. Hence it is added as part of codelist.

2. But when you push the element it always added as last element that why you have got element 4 added as part of DLL and rest of the elements are not added.

3. I have added screen shots and comments inline for better understanding.

Fix description: We have added a else part to handle if there is no element in that position and hence it will added as part of last element.

Screen Shot of corrected function:

Program:

#include <iostream>

using namespace std;

class DNode
{
public:
int data;
DNode *next, *prev;
DNode(int x);
};

class DLL
{
private:
DNode *first;
DNode *last;
int size;
  
public:
DLL(int x);
DLL();
void addFirst(int x);
void printList();
void insertAt(int ind, int x);
void push(int x);
};

DNode::DNode( int x)
{
data = x;
next = NULL;
prev = NULL;
}

// default constructor, initializes a list with NULL values
DLL::DLL()
{
first = NULL;
last = NULL;
size = 0;
}

DLL::DLL(int x)
{ // constructor, initializes a list with one new node with data x
DNode *n = new DNode (x);
first = n;
last = n;
size=size+1;
}

void DLL::addFirst(int x)
{
DNode* tmp = new DNode(x);
first = tmp;
last = first;
}

void DLL::printList()
{
DNode* temp = this->first;
  
   while(temp)
   {
       cout << temp->data<< ", ";
       temp = temp->next;
   }
   cout<<endl;
}

void DLL::insertAt(int ind, int x)
{
int i = 0;
DNode *tmp = first;
DNode *tmp2;
while(i < ind && tmp != NULL)
{
i += 1;
tmp2 = tmp;
tmp = tmp->next;
}

if (tmp != NULL)
{
DNode *tmp3 = new DNode(x);
tmp3->next = tmp;
tmp->prev = tmp3;
tmp2->next = tmp3;
tmp3->prev = tmp2;
}
//added the else part because if a user enter a value to insert at position 1 and if there is not element in
//position 1, then we add at the last.
//This is the reason for your incorrect output
else
{
//uncomment this line for debugging
//cout << "we have reached the end of list, hence adding the element at the end of DLL"<<endl;
DNode *tmp3 = new DNode(x);
last->next=tmp3;
tmp3->prev=last;
last=tmp3;
}
}

void DLL::push(int x)
{
if (first==NULL)
{
cout <<"List is empty, allocate memory to it\n";
}
else
{
DNode *tmp = new DNode(x);
last->next=tmp;
tmp->prev=last;
last = tmp;
}
}

int main()
{
DLL codelist;
  
codelist.addFirst(0);
codelist.printList();
codelist.insertAt(1,1);
codelist.printList();
codelist.insertAt(2,3);
codelist.printList();
codelist.insertAt(2,2);
codelist.printList();
codelist.push(4);
codelist.printList();
codelist.insertAt(2,42);
codelist.printList();
return 0;
}

Output:

0,
0, 1,
0, 1, 3,
0, 1, 2, 3,
0, 1, 2, 3, 4,
0, 1, 42, 2, 3, 4,

Screen Shot:

Output ScreenShot: