Null object design pattern in a linked list

Question

I'm trying to create a doubly linked list using the null object design pattern. I've implemented four classes: a node abstract class, nullnode and datanode classes for the null node object and the linkedlist class, for the linked list implementation. I'm not sure if I've done this correctly.

Can anyone tell me if I am correctly using the null object design pattern and if not, how I can fix it?

/* Node abstract class */
class node{
public:
node();
 node(int el) { element = el; }
 /* Return pointer to next node */
 node* getNext() { return next; }
 /* Set pointer to next node */
 void setNext(node* n) { next = n; }
 /* Return pointer to prev node */
 node* getPrev(){ return prev; }
 /* Set pointer to prev node */
 void setPrev(node* n) { prev = n; }
 /* Return element stored in node */
 int getElement() { return element; }
 /* Set element stored in node */
 void setElement(int e) { element = e; }
 node* self();
private:
 // pointer to next node 
 node* next;
 // pointer to prev node 
 node* prev;
 // element stored in node 
 int element;
};
/* Null node class */
class NullNode : public node{
public:
 /* Return pointer to next node */
 node* getNext() { return NULL; }
 /* Set pointer to next node */
 void setNext(node* n){ /* Do Nothing */ }
 /* Return pointer to prev node */
 node* getPrev() { return NULL; }
 /* Set pointer to prev node */
 void setPrev(node* n){ /* Do Nothing */ }
 /* Return element stored in node */
 int getElement() { return -1; }
 /* Set element stored in node */
 void setElement(int e){ /* Do Nothing */ }
 node* self(){ return NULL; }
};
/* datanode class */
class dataNode : public node{
public:
 dataNode(int ele) { node::node(); }
 // Return pointer to next node 
 node* getNext() { return node::getNext(); }
 // Set pointer to next node 
 void setNext(node* n){ node::setNext(n); }
 // Return pointer to prev node 
 node* getPrev() { return node::getPrev(); }
 // Set pointer to prev node 
 void setPrev(node* n){ node::setPrev(n); }
 // Return element stored in node 
 int getElement() { return node::getElement(); }
 // Set element stored in node 
 void setElement(int e){ node::setElement(e); }
 node* self(){ return this; }
};
/* linked list class */
class linkedlist{
public:
 linkedlist(){ 
 container.setNext(&container);
 container.setPrev(&container);
 }
 ~linkedlist();
 // Insert an element at the beginning of the list 
 dataNode* insertHead(int element);
 // Return pointer to first node in list
 dataNode* getHead() { return (container.getNext())->self(); }
 // Return pointer to last node in list 
 dataNode* getTail() { return (container.getPrev())->self(); }
 void insertBefore(dataNode* n, int e);
 void insertAfter(dataNode* n, int e);
// Remove specified node
void remove(dataNode* n);
private:
 // Pointer to first node in list 
 NullNode container;
};

• Winston Ewert: I'm sorry, but you don't appear to actually have working code here. That is a prerequisite for asking for a code review.

Answer 1

The question's classes are node, NullNode, dataNode, and linkedlist. Notice that the naming scheme appears not to be case-aware. It is best to fix this. Let's use camel case and capitalize the first letter. So we'll use Node, NullNode, DataNode, and LinkedList.

A problem is the type of LinkedList::container is NullNode. This means that LinkedList cannot contain DataNode objects!

DataNode -> Node (-> means implies)

NullNode -> Node

Also, the null object design pattern is not properly used for linked lists. For example, NullNode::setNode() does not set the node. What does this mean? If the caller wants to store a value in a LinkedList object and it only contains a NullNode should the method do nothing?

What if the result of NullNode::getNext() is invoked? For instance,

NullNode x = ...;
NullNode w = x.getNext();
w.getNext(); // Grr, error!

In terms of rewriting this, I'm not sure abstracting nodes (with the null object pattern) is useful for doubly (or singly) linked lists. My gut leads me to believe that using the null object pattern for abstracting the data or elements of the list may work well.

class Data
{
 // interface for getter and setter
};
class BlankData : public Data
{
 // returns 0 for summing, 1 for multiplying, etc.
};
class IntegerData : public Data
{
 // returns value
};
class Node
{
 // typical pointer handling code
 Data element;
};

Answer 2

I am not much aware of NULL Object pattern. But, I think NullNode should be a singleton as multiple object doesn't have any significance.