Self contained double ended linked list.

[Whorse]

Good evening everyone, I've recently been issued a challenge. I've got a brief to write a self contained doubly linked list that only consists of element objects. I was just wondering, how exactly you would begin such a task.

I have to begin by creating the node like so:

ListNode *pointer = new ListNode("Example");

Only using a char array, no templates or anything like that. I just need an idea of how to design the base class. I normally would make two classes; a LinkedList class then a Node class which contains a previous and next pointer and the single char. I'm not sure exactly how this differs.

[hamsterman]

What you you mean by "self contained"?
Only has one node class?
Should the line you posted create a list 0 <- E <-> x <-> a <-> m <-> p <-> l <-> e -> 0 ?

[Whorse]

I'm not sure what is meant by "self contained" myself.

[onur]

I'd use something like this:

class ListNode
{
public:
  typedef int PayloadType; // to easier migrate into a template later on
  ListNode (const PayloadType payload)
  : _previousOrZero(0)
  , _nextOrZero(0)
  , _payload(payload)
  {} ; // create a new doubly linked list

  ListNode* appendAndReturnPointerToNewNode(const Payloadype& payload);
  ListNode* prependAndReturnPointerToNewNode(const Payloadype& payload);
  bool hasNextNode() const;
  bool hasPreviousNode() const;
  ListNode* advance() const; // or use operator++
  ListNode* goBack() const; // or use operator--
  PayloadType getValue() const;

  ListNode* removeSelfAndReturnPointerToPrevious();
  ListNode* removeSelfAndReturnPointerToNext();
  void removeSelfAndAllNodesLeftAndRight();
  // maybe add a more iterator like interface and some more auxiliary functions

private:
  ListNode* _previousOrZero;
  ListNode* _nextOrZero;
  PayloadType _payload;
};

This is how the class could be used:

ListNode startNode(0);
ListNode* current = & startNode;
for (int i = 0; i < 10; ++i)
{
  current = current.appendAndReturnPointerToNewNode();
}
// doubly linked list now contains 0,1,2,...,8,9
//access 3rd element
current = & startNode;
for (int i = 0; i < 3;++i)
  current = current.advance();
std::cout << current.getValue();

startNode.removeSelfAndAllNodesLeftAndRight();

[Whorse]

Could you give me an example of how to append also? It would be much appreciated!

[rocketboy9000]

adding a node or nodes is like this, assuming end() returns a reference to the end of the list:

addnode(node *n){
	n->prev=end();
	end().next=&n;
}

[Whorse]

What is the general way of implementing a Begin and End function in linked lists?

[hamsterman]

Normally you would have a List class which holds pointers to the first and the last nodes.
In this case, you'll have to simply iterate through nodes until you find a null pointer.

[Whorse]

That would be for the end of the list, but what about the beginning?

[hamsterman]

It's a doubly linked list. It's symmetrical. It doesn't matter which way you go (as long as first node . prev == 0).

[simeonz]

In doubly-linked list the pointer-to-previous of the first node is null and the pointer-to-next of the last node is null. You can recognize them both.
EDIT: as hamsterman said :)

A problem with this approach is that you will not be able to save pointers to the first and last nodes somewhere aside. And this is usually the advantage that a List class provides over a node-based solution.

One way to hack this is to have a dummy start node and a dummy end node. They don't even need the storage slot for the payload. You will then iterate the nodes in the list starting from the second and finishing with the next to last node. The very first and very last nodes will never be relocated in memory (as your code will know not to mess with them) and you can use them to anchor parts of your code safely to the beginning and end of your list.

IMHO node-based lists are potentially useful stuff. Boost intrusive lists are a bit like that.

Regards

[Whorse]

Hey Simeonz, thanks for your informative response. Could you give me an example in some code about using dummy start and end nodes? It would be very helpful if I could visualise it a bit better!

At the moment in order to find the last node, I'm doing something like this:

	ListNode* Last()
	{
		ListNode *current = mFirst;

		while(current != NULL)
		{
			current = current->mNext;
		}

		return current;
	}

Am I on the right track?

[ne555]

So you are returning NULL.

[Whorse]

