Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C#
Article

Implementing Linked Lists with The Null Object Pattern

Rate me:
Please Sign up or sign in to vote.
4.21/5 (11 votes)
2 Mar 2006CPOL6 min read 51.9K   291   31   10
Designing a Linked List without the use of NULL or looping
Sample Image - NullObjectLists.jpg

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:

C#
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.

C#
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:

C#
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:

C#
//return the size of a linked list
abstract int size();

In the Node class, we will simply use recursion to iterate over the list, adding one for each element we see.

C#
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.

C#
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:

C#
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.

C#
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.

C#
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:

C#
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:

C#
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:

C#
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.

C#
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:

C#
// Remove all occurrences of a value:

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.

C#
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
United States United States
I am a analytics software engineer who has spent about three years in the field developing software in .NET and other technologies for the scientific data acquisition and analysis industry. Currently I am working developing optimization algorithms for search engines. I have a B.S in Computer Science with a Minor in Mathematics from Northeastern University's College of Computer and Information Science in Boston, MA.

Comments and Discussions

 
GeneralMy vote of 1 Pin
Rob Philpott23-Feb-10 1:58
Rob Philpott23-Feb-10 1:58 
QuestionHow can the code be turned to c++ version, I have a try, But Failed! Pin
QueKai20-Nov-09 3:41
QueKai20-Nov-09 3:41 
General[My vote of 1] No thanks Pin
Luc Pattyn13-Mar-09 18:21
sitebuilderLuc Pattyn13-Mar-09 18:21 
GeneralRe: [My vote of 1] No thanks Pin
Rob Philpott23-Feb-10 2:00
Rob Philpott23-Feb-10 2:00 
GeneralRemoving an item for a very long list Pin
Mohammad Nabil H.9-Mar-06 23:51
Mohammad Nabil H.9-Mar-06 23:51 
GeneralRe: Removing an item for a very long list Pin
Matt Fowler10-Mar-06 4:17
Matt Fowler10-Mar-06 4:17 
GeneralInteresting study of a recursive data structure but... Pin
Samuel Sirois3-Mar-06 4:21
Samuel Sirois3-Mar-06 4:21 
GeneralNaming suggestion Pin
fergdeff3-Mar-06 4:19
fergdeff3-Mar-06 4:19 
QuestionMissing File in download? Pin
Dr Herbie2-Mar-06 22:04
Dr Herbie2-Mar-06 22:04 
AnswerRe: Missing File in download? Pin
Matt Fowler3-Mar-06 3:01
Matt Fowler3-Mar-06 3:01 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.