Wednesday, 8 August 2018

Doubly Linked List in C#

I am reading the book "C#7 and .NET Core 2.0 High Performance" about data structures and came accross Doubly linked lists. This is an interesting data structure. We most often use arrays and lists in .NET in everyday use, but both are not as high performant as linked lists when it comes to inserting and removing items in their structure. Removing an item and inserting an item in a list is only quick, if we add to the end of the list or remove from the end of the list. Arrays have the same behavior, if you have a large data structure with many items, consider using a LinkedList instead. .NET already got a good implementation of linked lists in System.Collections.Generic with the LinkedListNode class, so this article just presents a class I wrote for fun on my own. If you want to see the source code of the .Net class, it is available here:
LinkedListNode implementation(Reference Source /.NET)
Now how fun is it to just use .NET's implementation, we want to learn something and do things ourselves as devoted coders? Therefore I present my own implementation! You can find the source code by cloning the following Git repo: Actually, the implementation is easy, the most cumbersome part is to be careful with the next and previous pointers. Just like the .NET implementation, this class supports generic and a payload of different types, in the demo I will use string as the payload of each node.

git clone https://toreaurstad@bitbucket.org/toreaurstad/doublylinkedlist.git


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
// ReSharper disable ArrangeThisQualifier
// ReSharper disable RedundantNameQualifier

namespace DoublyLinkedList
{

    /// <summary>
    /// Node in a doubly linked list data structure with pointers to the previous and next item in the linked list, if any.
    /// Allows quick insertion and removal of values in even large data structures
    /// </summary>
    /// <typeparam name="T">The type of Data in each node of the doubly linked list</typeparam>
    public class LinkedListNode<T>
    {

        public LinkedListNode(T data)
        {
            _data = data;
            _prev = null; //Init previous reference to null
            _next = null; //Init next reference to null
        }


        public T Data
        {
            get { return _data; }
        }

        /// <summary>
        /// Attempts to find a value in the doubly linked list. Uses object.Equals for comparison. O(N) complexity.
        /// </summary>
        /// <param name="value">Value to find</param>
        /// <returns>The first node with the matching value, if any.</returns>
        public LinkedListNode<T> Find(T value)
        {
            if (object.Equals(Data, value))
                return this;
            if (this._next is null)
                return null;
            return Find(this._next, value);
        }

        /// <summary>
        /// Attempts to find a value in the doubly linked list by a matchen with a given predicate. Returns null if no node values matches. O(N) complexity 
        /// </summary>
        /// <param name="searchCondition"></param>
        /// <returns></returns>
        public LinkedListNode<T> Find(Predicate<LinkedListNode<T>> searchCondition)
        {
            if (searchCondition(this))
                return this;
            if (this._next != null)
                return this._next.Find(searchCondition);
            return null;
        }

        /// <summary>
        /// Searches for multiple values and returns the nodes found. The search returns the first match if any for every search value. O(N*N) complexity.
        /// </summary>
        /// <param name="values"></param>
        /// <returns></returns>
        public LinkedListNode<T>[] FindMultiple(params T[] values)
        {
            if (values is null)
                throw new ArgumentNullException(nameof(values));
            if (!values.Any())
                throw new ArgumentException("Please provide a nonempty array of values!");
            var foundValues = new List<LinkedListNode<T>>();
            foreach (T value in values)
            {
                LinkedListNode<T> foundValue = Find(value);
                if (foundValue != null)
                    foundValues.Add(foundValue);
            }

            return foundValues.ToArray();
        }

        // ReSharper disable once UnusedMember.Local
        private LinkedListNode<T> Find(LinkedListNode<T> node, Predicate<T> searchCondition)
        {
            if (node is null)
                return null;
            if (searchCondition(node.Data))
                return node;
            if (node._next != null)
                return Find(node._next, searchCondition);
            return null;
        }

        private LinkedListNode<T> Find(LinkedListNode<T> node, T value)
        {
            if (node is null)
                return null;
            if (object.Equals(node.Data, value))
                return node;
            if (node._next != null)
                return Find(node._next, value);
            return null;
        }

        /// <summary>
        /// Inserts a node into the doubly linked list. Adjusts the prev and next pointers of the inserted node. O(1) complexity.
        /// </summary>
        /// <param name="node">The node to insert, node's prev and next pointers will be overwritted if already set.</param>
        /// <returns>The inserted node with updated prev and next pointers</returns>
        public LinkedListNode<T> Insert(LinkedListNode<T> node)
        {
            if (node is null)
                throw new ArgumentNullException(nameof(node));

            LinkedListNode<T> nextNode = this._next;
            node._prev = this;
            this._next = node;
            node._next = nextNode;
            if (nextNode != null)
                nextNode._prev = node;

            return node;
        }

        /// <summary>
        /// Inserts multiple nodes into the doubly linked list by building nodes with passed in values. O(1) complexity.
        /// </summary>
        /// <param name="values"></param>
        /// <returns></returns>
        public LinkedListNode<T>[] Insert(params T[] values)
        {
            if (values is null)
                throw new ArgumentNullException(nameof(values));
            if (!values.Any())
                throw new ArgumentException("Please provide a nonempty array of values!");

            values = values.Reverse().ToArray(); //Reverse order so insertion behaves sequentially 

            var inserted = new List<LinkedListNode<T>>();

            foreach (T value in values)
            {
                LinkedListNode<T> node = new LinkedListNode<T>(value);
                inserted.Add(Insert(node));
            }

            return inserted.ToArray();
        }

