My Double Linked List

[Halsafar]

Just curious, how'd I do?

I wrapped it up in a class even though ever document on the basic's of a linked list showed a simple struct then functions to manage the struct. I choose to wrap it up which may have prooved a few complications but will aid in what I need it for.

I think some of it is redundant and I may be taking an extra step in some places but it works, at least what you see here.

I am working on Insertion at any point given a node, but haven't got that working well yet.

#ifndef __HAL_DOUBLELINKEDLIST
#define __HAL_DOUBLELINKEDLIST


/*
A list node
*/
template <typename _TY>
struct listNode {
    listNode() {
        pPrev = NULL;
        pNext = NULL;
    }
    listNode(_TY tData) {
        tItem = tData;
        pPrev = NULL;
        pNext = NULL;
    }
    listNode *pPrev;
    listNode *pNext;
    _TY          tItem;
};    

/*
A double linked list
*/
template <typename _TY>
class cDoubleList 
{
private:
    listNode<_TY>    *m_pHead;
    listNode<_TY>    *m_pTail;
public:
    cDoubleList<_TY>();
    ~cDoubleList();

    void Destroy();

    void InsertFront(_TY tData);
    void InsertEnd(_TY tData);
    void Insert(_TY tData, listNode<_TY> *pListNode);

    _TY  RemoveFront();
    _TY  RemoveEnd();
        _TY  Remove(listNode<_TY> *pListNode);

    bool Empty();

    listNode<_TY> *Head() {
        return m_pHead;
    }
    listNode<_TY> *Tail() {
        return m_pTail;
    }
}; 

/*
Construct the list
*/
template <typename _TY>
cDoubleList<_TY>::cDoubleList()
{

}

template <typename _TY>
cDoubleList<_TY>::~cDoubleList()
{
    Destroy();
}


/*
Destroy the lsit
*/
template <typename _TY>
void cDoubleList<_TY>::Destroy()
{
    if (Empty()) {
        return;
    }

    listNode<_TY>    *pCurrentNode = 0;
    listNode<_TY>    *pLastNode = 0;
    for (pCurrentNode = m_pHead; pCurrentNode != NULL;) {
        pLastNode = pCurrentNode;
        pCurrentNode = pCurrentNode->pNext;
        
        //Protect against circular deletion
        if (pCurrentNode == pLastNode) {
            pCurrentNode = NULL;
        }

        delete pLastNode;
    }
}


/*
Checks if the list is empty
*/
template <typename _TY>
bool cDoubleList<_TY>::Empty()
{
    if (!m_pHead) {
        return true;
    }

    return false;
}

/*
Inserts a list at the front (head)
*/
template <typename _TY>
void cDoubleList<_TY>::InsertFront(_TY tData)
{
    //No Nodes
    if (Empty()) {
        m_pHead = new listNode<_TY>(tData);
        m_pHead->pPrev = NULL;
        m_pHead->pNext = m_pTail;
        return;
    }

    //One Node
    if (!m_pTail) {
        listNode<_TY> *pNewNode = new listNode<_TY>(tData);    
        m_pTail = m_pHead;
        m_pHead = pNewNode;
        m_pHead->pNext = m_pTail;
        m_pHead->pPrev = NULL;
        m_pTail->pNext = NULL;
        m_pTail->pPrev = m_pHead;
        return;
    }

    //All inbetween
    listNode<_TY> *pNewNode = new listNode<_TY>(tData);
    m_pHead->pPrev = pNewNode;
    pNewNode->pNext = m_pHead;
    pNewNode->pPrev = NULL;
    m_pHead = pNewNode;
}


template <typename _TY>
void cDoubleList<_TY>::InsertEnd(_TY tData)
{
    //No Nodes
    if (Empty()) {
        m_pHead = new listNode<_TY>(tData);
        m_pHead->pPrev = NULL;
        m_pHead->pNext = m_pTail;
        return;
    }

    //One Node
    if (!m_pTail) {
        listNode<_TY> *pNewNode = new listNode<_TY>(tData);    
        m_pTail = pNewNode;
        m_pTail->pNext = NULL;
        m_pTail->pPrev = m_pHead;
        m_pHead->pNext = m_pTail;
        m_pHead->pPrev = NULL;
        return;
    }

    //All inbetween
    listNode<_TY> *pNewNode = new listNode<_TY>(tData);
    m_pTail->pNext = pNewNode;
    pNewNode->pPrev = m_pTail;
    pNewNode->pNext = NULL;
    m_pTail = pNewNode;
}


/*
Insert an item in front of a given node
*/
template <typename _TY>
void cDoubleList<_TY>::Insert(_TY tData, listNode<_TY> *pGivenNode)
{
    if (pGivenNode == m_pTail) {
        InsertEnd(tData);
        return;
    }

    listNode<_TY> *pNewNode = new listNode<_TY>(tData);
    pNewNode->pNext = pGivenNode->pNext;
    pNewNode->pPrev = pGivenNode;
    pGivenNode->pNext->pPrev = pNewNode;
    pGivenNode->pNext = pNewNode;
}


