Linked List in C#

Question

I was searching for a implementation of a Linked List with the same power as a native List.

I wanted functionality closer to a List. The System.Collections.Generic.LinkedList misses some methods I'm used to work with, like Add Sort or access by index mylist[0]

I didn't find one so I made one of my own:

• I added the same constructors as List
• I used a merge sort which should be the most performant for this case
• I added IEnumberable to be able to use the power of Linq
• I added all native methods of a List

I'm searching for mistakes, performance improvements or missing functionality.

Note: This is not about a circular or doubly linked list; it's just about a singly linked list.

public class Node<T>
{
 public T data;
 public Node<T> next;
}
public class MyLinkedList<T> : IEnumerable<T>, System.Collections.IEnumerable
{
 private Node<T> _headNode;
 private int _count;
 public int Count { get { { return _count; } } }
 private IEnumerable<Node<T>> Nodes
 {
 get
 {
 Node<T> node = _headNode;
 while (node != null)
 {
 yield return node;
 node = node.next;
 }
 }
 }
 private Node<T> Pop()
 {
 Node<T> tResult = null;
 if (_headNode != null)
 {
 tResult = _headNode;
 _headNode = _headNode.next;
 _count--;
 }
 return tResult;
 }
 private void Push(Node<T> item)
 {
 item.next = _headNode;
 _headNode = item;
 _count++;
 }
 private Node<T> NodeAt(int index)
 {
 if (index < 0 || index + 1 > _count)
 {
 throw new IndexOutOfRangeException("Index");
 }
 int counter = 0;
 foreach (Node<T> item in Nodes)
 {
 if (counter == index)
 {
 return item;
 }
 counter++;
 }
 return null;
 }
 public MyLinkedList()
 {
 _headNode = null;
 _count = 0;
 }
 public MyLinkedList(IEnumerable<T> Items)
 {
 foreach (T item in Items)
 {
 Add(item);
 }
 }
 public void ForEach(Action<T> action)
 {
 foreach (Node<T> item in Nodes)
 {
 action(item.data);
 }
 }
 public void AddRange(IEnumerable<T> Items)
 {
 foreach (T item in Items)
 {
 Add(item);
 }
 }
 public void AddRange(params T[] Items)
 {
 foreach (T item in Items)
 {
 Add(item);
 }
 }
 public T this[int index]
 {
 get { return NodeAt(index).data; }
 set { NodeAt(index).data = value; }
 }
 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
 {
 return this.GetEnumerator();
 }
 public IEnumerator<T> GetEnumerator()
 {
 foreach (Node<T> item in Nodes)
 {
 yield return item.data;
 }
 }
 public bool Exists(T value)
 {
 foreach (Node<T> item in Nodes)
 {
 if (Comparer<T>.Default.Compare(value, item.data) == 0)
 {
 return true;
 }
 }
 return false;
 }
 public void Clear()
 {
 _headNode = null;
 _count = 0;
 }
 public void Shuffle()
 {
 if (_headNode != null)
 {
 Random rRand = new Random();
 T[] aResult = new T[_count];
 int i = 0;
 foreach (Node<T> nItem in Nodes)
 {
 int j = rRand.Next(i + 1);
 if (i != j)
 {
 aResult[i] = aResult[j];
 }
 aResult[j] = nItem.data;
 i++;
 }
 this.Clear();
 this.AddRange(aResult);
 }
 }
 public void Sort()
 {
 _headNode = MergeSortSub(_headNode);
 }
 private Node<T> MergeSortSub(Node<T> nHead)
 {
 if (nHead == null || nHead.next == null) { return nHead; }
 Node<T> nSeeker = nHead;
 Node<T> nMiddle = nSeeker;
 while (nSeeker.next != null && nSeeker.next.next != null)
 {
 nMiddle = nMiddle.next;
 nSeeker = nSeeker.next.next;
 }
 Node<T> sHalf = nMiddle.next;
 nMiddle.next = null;
 Node<T> nFirst = MergeSortSub(nHead);
 Node<T> nSecond = MergeSortSub(sHalf);
 Node<T> nResult = new Node<T>();
 Node<T> nCurrent = nResult;
 while (nFirst != null && nSecond != null)
 {
 IComparer<T> comparer = Comparer<T>.Default;
 if (comparer.Compare(nFirst.data, nSecond.data) < 1)
 {
 nCurrent.next = nFirst;
 nFirst = nFirst.next;
 }
 else
 {
 nCurrent.next = nSecond;
 nSecond = nSecond.next;
 }
 nCurrent = nCurrent.next;
 }
 nCurrent.next = (nFirst == null) ? nSecond : nFirst;
 return nResult.next;
 }
 public void Add(T item)
 {
 Node<T> NewNode = new Node<T>() { data = item, next = _headNode };
 _headNode = NewNode;
 _count++;
 }
 public IEnumerable<int> AllIndexesOf(T Value)
 {
 int IndexCount = 0;
 foreach (Node<T> item in Nodes)
 {
 if (Comparer<T>.Default.Compare(item.data, Value) == 0)
 {
 yield return IndexCount;
 }
 IndexCount++;
 }
 }
 public int IndexOf(T Value)
 {
 IEnumerator<int> eN = AllIndexesOf(Value).GetEnumerator();
 if (eN.MoveNext())
 {
 return eN.Current;
 }
 return -1;
 }
 public int LastIndexOf(T Value)
 {
 IEnumerator<int> eN = AllIndexesOf(Value).GetEnumerator();
 int Result = -1;
 while (eN.MoveNext())
 {
 Result = eN.Current;
 }
 return Result;
 }
 public void RemoveAll(Func<T, bool> match)
 {
 while (_headNode != null && match(_headNode.data)) // head node
 {
 _headNode = _headNode.next;
 _count--;
 }
 if (_headNode != null)
 {
 Node<T> nTemp = _headNode;
 while (nTemp.next != null)// other nodes
 {
 if (match(nTemp.next.data))
 {
 nTemp.next = nTemp.next.next;
 _count--;
 }
 else
 {
 nTemp = nTemp.next;
 }
 }
 }
 }
 public IEnumerable<T> Find(Predicate<T> match)
 {
 foreach (Node<T> item in Nodes)
 {
 if (match(item.data))
 {
 yield return item.data;
 }
 }
 }
 public void Distinct()
 {
 HashSet<T> uniques = new HashSet<T>();
 Node<T> nTemp = _headNode;
 if (nTemp != null)
 {
 uniques.Add(_headNode.data);
 while (nTemp.next != null)
 {
 if (!uniques.Add(nTemp.next.data))
 {
 nTemp.next = nTemp.next.next;
 _count--;
 }
 else
 {
 nTemp = nTemp.next;
 }
 }
 }
 }
 public void Reverse()
 {
 Node<T> nCurrent = _headNode;
 Node<T> nBack = null;
 while (nCurrent != null)
 {
 Node<T> nTemp = nCurrent.next;
 nCurrent.next = nBack;
 nBack = nCurrent;
 nCurrent = nTemp;
 }
 _headNode = nBack;
 }
 public void RemoveFirst()
 {
 if (_headNode != null)
 {
 _headNode = _headNode.next;
 _count--;
 }
 }
 public void RemoveLast()
 {
 if (_headNode != null)
 {
 if (_headNode.next == null)
 {
 _headNode = null;
 }
 else
 {
 NodeAt(Count - 2).next = null;
 }
 _count--;
 }
 }
 public void AddLast(T item)
 {
 Node<T> NewNode = new Node<T>() { data = item, next = null };
 if (_headNode == null)
 {
 _headNode = NewNode;
 }
 else
 {
 NodeAt(Count - 1).next = NewNode;
 }
 _count++;
 }
 public void Insert(T item, int index)
 {
 if (index < 0 || index + 1 > _count)
 {
 throw new IndexOutOfRangeException("Index");
 }
 Node<T> NewNode = new Node<T>() { data = item, next = null };
 if (index == 0)
 {
 NewNode.next = _headNode;
 _headNode = NewNode;
 }
 else
 {
 NewNode.next = NodeAt(index - 1).next;
 NodeAt(index - 1).next = NewNode;
 }
 _count++;
 }
 public void RemoveAt(int index)
 {
 if (index < 0 || index + 1 > _count)
 {
 throw new IndexOutOfRangeException("Index");
 }
 if (index == 0)
 {
 _headNode = _headNode.next;
 }
 else
 {
 Node<T> temp = NodeAt(index - 1);
 temp.next = temp.next.next;
 }
 _count--;
 }
 public void RemoveRange(int index, int count)
 {
 if (index < 0 || index + count > _count)
 {
 throw new IndexOutOfRangeException("Index");
 }
 if (index == 0)
 {
 for (int i = 0; i < count; i++)
 {
 _headNode = _headNode.next;
 }
 }
 else
 {
 Node<T> nStart = NodeAt(index - 1);
 for (int i = 0; i < count; i++)
 {
 nStart.next = nStart.next == null ? null : nStart.next.next;
 }
 }
 _count -= count;
 }
}