        /// <summary>
        /// Removes a node from the linked list. Adjusts the previous and next pointers of removed node. O(1) complexity.
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public LinkedListNode<T> Remove(LinkedListNode<T> node)
        {
            if (node is null)
                throw new ArgumentNullException(nameof(node)); 

            if (node._prev != null)
                node._prev._next = node._next;
            if (node._next != null)
                node._next._prev = node._prev;

            //Set unneeded references to null now and to avoid misuse
            node._prev = null;
            node._next = null;

            return node;
        }

        public void Remove()
        {
            if (this._prev != null)
                this._prev._next = this._next;
            if (this._next != null)
                this._next._prev = this._prev;

            //Set unneeded references to null now and to avoid misuse
            this._prev = null;
            this._next = null;
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            if (this._prev is null)
                sb.Append(Head);
            sb.Append(_data + GetArrow(this));
            IterateLinkedList(this._next, sb);
            return sb.ToString();
        }

        /// <summary>
        /// Iterates the doubly linked list and builds a string to output in the ToString() method
        /// </summary>
        /// <param name="node">LinkedListNode</param>
        /// <param name="sb">StringBuilder</param>
        private void IterateLinkedList(LinkedListNode<T> node, StringBuilder sb)
        {
            if (node != null)
            {
                sb.Append(node.Data + GetArrow(node));
                if (node._next != null)
                    IterateLinkedList(node._next, sb);
            }
        }

        private string GetArrow(LinkedListNode<T> node)
        {
            if (node != null)
            {
                if (node._next != null && node._next._prev != null)
                    return DoubleArrow;
                if (node._next != null && node._next._prev == null)
                    return Arrow;
                if (node._next == null)
                    return Arrow + NullString;
            }

            return ArrowUndefined;
        }

        private const string Head = "HEAD->";

        private const string Arrow = "->";

        private const string DoubleArrow = "<->";

        private const string ArrowUndefined = "??MISSINGLINK??";

        private const string NullString = "NULL";

        private readonly T _data;

        private LinkedListNode<T> _prev;

        private LinkedListNode<T> _next;

    }
}


This implementation has not got a specific pointer to the head of the list like a circular linked list can provide. The following code makes use of this class to demonstrate its usage:

using System;
using System.Diagnostics;
using System.Linq;

namespace DoublyLinkedList
{
    class Program
    {
        // ReSharper disable once UnusedParameter.Local
        static void Main(string[] args)
        {
            var root = new LinkedListNode("Hello");
            root.Insert(new LinkedListNode("world"));
            root.Insert(new LinkedListNode("Testing"));
            root.Insert(new LinkedListNode("Double linked list!"));

            root.Insert("Inserting", "some", "values!");

            root.Insert("Delete", "me", "please");

            root.FindMultiple("Delete", "me").ToList().ForEach(n => n.Remove(n));

            root.Find(n => n.Data.Contains("pl")).Remove();

            var mismatch = root.Find("Nonexisting value");
            Debug.Assert(mismatch is null, "Expected to not find any item in this doubly linked list with this search value");

            string rootRepresentation = root.ToString();

            Debug.Assert(rootRepresentation == @"HEAD->Hello<->Inserting<->some<->values!<->Double linked list!<->Testing<->world->NULL");

            Console.WriteLine(rootRepresentation);

            Console.ReadKey();
        }
    }
}

The output of this linked list is displaying the contents of the doubly linked list:

HEAD->Hello<->Inserting<->some<->values!<->Double linked list!<->Testing<->world->NULL

As we can see, with our ToString implementation we can deduce that the first and last node is special, the first one lacks a prev pointer illustrated by "HEAD->" and the last node lacks a next pointer illustrated with "->NULL". You will find this in the implementation of the class. I have decided to actually revert the order if the client wants to insert multiple values, as that ordering behaves more naturally. The client can look after a value or multiple values or search with a given predicate, or pass in a node and use it to search. Also, it is possible to remove a node. We end up with an implementation of a Doubly Linked list that can be used in many scenarios. I would advice you to use the .NET version as it supports more features, such as a pointer to the HEAD node. But this implementation is compact and easy to understand for many developers. You will usually use linked list in scenarios where you have much data and want to quickly insert or remove one or several nodes in the linked list. It also supports quick navigation from a node to its previous or next node. Imagine for example working with a class called Book which needs to have an iterable structure ("Pages") to move to the next and previous page and at the same time insert new pages or removing a page from the middle of the data structure. Using an array or a list would be low performant and slow, while a doubly linked list would actually allow the developer to create code that quickly inserts a new page or removes a page at an arbitrary position in the data structure of the Book. This class can of course be optimized to support for example circular linked list with a pointer always to HEAD, or maybe you want to have pointer to HEAD and TAIL and not have a circular list? The source code should be relatively self explanatory for the intermediate C#-developer to revise and improve. I hope you found this article interesting.

1 comment:

  1. AWS Training in Bangalore - Live Online & Classroom
    myTectra Amazon Web Services (AWS) certification training helps you to gain real time hands on experience on AWS. myTectra offers AWS training in Bangalore using classroom and AWS Online Training globally. AWS Training at myTectra delivered by the experienced professional who has atleast 4 years of relavent AWS experince and overall 8-15 years of IT experience. myTectra Offers AWS Training since 2013 and retained the positions of Top AWS Training Company in Bangalore and India.

    IOT Training in Bangalore - Live Online & Classroom
    IOT Training course observes iot as the platform for networking of different devices on the internet and their inter related communication. Reading data through the sensors and processing it with applications sitting in the cloud and thereafter passing the processed data to generate different kind of output is the motive of the complete curricula. Students are made to understand the type of input devices and communications among the devices in a wireless media.

    ReplyDelete