/*
Remove the head
*/
template <typename _TY>
_TY cDoubleList<_TY>::RemoveFront()
{
    //On empty return a 0based version of _TY
    if (Empty()) {
        _TY tTemp;
        memset(&tTemp, 0, sizeof(_TY));
        return tTemp;
    }

    //If the head has no next then it is the only one, the list dead
    if (!m_pHead->pNext) {
        _TY tTemp = m_pHead->tItem;
        delete m_pHead;
        m_pHead = NULL;
        m_pTail = NULL;

        return tTemp;
    }

    listNode<_TY> *pOldHead = m_pHead;
    m_pHead = m_pHead->pNext;
    m_pHead->pPrev = NULL;

    //If the tails end up as the head we NULL out the tail
    if (m_pTail == m_pHead) {
        m_pTail = NULL;
    }

    _TY tTemp = pOldHead->tItem;
    delete pOldHead;

    return tTemp;
}


/*
Remove an item from the end
*/
template <typename _TY>
_TY cDoubleList<_TY>::RemoveEnd()
{
    //On empty return a 0based version of _TY
    if (Empty()) {
        _TY tTemp;
        memset(&tTemp, 0, sizeof(_TY));
        return tTemp;
    }
    
    listNode<_TY> *pOld = 0; 

    //If tail doesn't exist, pop bottom else store the tail pointer
    if (!m_pTail) {
        return RemoveFront();
    } else {
        pOld = m_pTail;
    }

    //If the tails previous is the head, after the pop the tail will be the head, adjust here
    if (m_pTail->pPrev == m_pHead) {
        m_pTail = NULL;
        m_pHead->pNext = NULL;
    } else {
        m_pTail = m_pTail->pPrev;
        m_pTail->pNext = NULL;
    }

    _TY tTemp = pOld->tItem;
    delete pOld;

    return tTemp;
}


/*
Remove an item
*/
template <typename _TY>
_TY cDoubleList<_TY>::Remove(listNode<_TY> *pGivenNode)
{
    if (m_pHead == pGivenNode) {
        return RemoveFront();
    }

    pGivenNode->pPrev->pNext = pGivenNode->pNext;
    pGivenNode->pNext->pPrev = pGivenNode->pPrev;

    if (m_pTail == m_pHead) {
        m_pTail = NULL;
    }

    _TY tTemp = pGivenNode->tItem;
    delete pGivenNode;

    return tTemp;
} 

Edit: I added my working insert function.

Another Edit: I debugged it tons and found many bugs. So each function has had some minor modifications to it.

[Halsafar]

Here is a sample app to show it in use.

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#include <cDoubleList.h>
 
cDoubleList<int> dList;
//-----------------
//Main
//-----------------
int main()
{
    if (dList.Empty()) {
        cout << "LIST IS EMPTY" << endl;
    }
    
    dList.InsertFront(4);
    dList.InsertFront(5);
    dList.InsertEnd(2);
    dList.InsertFront(7);
    dList.InsertEnd(3);
    dList.Insert(6, dList.Head());
    dList.Insert(1, dList.Tail());

    cout << dList.RemoveFront() << endl;
    cout << dList.RemoveFront() << endl;
    cout << dList.RemoveFront() << endl;
    cout << dList.RemoveFront() << endl;
    cout << dList.Remove(dList.Tail()->pPrev) << endl;
    cout << dList.Remove(dList.Tail()->pPrev) << endl;
    cout << dList.RemoveEnd() << endl;

    if (dList.Empty()) {
        cout << "LIST IS EMPTY" << endl;
    }

    int x = 0;
    cin >> x;
} 

[oceanebelle]

I need to get a grip on my c/c++ again.

[Comreak]

Looking good. You could also add some sort of search function so you don't have to keep using 'next'. It wouldn't make it any more efficient, but it would certainly make it easier to use.

[CornedBee]

Looks fine. The next thing to do is to make sNode a private struct inside the list class and hide it from the user. Then, give the thing an iteration interface, so that the whole list can be traversed.

[Halsafar]

Yah, I wanted to do that.
So far the struct could be private but then the Insert() and Remove() from artibrary nodes would no longer be possible.

I was pondering on a method of transversion through the list.

[CornedBee]

The iterator interface of the standard library works really well. Try to emulate it.

[Halsafar]

I would love to but I need an explanation of the basic theory behind it.

Is it a compliation of Search functions?
Or does it allow a sort of random access? Does it ease tranversal?

A search func could be easy, pass in data and start from the head and compare the data to the data in each node.

[CornedBee]

Simplified view here, as I'm not covering const iterators or reverse iterators here.

An iterator is an object that acts very much like a pointer in that you can, depening on the category:
1) Dereference it using *. (This applies to all iterators.)
2) Apply both pre- and postincrement (++) to it. (This applies to all iterators.)
3) Use -> to call methods on referenced objects. (This applies only to forward iterators or better.)
4) Create a copy of it using a copy constructor or an assignment operator. This copy references the same object initially, but can be modified independently. (This applies only to forward iterators or better.)
5) Apply both pre- and postdecrement (--) to it. (This applies only to bidirectional iterators or better.)
6) Apply +, -, += and -= with an integer argument to it to modify its position, or use - to calculate the distance between two iterators. (This applies only to random access iterators.)

