Data structures in C# – Part 1 – Linked lists

Posts in this Series:

Linked Lists (this post)
Stacks
Queues
Trees

Although we use data structures daily in our programs, sometimes we forget the theory behind them. So, I decided to create this series of posts to give a refresher on the data structures theory.

This is is by no means a try to replace the current data structures (for sure, the .NET ones will be better optimized than these ones), but just a way to remember what’s going on when we use them.

They will be entirely developed in C# and I will create a WPF program to show examples of their use. So, let’s start with the first one: Linked Lists.

Linked lists are lists of elements that are linked by a pointer to the next element. Each element has a structure like this:

class NodeList
{
    public NodeList()
    {
        Next = null;
    }

    public object Data { get; set; }
    public NodeList Next { get; set; }
}

Each node stores its data and a pointer to the next node. The last node in the list points to null. The linked list would be something like this:

(Source – Wikipedia)

The only thing that the list must store is its top node. Then, all traversing is done using the Next pointers of each node. So, a basic linked list would be like this:

class LinkedList
{
    private NodeList _top = null;
}

This list wouldn’t do much, we need some operations. To insert some data in the list, we could use the Insert method:

public int Insert(object obj)
{
    var node = new NodeList { Data = obj };
    if (_top == null)
    {
        _top = node;
        _last = node;
    }
    else
    {
        _last.Next= node;
        _last = node;
    }
    _count++;
    return _count;
}

I added the fields _last, that stores the last item in the list, so there is no need to traverse the list for every inserted node and _count, that stores the number of items in the list. To clear the list, we only have to set the top node to null:

public void Clear()
{
    _top = null;
    _count = 0;
}

To get the number of Items on the list, we could call the Count property:

public int Count => _count;

We can also insert some data at a fixed position:

public int InsertAt(int position, object obj)
{
    if (position < 0 || position >= _count)
        throw (new IndexOutOfRangeException());
    var node = new NodeList { Data = obj };
    if (position == 0)
    {
        node.Next = _top;
        _top = node;
    }
    else
    {
        var current = GetNodeAt(position - 1);
        node.Next = current.Next;
        current.Next = node;
    }
    _count++;
    return _count;
}

To insert a new node in any position, we first check for the special case to insert in the first position. If it is, we replace the top item with the inserted node and set the Next property to point to the old top. If it’s another position, we traverse the tree using the GetNodeAt, to get the item before the item to be inserted and replace the next pointer of the inserted node, pointing to where the found item was pointing and replacing the next pointer of the found item, pointing to the inserted node. The GetNodeAt function is:

private NodeList GetNodeAt(int position)
{
    if (position < 0 || position >= _count)
        throw (new IndexOutOfRangeException());
    var current = _top;
    for(int i = 0; i < position;i++)
    {
        current = current.Next;
    }
    return current;
}

With GetNodeAt, we can create an indexed property to get the data in the nth node:

public object this[int index] => GetNodeAt(index).Data;

To remove a node, we just need to set the next pointer of the node before to the node after the deleted one:

public bool Remove(object obj)
{
    var currentItem = Find(obj);
    if (currentItem == -1)
        return false;
    if (currentItem == 0)
    {
        _top = _top.Next;
    }
    else
    {
        var previousNode = GetNodeAt(currentItem - 1);
        previousNode.Next = previousNode.Next.Next;
        if (previousNode.Next == null)
            _last = previousNode;
    }
    _count--;
    return true;
}

We find the item related to the object we want to remove and then set the next node to the value pointed to the node to be deleted. The Find method is:

public int Find(object obj)
{
    if (Count == 0)
        return -1;
    NodeList current = _top;
    int currentNo = 0;
    do
    {
        if (current.Data.Equals(obj))
        {
            return currentNo;
        }
        current = current.Next;
        currentNo++;
    } while (current != null);
    return -1;
}

We can also create a RemoveAt method:

