doubly linked list

[nowy20180820]

Write your question here.

  #include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;

template <class T>
class Node
{
    T data;
    Node<T> *prev;
    Node<T> *next;
public:
    Node();
    Node(T d);
    void setData(T data);
    T getData();
    void setPrev(Node<T> *prev);
    Node<T> *getPrev();
    void setNext(Node<T> *next);
    Node<T> *getNext();
};

template <class T>
Node<T>::Node()
{
    next = nullptr;
    prev = nullptr;
}

template <class T>
Node<T>::Node(T d)
{
    data = d;
    next = nullptr;
    prev = nullptr;
}

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

template <class T>
T Node<T>::getData()
{
    return data;
}

template <class T>
void Node<T>::setPrev(Node<T> *prev)
{
    this->prev = prev;
}

template <class T>
Node<T> * Node<T>::getPrev()
{
    return prev;
}

template <class T>
void Node<T>::setNext(Node<T> *next)
{
    this->next = next;
}

template <class T>
Node<T> *Node<T>::getNext()
{
    return next;
}

template<class T>
class LinkedList
{
    Node<T> *head;
public:
    LinkedList();
    void setHead(Node<T> *head);
    Node<T> *getHead();
    bool isEmpty();
    void print();
    Node<T> *searchNode(T k);
    void insertNode(T k);
    void deleteNode(T k);
    ~LinkedList();
};

template<class T>
LinkedList<T>::LinkedList()
{
    head = nullptr;
}

template<class T>
void LinkedList<T>::setHead(Node<T> *head)
{
    this->head = head;
}

template<class T>
Node<T> *LinkedList<T>::getHead()
{
    return head;
}

template<class T>
bool LinkedList<T>::isEmpty()
{
    return getHead() == nullptr;
}

template<class T>
void LinkedList<T>::print()
{
    Node<T> *p = getHead();
    Node<T> *q = nullptr;
    int counter = 0;
    cout<<"Head traversal"<<endl;
    while(p != nullptr)
    {
        q = p;
        cout<<p->getData()<<" -> ";
        counter++;
        p = p->getNext();
    }
    cout<<"NULL"<<endl;
    cout<<"Number of nodes on the list :"<<counter<<endl;
    counter = 0;
    cout<<"Tail traversal"<<endl;
    while(q != nullptr)
    {
        cout<<q->getData()<<" -> ";
        counter++;
        q = q->getPrev();
    }
    cout<<"NULL"<<endl;
    cout<<"Number of nodes on the list :"<<counter<<endl;
}

template<class T>
Node<T> *LinkedList<T>::searchNode(T k)
{
    Node<T> *p = getHead();
    while(p != nullptr && p->getData() != k)
        p = p->getNext();
    return p;
}

template<class T>
void LinkedList<T>::insertNode(T k)
{
    Node<T> *x = new Node<T>(k);
    Node<T> *y = getHead();
    Node<T> *z = nullptr;
    while(y != nullptr && x->getData() > y->getData())
    {
        z = y;
        y = y->getNext();
    }
    if(z == nullptr)
    {
        x->setNext(getHead());
        if(getHead() != nullptr)
        {
            getHead()->setPrev(x);
        }
        setHead(x);
        x->setPrev(nullptr);
    }
    else
    {
       x->setNext(y);
       if(y != nullptr)
            y->setPrev(x);
       x->setPrev(z);
       z->setNext(x);
    }
}

template<class T>
void LinkedList<T>::deleteNode(T k)
{
    Node<T> *x = searchNode(k);
    if(x != nullptr)
    {
        if(x->getPrev() != nullptr)
            x->getPrev()->setNext(x->getNext());
        else
            setHead(x->getNext());
        if(x->getNext() != nullptr)
            x->getNext()->setPrev(x->getPrev());
        delete x;
    }
}

template<class T>
LinkedList<T>::~LinkedList()
{
    while(!isEmpty())
        deleteNode(getHead()->getData());
}

int main()
{
    int k,m,n;
    LinkedList<int> *L = new LinkedList<int>();
    srand(time(nullptr));
    cout << "Enter number of nodes"<<endl;
    cin>>n;
    cout<<"Enter the upper range of data in nodes" << endl;
    cin>>m;
    for(k=0;k<n;k++)
        L->insertNode(rand()%m);
    L->print();
    L->~LinkedList();
    return 0;
}

Code seems to work as i expect but
if i declare list not as a pointer i get error
like this
conversion from 'LinkedList<int>*' to non-scalar type 'LinkedList<int>' requested

How to fix this error

Suppose i would like to introduce pointer to the tail node
How should i update it in functions which modify the list

[ne555]

if you have issues with your code, then post the code that is giving you those issues
don't post a code that's different and it hasn't those particular errors


> Suppose i would like to introduce pointer to the tail node
> How should i update it in functions which modify the list
¿what functions would need to keep it updated? ¿how did you manage with `head'?

[nuderobmonkey]

I tested your code with at the the online shell and it worked fine, even without instantiating your list as an object on the heap.

Here the main() which I used for testing at the online shell:

int main()
{
    int k,m,n;
    LinkedList<int> L;// = new LinkedList<int>();
    srand(time(nullptr));
    // cout << "Enter number of nodes"<<endl;
    n = 5; //cin>>n;
    //cout<<"Enter the upper range of data in nodes" << endl;
    m = 10; //cin>>m;
    for(k=0;k<n;k++)
        L.insertNode(rand()%m);
    L.print();
    //delete L;
    return 0;
}

Here the output:

Head traversal
1 -> 1 -> 4 -> 6 -> 9 -> NULL
Number of nodes on the list :5
Tail traversal
9 -> 6 -> 4 -> 1 -> 1 -> NULL
Number of nodes on the list :5