A linked list would support bidirectional iterators.

As far as the container goes, the interface is thus:
1) The iterator type is called 'iterator' and is a nested type of the container. Thus, container<T>::iterator gets a suitable iterator type.
2) The member function begin() returns an iterator that points to the first element of the container, in iteration order.
3) The member function end() returns an iterator that points one past the last element of the container, in iteration order. This means that dereferencing the end iterator yields undefined behaviour.

As such, the iterator loop is:

container<int> c;
c += 1, 2, 3, 4, 5, 6; // This requires a Boost library to work - it simply puts a few elements into the container.

for(container<int>::iterator it = c.begin(); it != c.end(); ++it) {
}

Note that the pre-increment is important, as the post-increment creates temporary copies of the iterator that waste time, since they aren't used.

So your iterator would store a pointer to its current node, on dereferencing return a reference to the node's data field, and on in- and decrementing replace the current node by the next or previous one.

At least in release mode, iterators don't do error checking. If you overflow, you overflow.

[Halsafar]

Ah yes, that makes a ton of sense.
Doesn't seem like to hard a task.

So that last snippet you posted goes along with my first mis-understanding.
A list's pointers are not fluent.
pHead+1 != pHead->pNext

so the custom iterator would have to have its own pre increment code added, so in the for loop you posted, ++it actually would have to returns the current nodes ->pNext right?

[sunburnt]

so the custom iterator would have to have its own pre increment code added, so in the for loop you posted, ++it actually would have to returns the current nodes ->pNext right?

Right -- you'll probably want to overload both the pre and post increment operators.

//pre increment
myiterator& myiterator::operator++()
{
   // ...
   return *this;
}

// post increment
myiterator myiterator::operator++(int)
{
  // ...
  return new_myiterator;
}

[Halsafar]

How would the declaration of iterator look in a class?

Sunburnt I didnt quite follow...
for(container<int>::iterator it = c.begin(); it != c.end(); ++it)
-I assume in this case iterator is type int*
-My list class begin() would return the head, end would be the tail, thus I get confusion. But if +it returns pNext on the tail it will be NULL.
- When ++it occurs, in my list class it would have to return the current nodes pNext member since none of the memory can be guarantee'd to be aligned. Each list index is created with a new call. (If I had a custom memory pool I suppose I could get rid of that problem quickly, but I'm goona save that for next game engine).

[CVMichael]

Any double linked list should have the following fuctions:
move first
move next
move previous
move last
get current item

I did not see any of those...

Also, you were talking about a search function, wich one is it ? i don't see it.

[CornedBee]

No, it should not. No container should ever have an iteration state, it just cries for trouble.

[Halsafar]

I agree with CB, who has yet to lead me wrong.
Implmenting those kinda functions would definetly lead to more trouble than ease.



I am however able to write an iterator specific to the double list...
I am yet to see the connection that can be made to write an iterator for anything.

[CVMichael]

OK, I learned linked lists, and double linked lists at school and i learned it pretty well, but I just don't get what you guys are talking about....

A double linked list where you only put data in it ??? That totaly does not makes sence to me... what's the use then ? I mean wherever you put data, you need to read it...

The code you have, looks more like a stack... wich is both FIFO (First in first out), and FILO (First in, last out). Only in a stack you don't iterate through the nodes...

[CornedBee]

Iteration is necessary, but the methods your described are the wrong way to go about it. That's because they hold the iteration position within the container, which means there can be only one iteration position, which means there can only be one iteration at a time. Even in a single-threaded environment this means that, for example, you can't perform any operations where each element of the container must be matched against each other, like:

int array[100];
for(int i = 0; i < 100; ++i) {
  for(int j = 0; j < 100; ++j) {
    cout << array[i]*array[j] << ' ';
  }
}

The iteration state (= the current element) must be held in an object separate from the container. This object is usually called the iterator, and the C++ standard library recommends a common interface for all such iterator objects.

[CVMichael]

OK, I get it now... if you have the iterator built in the doule linked list, you can't read data for a multithreaded application (or something like that)...

But to use it like the array example, you can do it with a single iterator too, but it takes more processing because it's moving back and forth a lot...

To avoid to make an extra iterator class to do only the iteration, you can include the iteration in the container (so it will have one iteration as I originally said), but make a copy constructor, and when you copy, don't actually make a copy to the whole data, just to the head and tail pointers, so then the copy will iterate the same data. (just an idea...) That way you won't have to expose the node structure since it's doing everyting internally in one class

[Halsafar]

I have read in many places that the linked list is what the array isn't.
No random access but items are added in constant time.

I do not think a list should have the ability to go dList[1] = ... Overloading the [] for a list container.

I think it would be better to use an iterator interface and do something like
itr = dList.Head();
itr++ is actually itr = itr->pNext

Which is whats been pointed out.