Yeah at the moment, my question is how would I get this working correctly the way I want it to?

[ne555]

current->mNext != NULL But be careful to do not dereference a null pointer

[simeonz]

Here is a prototype of the solution for dummy/sentinel nodes with some implementations left for you. Its a bit excessive and probably not the best approach for your purposes. A lot of tight coupling. There are many choices that could be made differently. Like, the links are bound to one type and the list manages the lifetime and storage for the nodes. There are other approaches.

#include <iostream>

using std::cout;
using std::endl;
using std::cin;

template <typename T>
class Node;

template <typename T>
class List;

// Link is a helper class that contains only the hooks that a node
// uses to connect to the other nodes. It contains no payload.

template <typename T>
class Link {

public:

    // Return the node corresponding to the next link.
    Node<T> *next() const
    {
        if (m_next->m_next)
        {
            return static_cast<Node<T>*>(m_next);
        }
        else
        {
            return NULL;
        }
    }

    // Return the node corresponding to the next link.
    Node<T> *prev() const
    {
        if (m_prev->m_prev)
        {
            return static_cast<Node<T>*>(m_prev);
        }
        else
        {
            return NULL;
        }
    }

    // Create a node and link it after this link.
    void insertBefore(const T &data);

    // Create a node and link it before this link.
    void insertAfter(const T &data);

protected:

    // Decouple the link from its two neighbours in the list.
    void unlink();

    // Connect link between this and the preceding one.
    void linkBefore(Link *prev);

    // Connect link between this and the next one.
    void linkAfter(Link *next);

    // Disallows constructing links directly
    Link() {}
    
    // Disallows destroying links directly
    ~Link() {}

private:

    Link *m_prev;
    Link *m_next;

    // List and Link are tightly coupled.
    // They must both understand dummy nodes.
    
    friend class List<T>;
};

// The nodes augments the links with payload.

template <typename T>
class Node : public Link<T> {

public:

    // These friend functions need to construct nodes.
    // The nodes are otherwise not constructible.
    friend
    void Link<T>::insertBefore(const T &data);

    friend
    void Link<T>::insertAfter(const T &data);

    // Destroy and deallocate the node.
    void kill();

    T &data() { return m_data; }

private:

    // Initialize the payload. Not user constructible.
    Node(const T &data);

    // Unlink the node. Not user destructible.
    ~Node();

    T m_data;
};

// List is functionality that does not have to exist in a class.
// This code is template for the way that the program can use the
// dummy nodes. Insertion/removal) are still possible by using
// the nodes entirely.

template <typename T> class List {

public:

    List()
    {
        m_start.m_prev = NULL;
        m_start.m_next = &m_end;
        m_end.m_prev = &m_start;
        m_end.m_next = NULL;
    }

    ~List()
    {
        Node<T> *current, *next = begin();

        while((current = next) != NULL)
        {
            next = current->next();
            current->kill();
        }
    }

    Node<T> *begin() const
    {
        m_start.next();
    }

    Node<T> *end() const
    {
        m_end.prev();
    }

    void push_front(const T &data)
    {
        m_start.insertAfter(data);
    }

    void push_back(const T &data)
    {
        m_end.insertBefore(data);
    }

private:

    Link<T> m_start;
    Link<T> m_end;
};

int main()
{
    {
        List<int> list;

        for(int i = 0; i < 10; ++i)
        {
            list.push_back(i);
        }

        Node<int> *next;

        // Print the numbers in the list and remove the odd ones.
        for (Node<int> *node = list.begin(); node != NULL; /*node == next*/)
        {
            cout << node->data() << endl;

            next = node->next();

            if (node->data() % 2)
            {
                node->kill();
            }

            node = next;
        }

        cout << endl;

        // Print the numbers in the list again.
        for (Node<int> *node = list.begin(); node != NULL; node = node->next())
        {
            cout << node->data() << endl;
        }
        
        // Destroy the list.
    }

    cin.get();
}

[taylorc8]

Just wondering, how would writing these data structures ever be useful? I would imagine the C++ std lib would have this covered. In what scenarios would this be useful?

[hamsterman]

It is very useful in the scenario where you want to learn something.