C# OOP: Creating a List using Composition

Greetings, and welcome to this new article at Programmer's Ranch!

I will be using this article and the next few to introduce you to Object Oriented Programming (OOP). In the articles so far, we've mostly put all the code in the Main() method. That might work for small programs, but as things get more complex, it's useful to model them as different components, or objects, that together make up something bigger. Think of a car - it's made up of the engine, steering wheel, and many other parts.

The .NET collections, of which we have seen a few, are a good example of the relationships between objects in OOP. Although .NET provides its own List class (see "C# Basics: Snake Game in ASCII Art (Part 2)"), in this article we will implement a list of our own and use it to learn OOP.

There are many different ways to implement a list; below is one of them:

The various items in the list are the purple boxes. Each item, apart from storing some kind of data (in this case a letter), keeps a reference to the next item in the list (the last one points to null).

For convenience, we also keep a reference to the first and last items in the list. This helps us when we need to process the list. For example, we could have used just a Head and left out the Tail, but then we'd have to go through the whole list sequentially if we had to use the last item in the list.

The above diagram shows what is actually in a list item. As I mentioned earlier, all we need is a Next reference pointing to the next item in the list, and the actual Data we are storing in the list item.

This design is enough to create the list. Create a new SharpDevelop console application, and start by adding a ListItem class. In this simple example you can add classes directly in Program.cs, but for more complex scenarios it's convenient to have classes in their own file (right click on project, Add -> New Item..., select Class and give it a name).

    class ListItem
    {
        public ListItem Next;
        public String Data;
       
        public ListItem(String data)
        {
            this.Next = null;
            this.Data = data;
        }
    }

The ListItem contains a reference to the next item in the list, and the actual data stored in the list item (as I said earlier). I am also using a constructor to initialise Next to null, and set Data to whatever value is provided.

The actual list itself is just as straightforward to create:

    class List
    {
        public ListItem Head;
        public ListItem Tail;
       
        public List()
        {
            this.Head = null;
            this.Tail = null;
        }
    }

The list contains a Head (first item) and a Tail (last item). Any items between them can be reached by following Next references from the head. In the List constructor, we initialise both Head and Tail to null since the list is empty.

We can now add some methods to the List to help us work with it. In particular we want to allow items to be added to the end of the list:

        public void Add(String data)
        {
            ListItem item = new ListItem(data);
           
            if (this.Head == null) // list is empty
            {
                this.Head = item;
                this.Tail = item;
            }
            else
            {
                // set (old) tail's Next to new item
                this.Tail.Next = item;
                // new item is the new tail
                this.Tail = item;
            }
        }

If the list is empty, we set both head and tail to the new item, since it is the only item in the list. Otherwise, the item is added to the end of the list. This means that item that was last becomes the one before the last, and the tail must be updated. Note that I could have simplified the code by taking this.Tail = item; out of the conditional, but I thought it's clearer for human consumption this way.

Let's also add a method that shows the contents of the list, so that we can check our work:

        public void Show()
        {
            ListItem currentItem = this.Head;
           
            while (currentItem != null)
            {
                Console.WriteLine(currentItem.Data);
                currentItem = currentItem.Next;
            }
        }

All we're doing here is starting at the head and visiting the items one by one. For each item, we write its data to the console, and then move to the next item until we hit a null (which would be at the tail).

In Main(), we can now write code to use our list:

        public static void Main(string[] args)
        {
            Console.Title = "C# OOP Composition using Lists";
           
            List shoppingList = new List();
           
            shoppingList.Add("sausages");
            shoppingList.Add("beans");
            shoppingList.Add("jam");
            shoppingList.Add("water");
           
            shoppingList.Show();
           
            Console.ReadLine();
        }

...and voilà:

Awesome. This article probably felt like an exercise in data structure design, and in a way that's true. However, we have used something called composition to create our list data structure. Our list contains ListItem data members. Another way to see it is that the list is made up (composed) of those ListItems.

Composition is probably the most basic part of working with OOP. Complex software is full of objects that contain other objects, and that's pretty intuitive, because so is the world.

The real challenge in designing complex systems using OOP (which is the part that most people get wrong) is getting the relationships between objects right. There are many other ways for objects to interact other than composition, and we will take a look at them in the coming articles.