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.
No comments:
Post a Comment