Update the DLinkedList class deletePos( ) BELOW method to account for a single n
ID: 3595261 • Letter: U
Question
Update the DLinkedList class deletePos( ) BELOW method to account for a single node list and an empty list. Your code should run with the driver (main) included in the code.
//COMMENT WHAT YOU ADD
//C++
#include <iostream>
using namespace std;
class Node {
public:
char letter;
Node *next, *prev;
};
class DLinkedList {
private:
Node *head, *tail; //Node pointers to head and tail
public:
DLinkedList()
{
head = NULL;
tail = NULL;
}
DLinkedList(char item) //overloaded constructor
{
Node *temp;
temp = new Node;
temp->letter = item;
temp->next = NULL;
temp->prev = NULL;
head = temp;
tail = temp;
}
void addAfter(char item, int pos);
void deletePos(int pos); //homework
void printAll();
void insertFront(char item);
void deleteFront();
void insertBack(char item);
void deleteBack();
};
void DLinkedList::deletePos(int pos)
{
Node *before, *p, *after;
p = head;
for (int i = 0; i < pos; i++) //make p point to pos
{
p = p->next;
}
before = p->prev;
after = p->next;
if (after == NULL) //last in list
{
before->next = NULL;
tail = before;
}
else if (p->prev == NULL) //if first in list
{
after->prev = NULL;
head = after;
}
//add conditions for for one item list and empty list
// else if (one item in list) //change conditions in parenthesis
//else if (empty list) //change conditions in parenthesis
else
{
before->next = after;
after->prev = before;
}
}
void DLinkedList::addAfter(char item, int pos)
{
Node *temp, *p;
p = head;
for (int i = 0; i < pos; i++) //make p point to pos
{
p = p->next;
}
//insert the node behind the current position
temp = new Node;
temp->letter = item;
//check to see if we are at the end
if (p->next == NULL)
{
//temp.insertBack(item);
p->next = temp;
temp->next = NULL;
}
else
{
temp->next = p->next; //sets temp next to the old next
(temp->next)->prev = temp; //sets the next node's previos to temp
p->next = temp;
}
temp->prev = p;
}
//----------copied and edited from SLinkedList----------
void DLinkedList::printAll() //function to print all the values in the list
{
Node *p; //creates a pointer to a node
p = head;
int i = 0;
if (head == NULL && tail == NULL) //empty list
exit;
else
{
while (p->next != NULL) //while the next value is not pointing to null
{
cout << "[" << i << "]" << p->letter << " "; //print out the nodes letter
p = p->next;
i++;
}
cout << "[" << i << "]" << p->letter << endl; //print the last node
}
}
void DLinkedList::insertFront(char item)
{
Node* temp;
temp = new Node;
temp->letter = item; //in python temp.letter = item
if (head == NULL) { //first item added to the list
temp->next = NULL;
tail = temp;
}
else
{
temp->next = head;
}
temp->prev = NULL;
head = temp;
}
void DLinkedList::deleteFront()
{
Node *p;
p = head;
head = p->next;
}
int main()
{
DLinkedList abc; //create a linked list called abc
abc.insertFront('D');
abc.addAfter('C', 0);
abc.addAfter('B', 0);
abc.printAll();
abc.deletePos(0);
abc.printAll();
abc.deletePos(0);
abc.printAll();
abc.deletePos(0);
abc.printAll();
return 0;
}
Explanation / Answer
Please find the modified method below:
void DLinkedList::deletePos(int pos)
{
if (head || n <= 0)
return;
struct Node* current = head;
int i;
/* traverse up to the node at position 'n' from
the beginning */
for (int i = 0; current != NULL && i < n; i++)
current = current->next;
/* if 'n' is greater than the number of nodes
in the doubly linked list */
if (current == NULL)
return;
/* If node to be deleted is head node */
if (head == current)
head = current->next;
/* Change next only if node to be deleted is NOT
the last node */
if (current->next != NULL)
current->next->prev = current->prev;
/* Change prev only if node to be deleted is NOT
the first node */
if (current->prev != NULL)
current->prev->next = current->next;
/* Finally, free the memory occupied by current*/
delete current;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.