Linked lists in C#

[wossname]

(I've had to restart this thread since it lost it's way a bit)

How can I do Linked lists properly in C#?

I know how to do it in C++ but I'm new to C# and its a bit of a grey area.

Thanks.

Preferably a 2 way linked list, but 1 will suffice.

Many thanks

[Memnoch1207]

This might help.

Linked List in C#

[CornedBee]

I wrote one too, a long time ago.

using System;

namespace System.Collections
{
	class Node
	{
		internal Node _prev;
		internal Node _next;
		internal object _data;
		internal bool _valid = true;
	}

	/// <summary>
	/// A double linked list.
	/// </summary>
	/// <remarks>
	/// This class does not invalidate the enumerators when changed except when the
	/// enumerator points to a node that is removed.
	/// </remarks>
	public class DoubleLinkedList
		: ICollection
	{
		private int _count;
		internal Node _head;
		internal Node _tail;

		/// <summary>
		/// Constructs an empty list.
		/// </summary>
		public DoubleLinkedList()
		{
		}

		/// <summary>
		/// Adds an element at the head of the list.
		/// </summary>
		/// <param name="o">The element to be added.</param>
		public void AddHead(object o)
		{
			Node n = new Node();
			n._prev = null;
			if(_head != null)
				_head._prev = n;
			n._next = _head;
			n._data = o;
			_head = n;
			if(_tail == null)
				_tail = n;
			_count++;
		}

		/// <summary>
		/// Adds an element at the back of the list.
		/// </summary>
		/// <param name="o">The element to be added.</param>
		public void AddTail(object o)
		{
			Node n = new Node();
			if(_tail != null)
				_tail._next = n;
			n._prev = _tail;
			n._next = null;
			n._data = o;
			_tail = n;
			if(_head == null)
				_head = n;
			_count++;
		}

		/// <summary>
		/// Gets or sets the first element of the list.
		/// </summary>
		public object Head
		{
			get
			{
				return _head._data;
			}
			set
			{
				_head._data = value;
			}
		}

		/// <summary>
		/// Gets or sets the last element of the list.
		/// </summary>
		public object Tail
		{
			get
			{
				return _tail._data;
			}
			set
			{
				_tail._data = value;
			}
		}

		/// <summary>
		/// Removes the first element of the list.
		/// </summary>
		/// <returns>The data stored at the now-removed head.</returns>
		public object RemoveHead()
		{
			if(_count <= 0)
				throw new InvalidOperationException(
					"Can't remove an element of an empty list");
			if(_head._next != null)
				_head._next._prev = null;
			else
				_tail = null;
			Node n = _head;
			_head = _head._next;
			n._next = null;
			object o = n._data;
			n._data = null;
			n._valid = false;
			_count--;
			return o;
		}

		/// <summary>
		/// Removes the last element of the list.
		/// </summary>
		/// <returns>The data stored at the now-removed tail.</returns>
		public object RemoveTail()
		{
			if(_count <= 0)
				throw new InvalidOperationException(
					"Can't remove an element of an empty list");
			if(_tail._prev != null)
				_tail._prev._next = null;
			else
				_head = null;
			Node n = _tail;
			_tail = _tail._prev;
			n._prev = null;
			object o = n._data;
			n._data = null;
			n._valid = false;
			_count--;
			return o;
		}

		/// <summary>
		/// Removes the element an enumerator points to. Invalidates the enumerator.
		/// </summary>
		/// <param name="i">The enumerator that points to the element that should be removed.
		/// Must be a DoLiLiEnumerator, otherwise the function throws an exception.</param>
		public void RemoveAt(IEnumerator i)
		{
			if(_count <= 0)
				throw new InvalidOperationException(
					"Can't remove an element of an empty list");
			try
			{
				DoLiLiEnumerator e = (DoLiLiEnumerator)i;
				if(e._list != this)
					throw new ArgumentException(
						"Enumerator does not belong to the collection", "i");
				RemoveNode(e._node);
			}
			catch(InvalidCastException e)
			{
				throw new ArgumentException(
					"Enumerator does not belong to the collection", "i", e);
			}
		}

		/// <summary>
		/// Searches and removes a node from the list.
		/// </summary>
		/// <param name="o">The object to remove.</param>
		public void Remove(object o)
		{
			for(Node n = _head; n != null; n = n._next)
			{
				if(n._data == o)
				{
					RemoveNode(n);
					break;
				}
			}
		}

		private void RemoveNode(Node n)
		{
			if(n._next != null)
				n._next._prev = n._prev;
			if(n._prev != null)
				n._prev._next = n._next;
			if(_head == n)
				_head = n._next;
			if(_tail == n)
				_tail = n._prev;
			n._next = null;
			n._prev = null;
			n._data = null;
			n._valid = false;
			_count--;
		}

		#region ICollectionImpl
		/// <summary>
		/// Gets the number of elements in the list.
		/// </summary>
		public int Count
		{
			get
			{
				return _count;
			}
		}

		/// <summary>
		/// Returns true if this list is synchronized (thread-safe).
		/// Always returns false;
		/// </summary>
		public bool IsSynchronized
		{
			get
			{
				return false;
			}
		}

		/// <summary>
		/// Returns an object to synchronize on.
		/// Always returns null.
		/// </summary>
		public object SyncRoot
		{
			get
			{
				return null;
			}
		}

		public void CopyTo(Array array, int index)
		{
			if(array == null)
				throw new ArgumentNullException("array");
			if(index < 0)
				throw new ArgumentOutOfRangeException("index");
			if(array.Rank > 1 || index > array.GetLength(0)
				|| _count > array.GetLength(0)-index)
				throw new ArgumentException();
			// This satisfies the last exception requirement of CopyTo.
			foreach(object o in this)
			{
				array.SetValue(o, index++);
			}
		}
		#endregion

		#region IEnumerableImpl
		/// <summary>
		/// Obtains an enumerator for this list.
		/// </summary>
		/// <returns>An IEnumerator that points to a DoLiLiEnumerator.</returns>
		public IEnumerator GetEnumerator()
		{
			return new DoLiLiEnumerator(this);
		}
		#endregion

		/// <summary>
		/// An enumerator for a double linked list.
		/// </summary>
		public class DoLiLiEnumerator
			: IEnumerator
		{
			internal DoubleLinkedList _list;
			internal Node _node;

			/// <summary>
			/// Constructs a new enumerator for a list.
			/// </summary>
			/// <param name="list">The list to enumerate.</param>
			public DoLiLiEnumerator(DoubleLinkedList list)
			{
				_list = list;
			}

			#region IEnumeratorImpl
			/// <summary>
			/// Gets the element the enumerator points to.
			/// This implementation supports set. This sets the data at the current node.
			/// </summary>
			public object Current
			{
				get
				{
					if(_node == null || !_node._valid)
						throw new InvalidOperationException("Enumerator invalid");
					return _node._data;
				}
				set
				{
					if(_node == null || !_node._valid)
						throw new InvalidOperationException("Enumerator invalid");
					_node._data = value;
				}
			}

			/// <summary>
			/// Advances the enumerator.
			/// </summary>
			/// <returns>true if the enumerator is still valid.</returns>
			public bool MoveNext()
			{
				if(_node == null)
					_node = _list._head;
				else
					_node = _node._next;
				return _node != null;
			}

			/// <summary>
			/// Resets the enumerator to the start of the list.
			/// </summary>
			public void Reset()
			{
				_node = null;
			}
			#endregion
		}
	}
}

