Introduction
Many linked list implementations on the Internet mainly rely on the use of the NULL
pointer and looping to implement linked list data structures. While these implementations work perfectly fine, they are missing out on an opportunity to make code simpler and easier to understand by encapsulating the NULL
pointer by use of the Null Object Pattern. In this article, I will present a simple implementation of a linked List using the Null Object Pattern.
Re-Examining the Linked List Data Structure
Think about a linked list. What is it that makes it what it is? What are its components? To successfully design this data structure, we need to think about it from a component level. Consider this classic C++ implementation of a linked list:
class List
{
struct Node
{
int myData;
Node *next;
};
};
It looks like we have two components to our linked list, but in reality we have three. We have our data, and then we have our link to the next Node
, so far so good, but what is Node *next
actually? It has two possible values for itself, it can either be another Node
structure, or NULL
. This underlying nature of the link is how we can avoid using NULL
, if we encapsulate the behavior of NULL
in a class we can avoid its direct use. This is what the Null Object Pattern aims to do.
Designing the Data Structure
Now we have enough information to design our class. We know that a Linked list is either a Node
, or NULL
, that is to say it is empty and has nothing in it. We can define this as an abstract Linked List class, which we will call NullObjectList
, with subclasses called Node
and Empty
representing the Node
and the NULL
cases respectively.
public abstract class NullObjectList
{
}
class Node : NullObjectList
{
int data;
NullObjectList next;
Node(int data, NullObjectList next)
{
this.data = data;
this.next = next;
}
}
class Empty : NullObjectList
{
}
We can now use this simple definition to create an actual instantiation of a linked list data structure, which reveals the underlying recursive nature of linked lists:
NullObjectList myList = new Node(1, new Node(2, new Node(3, new Empty())));
Here we constantly keep calling the Node
constructor until we've reached our instance of Empty
, which replaces NULL
as the terminator of the linked list.
Designing Methods
Now we can begin to write simple abstract
methods to perform operations on our lists that take advantage of the recursive nature of the data structure. First we will develop an abstract
method which returns the number of elements in a linked list. In the NullObjectList
class, we will define the abstract
method as follows:
abstract int size();
In the Node
class, we will simply use recursion to iterate over the list, adding one for each element we see.
public override int size()
{
return 1 + next.size();
}
In the Empty
class, we know we've reached the end, so we need to have a termination of our recursion. Since empty represents NULL
, which itself represents nothing, we return the equivalent of nothing, zero.
public override int size()
{
return 0;
}
We probably don't want to rely on recursive definitions such as LinkedList myList = new Node(1, new Node(2, new Node(3,new Empty())));
as they're not practical to type out. However we can very easily hide this by formulating a method to take care of this for us. We will develop an abstract
method to append an integer to the end of the linked list. In the abstract
class NullObjectList
, our definition for this abstract
method is as given below:
public abstract NullObjectList append(int toAppend);
Now let's concentrate on how we go about appending an integer to a linked list. The basic algorithm is to find the end of the list, and replace the NULL
(empty) portion with a new list with the integer we wish to append. So the approach will be similar to our size method, we will use recursion to create a copy of the caller's list when we write this method for the Node
class.
public override NullObjectList append(NullObjectList toAppend)
{
return new Node(this.data, this.next.append(toAppend));
}
If we expand out this recursion to a form more easily readable, it becomes clearer that what we're doing is equivalent to the way we originally declared our first linked list instance:
call 1 : new Node( this.data,
call 2 : new Node( this.next.data,
call 3 : new Node( this.next.next.data,
call n : new Node( this.next.next.next.
... .next.data, ... ))));
But now what do we do in the Empty
class? Since we're making a copy of the list, and merely replacing what would have been the empty instance, we can just return the integer we were passed in a Node
class when we write this method in the Empty
class.
public override NullObjectList append(int toAppend)
{
return new Node(toAppend, new Empty());
}
Now we can easily use this function to append integers to a list, for example:
NullObjectList list = new Empty();
list = list.append(1);
list = list.append(2);
Almost as easily, we can create an abstract
method to remove all occurrences of a specific integer of a list. Our definition in the NullObjectList
class will be as follows:
public abstract NullObjectList remove(int rem);
Since we will be creating a new list recursively with this function, it will be exactly the same as our append
function, but we need to add an if
-else
clause to account for the removal condition we'll have. In the Node
class, we write:
public override NullObjectList remove(int rem)
{
if (this.data == rem)
return this.next.remove(rem);
else
return new Node(this.data, this.next.remove(rem));
}
The last line is exactly the same as it was with our last function, but if the data in the current node we're looking at matches what we're trying to remove, we use no new call, ignoring this.data
and moving through and copying the rest of the list without this.data
.
When we write this method for the Empty
class, all we need to do is simply add a new instance of Empty
to signify we're at the end of the list.
public override NullObjectList remove(int rem)
{
return new Empty();
}
Demonstration Project
A simple demonstration project is included for this article, contained in the C# file testClass.cs. It is a simple program that allows the user to enter choices to append, remove, get the size of a list, or print out the list, starting off with an empty list. A function not discussed here, printList
, is a simple recursive function to traverse the list and print out the values of individual nodes.
Conclusions
The use of the Null Object pattern together with its naturally simple recursive way of writing methods has the ability to substantially simplify code, making it take up less lines as well as being more easily read. Consider the implementation of the remove
method in the List
class in the Standard Template Library:
template <class T>
void list<T>::remove(const T& value) {
iterator first = begin();
iterator last = end();
while (first != last) {
iterator next = first;
++next;
if (*first == value) erase(first);
first = next;
}
}
Consider the main implementation of the remove
function in the Linked List we implemented.
public override NullObjectList remove(int rem)
{
if (this.data == rem)
return this.next.remove(rem);
else
return new Node(this.data, this.next.remove(rem));
}
The code in the STL which is several lines of code longer than our version, is substantially more verbose and therefore harder to read and understand. By using the Null Object Design pattern, we have substantially increased the readability of the function as well as reduced the number of lines of code needed to implement a function. This is one of the main advantages of using this pattern.
When we use this pattern, we also avoid the use of NULL
checking in our programs entirely, reducing again the size of code required and eliminating the possibility of forgetting to check the NULL
case, a common error.
This design is not without its disadvantages. The main disadvantage of this pattern is that the Empty
class that acts as a placeholder for NULL
can take up memory while storing no real, uniquely useful data. That is to say that multiple occurrences of the Empty
class can be wasteful, especially if we have a lot of lists that we need in memory. However, this is a shortcoming that can easily be resolved by combining the Empty
class with a Singleton
Pattern to ensure that only one instance of this class is created and shared between all Lists.
History
- 2nd March, 2006: Initial post