• Mark Rogers: You can probably add extension functions for some of those desired methods. Generally developers avoid re-implementing a built-in .net feature, unless there is a justifiable reason, which I don't want to be judgy, but you can probably avoid reimplementation in your case.
• Pharap: Out of interest, List will be faster than both the built in LinkedList and the one you're making. Linked lists are naturally slower in modern computers because of issues with caching and memory locality. And a doubly linked list is still a linked list, what you're talking about is a singly linked list, many people take 'linked list' on its own to refer to doubly linked list because they're more common and more useful.
• Pieter Witvoet: Tolani Jaiye-Tikolo's answer made me wonder: why treat a linked list as a 'normal' list without taking advantage of its benefits? Doesn't that give you the worst of both worlds? Poor indexing performance and poor insertion performance?
• fubo: @PieterWitvoet I think there is no reason to use a Linked List productive. The performance is worse in almost every case - I've benchmaked a lot and the only method that's faster compared to a List: inserting items always at the first possition :)

Answer 1

Just a few quick remarks:

• Creating a linked list from another enumerable stores items in reverse order. That's probably not what most people would expect. Note that System.Collections.Generic.LinkedList does preserve the original order.
• A similar case can be made for Add: it adds items to the front. People familiar with List<T> would expect it to add at the end. Note that LinkedList explicitly uses AddFirst and AddLast, likely to prevent such confusion. Granted, not all collections are ordered, but if you do want to stick to this behavior, then at least document it.
• Implement ICollection(<T>) and IList(<T>) while you're at it. You already implemented most of their functionality anyway (sometimes with different method names, or methods with different argument order).
• Keeping track of the tail node allows you to improve the performance of adding items at the end (at the expense of making removing and inserting nodes a bit more complicated).
• There are several methods that don't really need to be member methods, such as Find, Distinct and Reverse. Linq already provides extension methods for these (using mostly the same names, except that Find is called Where).
• The same can be said for ForEach: it can easily be implemented as an extension method, which would make it available for everything that implements IEnumerable(<T>). Or you could just use foreach.
• Some methods appear to be unused, such as Pop and Push.