[wossname]

Thanks.

1 Since I posted this thread, I've created a DLL in C++ that contains classes for Stack, Queue, Deque (pronounced "deck"). All implemented with linked lists.

At the moment the data part of each list item is just an integer. But say I wanted to use these classes in any future program with any kind of data (new classes fo instance) how would I rewrite the listitem class? Would I just create an interface and have a pointer to it (rather than the integer) and any classes that I want to attach to the list would have to implement that class?

OOP is so funky!

2 If I nullify the pointer to the first item in the list (the head item) will the whole list be free'd up in memory like a chain reaction?

[CornedBee]

1) Do it like I did. Store System.Object references. That's what all existing containers (and the container framework) do.

2) If you remove every reference to the list items from your linked list class, the chain of nodes will be left dangling and eventually will be reclaimed by the GC.

[wossname]

Why references and not pointers? Are references faster?

[CornedBee]

My implementation is C#, so I just used the term reference.

In C++, references and pointers have the same binary representation, so they are exactly equal.

In Managed C++ I think you may not use references.

[wossname]

Nice one, thanks

[PT Exorcist]

Originally posted by wossname
Thanks.

1 Since I posted this thread, I've created a DLL in C++ that contains classes for Stack, Queue, Deque (pronounced "deck"). All implemented with linked lists.

At the moment the data part of each list item is just an integer. But say I wanted to use these classes in any future program with any kind of data (new classes fo instance) how would I rewrite the listitem class? Would I just create an interface and have a pointer to it (rather than the integer) and any classes that I want to attach to the list would have to implement that class?

OOP is so funky!

2 If I nullify the pointer to the first item in the list (the head item) will the whole list be free'd up in memory like a chain reaction?

In the new C# you can have templates so i believe you can make a template for that class

[CornedBee]

Pseudo-templates, like in Java 1.5.