public bool RemoveAt(int position)
{
    if (position < 0 || position >= _count)
        throw (new IndexOutOfRangeException());
    if (position == 0)
    {
        _top = _top.Next;
    }
    else
    {
        var previousNode = GetNodeAt(position - 1);
        previousNode.Next = previousNode.Next.Next;
        if (previousNode.Next == null)
            _last = previousNode;
    }
    _count--;
    return true;
}

We must still create one last method to retrieve all elements in the list:

public IEnumerable GetItems()
{
    if (Count == 0)
        yield break;
    _currentItem = _top;
    while (_currentItem != null)
    {
        yield return _currentItem.Data;
        _currentItem = _currentItem.Next;
    }
}

The LinkedList class is finished, but it has one issue, here: the Data property is an Object and this brings some issues: boxing and unboxing of objects, there is no verifying of data integrity (you can add any type of object, and the objects don’t need to be related). So, the next step is to introduce a Generic Linked List, so we can solve these issues. The new NodeList is:

class NodeList<T>
{
    public NodeList()
    {
        Next = null;
    }

    public T Data { get; set; }
    public NodeList<T> Next { get; set; }
}

And the new LinkedList is:

public class LinkedList<T> 
{
    private NodeList<T> _top;
    private NodeList<T> _last;
    private int _count;
    private NodeList<T> _currentItem;

    public int Insert(T obj)
    {
        var node = new NodeList<T> { Data = obj };
        if (_top == null)
        {
            _top = node;
            _last = node;
        }
        else
        {
            _last.Next = node;
            _last = node;
        }
        _count++;
        return _count;
    }

    private NodeList<T> GetNodeAt(int position)
    {
        if (position < 0 || position >= _count)
            throw (new IndexOutOfRangeException());
        var current = _top;
        for (int i = 0; i < position; i++)
        {
            current = current.Next;
        }
        return current;
    }

    public int InsertAt(int position, T obj)
    {
        if (position < 0)
            throw (new IndexOutOfRangeException());
        var node = new NodeList<T> { Data = obj };
        if (position == 0)
        {
            node.Next = _top;
            _top = node;
        }
        else
        {
            var current = GetNodeAt(position - 1);
            node.Next = current.Next;
            current.Next = node;
        }
        _count++;
        return _count;
    }

    public void Clear()
    {
        _top = null;
        _count = 0;
    }

    public int Count => _count;

    public T this[int index] => GetNodeAt(index).Data;

    public int Find(T obj)
    {
        if (Count == 0)
            return -1;
        NodeList<T> current = _top;
        int currentNo = 0;
        do
        {
            if (current.Data.Equals(obj))
            {
                return currentNo;
            }
            current = current.Next;
            currentNo++;
        } while (current != null);
        return -1;
    }

    public bool Remove(T obj)
    {
        var currentItem = Find(obj);
        if (currentItem == -1)
            return false;
        if (currentItem == 0)
        {
            _top = _top.Next;
        }
        else
        {
            var previousNode = GetNodeAt(currentItem - 1);
            previousNode.Next = previousNode.Next.Next;
            if (previousNode.Next == null)
                _last = previousNode;
        }
        _count--;
        return true;
    }

    public bool RemoveAt(int position)
    {
        if (position < 0 || position >= _count)
            throw (new IndexOutOfRangeException());
        if (position == 0)
        {
            _top = _top.Next;
        }
        else
        {
            var previousNode = GetNodeAt(position - 1);
            previousNode.Next = previousNode.Next.Next;
            if (previousNode.Next == null)
                _last = previousNode;
        }
        _count--;
        return true;
    }

    public IEnumerable<T> GetItems()
    {
        if (Count == 0)
            yield break;
        _currentItem = _top;
        while (_currentItem != null)
        {
            yield return _currentItem.Data;
            _currentItem = _currentItem.Next;
        }
    }
}

As you can see, there was not much trouble to change from a LinkedList that stores objects to a generic Linked List.

Our Linked List is ready to be used, and in the next article we will see another data structure, the Stack.

The source code for this series of articles is in https://github.com/bsonnino/DataStructures

Data structures in C# – Part 1 – Linked lists

1 thought on “Data structures in C# – Part 1 – Linked lists”

Leave a Reply Cancel reply