• Bryce Wagner: Find and Distinct are going to behave similar to the Linq version, but "Reverse()" is actually reversing the list itself, and it avoids the temporary storage that a generic "Reverse()" method requires over an IEnumerable<>

Answer 2

I'd like to quickly point to one huge problem with the current implementation.

Your linked list uses extensively the NodeAt method which is O(n). The AddLast in the original implementation is however O(1). This could be a real bottle neck.

---

In a comment you say that:

The System.Collections.Generic.LinkedList misses some methods i'm used to work with, like Add Sort or access by index mylist[0]

• The LinkeList's Add method is AddLast
• You can sort the items with OrderBy
• You can access elements by index with ElementAt (and it would be as fast or rather as slow as your implementation)

For example:

var foo = new LinkedList<string>(new[] { "z", "b", "a", "c" });
var fooSorted = new LinkedList<string>(foo.OrderBy(x => x));
var nthFoo = foo.ElementAt(2);

The sorting and returning a new linked list could be an extension too.

• fubo: O(1) isn't possible with a Linked List. I decided knowingly not to implement a circular or doulby linked list.
• t3chb0t: @fubo LinkedList<T>.AddLast Method (T) This method is an O(1) operation. like a few others that make the linked list so useful and fast.
• Random832: @fubo Why? LinkedList<T> is implemented as a circular doubly linked list, which allows operations on the last node to be O(1).
• fubo: @Random832 because this is about the heck of implementing a basic Linked List. I know about performance issues compared to a Listand I know my Linked List is slower in almost every case.

Answer 3

• Naming: local variables should be named using camelCase. NewNode => newNode.

• Some of the methods can be shortened by using LINQ. For example:

  public bool Exists(T value)
  {
   return Nodes.Any(node => Comparer<T>.Default.Compare(value, node.data) == 0);
  }
  

  Also, if your goal is to mimic IList<T> API then you might as well use the same method names: Contains instead of Exists.

• If you are creating a replacement for default LinkedList I would expect it to at least implement the same interfaces:

   LinkedList<T> : ICollection<T>, IEnumerable<T>, 
   IEnumerable, ICollection, IReadOnlyCollection<T>, ISerializable, 
   IDeserializationCallback
  

  You might also want to implement IList<T>. Your linked list also lacks some of the most basic functions, such as adding new elements to the back.

• All things considered, I don't think your class is very useful. If you need to access items by index often, then you should use regular List<T>, period. Regular list is not that slow when it comes to adding items, but it is a lot faster, when it comes to accessing items by index. If you need to get item by index once in while though, you should just create an extension method for regular linked list:

  public static T ElementAt<T>(this LinkedList<T> list, int index)
  {
   //throw "index out of range" exceptions, if needed
   return list.Skip(index).FirstOrDefault();
  }
  

  And be done with it. EDIT: oh, mr. t3chb0t is right. I completely forgot, that LINQ already has ElementAt method. So you don't even have to implement it yourself. Even better.

