Question

I am trying to create my own doubly linkedlist class and here is what I have so far. my addfirst is adding elements forever and ever, and I could use some help. This is in C++. Please help me complete my doubly linkedlist class. the addfirst method is what I would like to complete.

#ifndef DLLIST_H
#define DLLIST_H
#include "node.h"
#include
using namespace std;
template
class DLList
{
private:

    Node* head = nullptr;
    Node* tail = nullptr;
    T data;
    // private DLList stuff goes here
public:
    // public DLList stuff goes here
    DLList();
    DLList(const DLList&L);
    DLList& operator=(const DLList &L);
    ~DLList();
    void addFirst(T data);
    void addElement(int position, T data);
    void remove(int position);
    void printElements();
    void removeFirst();
    bool exists(T value);
};
template
DLList::DLList(){
    head = nullptr;
    tail = nullptr;
    this ->data = data;
}

template
DLList::DLList(const DLList&L){
     L.head = head;
     while(L.head != nullptr){
         L.data = head->data;
         head = head -> next;
     }
     L.tail = tail;
     L.data = data;
}

template
DLList&DLList::operator=(const DLList &L){
     L.head = head;
     while(L.head != nullptr){
         L.data = head->data;
         head = head -> next;
     }
     L.tail = tail;
     L.data = data;
}

template
DLList::~DLList(){

}

template
void DLList::printElements(){
      Node* curr = head;
      while(curr != nullptr){
          cout << curr->data;
      }

}
template
//create new node
//set appropriate data
//set next to current head
//set nodes prev to nullptr
//set past heads previous to node
void DLList::addFirst(T data){
     Node* node = new Node();
     node->setData(data);
     if(head == nullptr){
         head = node;
         head -> next = nullptr;
         head -> prev = nullptr;
     }
     else{
     node -> next = head;
     node -> prev = nullptr;
     head -> prev = node;
     }
}

template
//create node with data
//traverse to find the area to insert
//adjust the pointers
void DLList::addElement(int position,T data){
    Node* node = new Node();
    node->setData(data);
    Node* curr = new Node();
    curr -> head;
    for(int i = 0; i < position - 1; i++){
         curr = curr -> next;
    }
    node -> prev = curr -> prev;
    curr -> prev = node;
    node -> next = curr;
    node -> prev -> next = node;

}

template
void DLList::remove(int position){
     Node* curr = head;
     Node* next = curr;
     for(int i = 0; i < position - 1; i++){
         curr = curr -> next;
     }
     curr -> prev = nullptr;
     curr -> next = nullptr;
     curr -> prev -> next = curr -> next;
}

template
void DLList::removeFirst(){
   Node* curr = head;
   curr -> next -> prev = nullptr;
   curr -> next = nullptr;

}

template
bool DLList::exists(T value){
    Node* curr = head;
    while(curr != nullptr){
        if(curr->data == value){
            return true;
        }
       curr = curr-> next;
    }
    return false;
}

#endif // DLLLIST_H

//here is my node class for reference.

#ifndef NODE_H
#define NODE_H
using namespace std;
template
class Node{
private:
    T data;
    Node* next;
    Node* prev;
    template
    friend class DLList;
public:
    Node();
    Node(const Node& N);
    T& getData();
    void setData(T data);
    Node* getNext();
    Node* getPrev();
    /*Node():next(nullptr),prev(nullptr){}
    Node(T val):next(nullptr),prev(nullptr),data(val){}
    Node(const Node& rhs):next(nullptr),prev(nullptr),data(rhs.data){}
    ~Node();*/
};

template
Node::Node(){
    next = nullptr;
    prev = nullptr;
}

template
Node::Node(const Node& N){
    N.next = next;
    N.prev = prev;
    N.data = data;
}

template
T& Node ::getData(){
    return data;
}

template
void Node:: setData(T data){
    this -> data = data;
}

template
Node* Node::getNext(){
   return next;
}

template
Node* Node::getPrev(){
    return prev;
}

/*template
Node::Node(T data){
     this->data = data;
}

template
T Node::getData(){
    return this -> data;
}

template
Node::~Node(){

}*/

#endif // NODE_H

Answer 1

Assuming addFirst() adds an element to the beginning of your DLL, I found a few logical errors.

Firstly, you didn't update your tail while adding an element to your new list ( you only updated the head) which causes the tail to keep pointing to NULL. This may lead to issues elsewhere.

Secondly, whenever adding an element to an existing list, you have not updated the head.

Please see the updated snippet:

void DLList::addFirst(T data){
Node* node = new Node();
node->setData(data);
if(head == nullptr){
head = node;
head -> next = nullptr;
head -> prev = nullptr;

tail = node; //update tail if first element
//tail = x; //I mistyped x instead of node
}
else{
node -> next = head;
node -> prev = nullptr;
head -> prev = node;
head = node; //update head
}
}

Lastly, I found issues with your print function. You didn't change the value of curr, which was causing your infinite loop.

void DLList::printElements(){
Node* curr = head;
while(curr != nullptr){
cout << curr->data;
curr = curr->next; //traverse to the next node / nullptr
}

}

As you only requested help for the addFirst(), I have not tested the other methods.