Linked list and Double linked list in C#

December 22, 2010

Below are two examples of implementing a linked and double linked list in C#. The framework already has a LinkedList implementation from version 2.0 - it is infact a double linked list and supports a whole lot of features the example below doesn’t. I wrote the code below out of curiosity more than anything (some programmers like doing this kind of thing, some don’t!). Most degree students or earlier will have learnt about linked lists in their courses, some may have not.

The links at the bottom of the page give a whole host of discussions on the subject, mostly from stackoverflow. You might wonder where you’d ever need to use a (double) linked list, and you might be right when it comes .NET however the class itself is used internally by Regex and by a System.Net timer. It’s not (as I previously said here) used by stacktraces for Exceptions, these are are handled by the StackTrace and StackFrame classes.

But anything that needs a parent-child relationship makes use of a form of it, and a single linked list is an alternative form of a stack or queue.

As always with all the code on the site, if you spot a bug or something you think is a glaring load of rubbish, feel free to contact me on the contact page.

Linked List

	public static void Main()
	{
	LinkedList list = new LinkedList();
	list.Insert("1");
	list.Insert("2");
	list.Insert("3");
	list.Insert("4");
	list.Insert("5");
	Console.WriteLine("List: " + list);

	while (!list.IsEmpty)
	{
	Link deletedLink = list.Delete();
	Console.Write("Removed: " + deletedLink);
	Console.WriteLine("");
	}

	Console.WriteLine("List: " + list);
	Console.Read();
	}

	public class Link
	{
	public string Title { get; set; }
	public Link NextLink { get; set; }

	public Link(string title)
	{
	Title = title;
	}

	public override string ToString()
	{
	return Title;
	}
	}

	public class LinkedList
	{
	private Link _first;
	public bool IsEmpty
	{
	get
	{
	return _first == null;
	}
	}

	public LinkedList()
	{
	_first = null;
	}

	public Link Insert(string title)
	{
	// Creates a link, sets its link to the first item and then makes this the first item in the list.
	Link link = new Link(title);
	link.NextLink = _first;
	_first = link;

	return link;
	}

	public Link Delete()
	{
	// Gets the first item, and then this to be the one it is linked forward to
	Link temp = _first;
	if (_first != null)
	_first = _first.NextLink;

	return temp;
	}

	public override string ToString()
	{
	Link currentLink = _first;
	StringBuilder builder = new StringBuilder();
	while (currentLink != null)
	{
	builder.Append(currentLink);
	currentLink = currentLink.NextLink;
	}
	return builder.ToString();
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

Doubly linked list

As you can see, the implementation for a doubly linked list doesn’t differ much from a linked list. The extra functionality comes in the form of operations like deep copying, enumerators, advanced finds and inserts which I’ve left out; these are in framework’s LinkedList implementation.

	public static void Main()
	{
	DoubleLinkedList list = new DoubleLinkedList();
	list.Insert("1");
	list.Insert("2");
	list.Insert("3");

	DoubleLink link4 = list.Insert("4");
	list.Insert("5");
	Console.WriteLine("List: " + list);

	list.InsertAfter(link4, "[4a]");
	Console.WriteLine("List: " + list);
	Console.Read();
	}

	public class DoubleLink
	{
	public string Title { get; set; }
	public DoubleLink PreviousLink { get; set; }
	public DoubleLink NextLink { get; set; }

	public DoubleLink(string title)
	{
	Title = title;
	}

	public override string ToString()
	{
	return Title;
	}
	}

	public class DoubleLinkedList
	{
	private DoubleLink _first;
	public bool IsEmpty
	{
	get
	{
	return _first == null;
	}
	}
	public DoubleLinkedList()
	{
	_first = null;
	}

	public DoubleLink Insert(string title)
	{
	// Creates a link, sets its link to the first item and then makes this the first item in the list.
	DoubleLink link = new DoubleLink(title);
	link.NextLink = _first;
	if (_first != null)
	_first.PreviousLink = link;
	_first = link;
	return link;
	}

	public DoubleLink Delete()
	{
	// Gets the first item, and sets it to be the one it is linked to
	DoubleLink temp = _first;
	if (_first != null)
	{
	_first = _first.NextLink;
	if (_first != null)
	_first.PreviousLink = null;
	}
	return temp;
	}

	public override string ToString()
	{
	DoubleLink currentLink = _first;
	StringBuilder builder = new StringBuilder();
	while (currentLink != null)
	{
	builder.Append(currentLink);
	currentLink = currentLink.NextLink;
	}
	return builder.ToString();
	}

	///// New operations
	public void InsertAfter(DoubleLink link, string title)
	{
	if (link == null \|\| string.IsNullOrEmpty(title))
	return;
	DoubleLink newLink = new DoubleLink(title);
	newLink.PreviousLink = link;
	// Update the 'after' link's next reference, so its previous points to the new one
	if (link.NextLink != null)
	link.NextLink.PreviousLink = newLink;
	// Steal the next link of the node, and set the after so it links to our new one
	newLink.NextLink = link.NextLink;
	link.NextLink = newLink;
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

Chris's coding blog

Linked list and Double linked list in C#

Linked List

Doubly linked list

Links