Answer 4

In addition to what other reviewers have identified.

• Amend your constructor: you should only trying adding items from a collection once the collection is not null.E,g doing the below will throw a NullReferenceException

 MyLinkedList<string> myLinkedList = new MyLinkedList<string>(null);
 Console.WriteLine(myLinkedList.Count);

Rather you should be throwing ArgumentNullException. For instance

 public MyLinkedList(IEnumerable<T> Items)
 {
 if (Items == null)
 {
 throw new ArgumentNullException(nameof(Items));
 }
 foreach (T item in Items)
 {
 Add(item);
 }
 }

• There is so much confusion in your implementation e.g Find . From my perspective Find should be returning a Node rather than IEnumerable<T> hence it should be used in the NodeAt method. In general, the C# definition for Find identifies based on a parameter called value which is the data in your Node class e.g

 public LinkedListNode<T> Find(T value)
 {
 // finds node and returns node
 return null;
 }

Since there is no dependency on your Find method, it can be extended to find a node based on indexing. Below is a snippet

 private Node<T> NodeAt(int index)
 {
 if (index < 0 || index + 1 > _count)
 {
 throw new IndexOutOfRangeException("Index");
 }
 Node<T> foundNode = Nodes.Find(index);
 // return foundNode
 return null;
 }
 public Node<T> Find(T item)
 {
 Node<T> node = _headNode;
 while (node != _headNode)
 {
 // iteratively assign node to the next item and compare the data
 }
 return null;
 }

• When you've two methods doing the same thing you should be worried - DRY . This has happened with the two AddRange methods. An Array by default has a fixed size and params allows you to dynamic add a variable number of items. This is equal to using an ArrayList in C#. If I may remind you again ArrayList implements the IEnumerable interface which makes the second method pretty redundant.

• Pieter Witvoet: Find should not return a node - nodes are an internal implementation detail, and returning one would allow a caller to mess with it. Taking a predicate and returning a value is consistent with other Find methods. The only issue is that it's called Find instead of FindAll.
• Tolani: you maybe right.. In the context of a LinkedList implemetation the Find does return a Node. Taking a predicate is also a good approach to this. It willl also be helpful if OP used a good naming Convention FindAll instead of Find.
• Pieter Witvoet: You're right, LinkedList<T>.Find returns a node (I was only looking at List<T>.Find and Array.Find). But LinkedList<T> also offers methods that accept nodes as arguments, so they're part of the public 'interface', which is not the case with the OP's code. Exposing and using nodes like that looks like a better design - it forces you to take the characteristics of a linked list into account (e.g. no cheap random access).

Answer 5

Before I add additional points I'd like to emphasise some of the things others have brought up. Particularly that wanting to index a linked list is never a good idea, and that all local variables and parameters should use camel case instead of pascal case.

• There is no need to use the bare enumerator in IndexOf and LastIndexOf, you should use a foreach instead. e.g

  public int IndexOf(T Value)
  {
   foreach (var n in AllIndexesOf(Value).GetEnumerator())
   {
   return n;
   }
   return -1;
  }
  

• Node deserves its own constructor, not just a default one. Also its fields should not be public because it means people using your class can start fiddling with the internals of the list by assigning to the node's fields. Instead you should hide them to everything but your LinkedList and give Node<T> some public get-only properties. The best ways to hide the fields from outside code would probably be to make them internal instead of public.

• Stylistically Nodes should be a method instead of a property because properties aren't really meant to be used like that.
• People might try to disagree with me here, but the preferred plural of index in a technical setting (e.g. computer science) is indices. AllIndexesOf should be AllIndicesOf, and even then the All part is debatable since it's heavily implied. If I am asking for the indices of something I'd be pretty annoyed if some got left out unless I had specified a reason to leave them out.
• A lot of your methods look like they should be extension methods such as Shuffle and Find(Predicate<T> match). The Enumerable extensions in Linq actually provide Find for you, except it's called Where.
• The method RemoveAll should ideally be called RemoveWhere given its predicate-based nature. Also the fact it uses a Func<T, bool> instead of a Predicate<T> find is an issue. When it comes to Predicate<T> and Func<T, bool> you should ideally choose one and stick to it.
• I'm not entirely sure how good your shuffle algorithm is, but I'm willing to bet it's not as good as it could be. I suggest using an implementation of the Fisher-Yates Shuffle to ensure a good level of randomness.
• Lastly, AddRange(params T[] Items) could be rerouted to use AddRange(IEnumerable<T> Items) by using a cast.