Implementing a singly LinkedList and IList interface

Question

I have implemented a LinkedList in C#. What would you change/make better? What naming conventions are misused? What would you add? Some of my ideas are to make it thread-safe.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TestIt.DataStructures
{
 public class MyLinkedList<T> : IList<T>
 {
 private int size;
 private MyLinkedListNode<T> head;
 public long Size()
 {
 return size;
 }
 public void Add(T nodeValue)
 {
 Add(new MyLinkedListNode<T>(nodeValue));
 }
 public void Add(MyLinkedListNode<T> newItem)
 {
 if (size == 0)
 {
 head = newItem;
 }
 else
 {
 var last = head;
 while (last.Next != null) { last = last.Next; }
 last.Next = newItem;
 newItem.Prev = last;
 }
 size++;
 }
 public MyLinkedListNode<T> Get(long index)
 {
 if (index > size)
 {
 throw new IndexOutOfRangeException(String.Format("List size is {0} but the index {1}", size, index));
 }
 long c = 0;
 var curr = head;
 while (c != index) { curr = curr.Next; c++; }
 return curr;
 }
 public bool Remove(long index)
 {
 if (index > size)
 {
 throw new IndexOutOfRangeException(String.Format("List size is {0} but the index {1}", size, index));
 }
 if (size == 0) return false;
 long c = 0;
 var curr = head;
 while (curr.Next != null && c < index) { curr = curr.Next; c++; }
 if (curr.Prev == null && curr.Next == null)
 {
 curr = null;
 head = null;
 }
 else if (curr.Prev == null) { curr.Next.Prev = null; head = curr.Next; curr = null; }
 else if (curr.Next == null) { curr.Prev.Next = null; curr = null; }
 else
 {
 curr.Prev.Next = curr.Next;
 curr.Next.Prev = curr.Prev;
 curr = null;
 }
 size--;
 return true;
 }
 public bool Remove(MyLinkedListNode<T> node)
 {
 if (size == 0)
 {
 return false;
 }
 var curr = head;
 while (curr != null && curr != node) { curr = curr.Next; }
 if (curr == null) { return false; }
 curr.Next.Prev = curr.Prev;
 curr.Prev.Next = curr.Next;
 curr = null;
 size--;
 return true;
 }
 public int IndexOf(T item)
 {
 if (item == null)
 {
 return -1;
 }
 int index = 0;
 var curr = head;
 while (curr != null)
 {
 if (curr.Value.Equals(item))
 {
 return index;
 }
 curr = curr.Next;
 index++;
 }
 return -1;
 }
 public void Insert(int index, T item)
 {
 if (index > size + 1)
 {
 throw new Exception("Index if out of range of the linked list");
 }
 var curr = head;
 var i = 0;
 if (index == i)
 {
 var newNode = new MyLinkedListNode<T>(item);
 newNode.Next = curr;
 head = newNode;
 size++;
 return;
 }
 curr = curr.Next;
 i++;
 while (curr != null)
 {
 if (i == index)
 {
 var newNode = new MyLinkedListNode<T>(item);
 newNode.Next = curr.Next;
 curr.Next = newNode;
 size++;
 return;
 }
 curr = curr.Next;
 i++;
 }
 }
 public void RemoveAt(int index)
 {
 Remove(index);
 }
 public T this[int index]
 {
 get
 {
 if (size < index - 1)
 {
 throw new IndexOutOfRangeException();
 }
 var curr = head;
 int i = 0;
 while (curr != null)
 {
 if (i == index)
 {
 return curr.Value;
 }
 curr = curr.Next;
 i++;
 }
 return default(T);
 }
 set
 {
 if (size < index - 1)
 {
 var curr = head;
 int i = 0;
 while (curr != null)
 {
 if (i == index)
 {
 curr.Value = value;
 return;
 }
 curr = curr.Next;
 i++;
 }
 }
 }
 }
 public void Clear()
 {
 size = 0;
 head = null;
 }
 public bool Contains(T item)
 {
 if (size == 0)
 {
 return false;
 }
 var curr = head;
 while (curr != null)
 {
 if (curr.Value.Equals(item))
 {
 return true;
 }
 curr = curr.Next;
 }
 return false;
 }
 public void CopyTo(T[] array, int arrayIndex)
 {
 if (size == 0)
 {
 return;
 }
 var curr = head;
 while (curr != null)
 {
 array[arrayIndex] = curr.Value;
 curr = curr.Next;
 arrayIndex++;
 }
 }
 public int Count
 {
 get { return (int)size; }
 }
 public bool IsReadOnly
 {
 get { return false; }
 }
 public bool Remove(T item)
 {
 return Remove(new MyLinkedListNode<T>(item));
 }
 public IEnumerator<T> GetEnumerator()
 {
 var curr = head;
 while (curr != null)
 {
 yield return curr.Value;
 curr = curr.Next;
 }
 }
 IEnumerator IEnumerable.GetEnumerator()
 {
 return GetEnumerator();
 }
 }
 public class MyLinkedListNode<T> : IComparable<T>
 {
 public T Value { get; set; }
 public MyLinkedListNode<T> Next { get; set; }
 public MyLinkedListNode<T> Prev { get; set; }
 public MyLinkedListNode(T value)
 {
 this.Value = value;
 }
 public int CompareTo(T other)
 {
 throw new NotImplementedException();
 }
 }
}

Answer 1

Possible problems

• MyLinkedListNode<T> Get(long index) passing negative index will lead to a NullReferenceException but should lead to an ArgumentOutOfRangeException.

• Calling CopyTo(T[] array, int arrayIndex) with array == null will lead to an IndexOutOfRangeException but should lead to an ArgumentNullException.

• Calling CopyTo(T[] array, int arrayIndex) with arrayIndex >= array.Length will lead to an IndexOutOfRangeException but should lead to an ArgumentOutOfRangeException.

• The guard condition in the this getter should be changed from

   if (size < index - 1)
   {
   throw new IndexOutOfRangeException();
   }
  

  to this

  if (size-1 < index)
  {
   throw new ArgumentOutOfRangeException();
  } 
  

  otherwise with size == 1 calling with index == 1 or index == 2 would succeed.

• You should change every guard condition which states

  if (index > size) 
  

  to

  if (index >= size) 
  

• Insert(int index, T item)

  here you need to change the guard condition also and you should throw an ArgumentOutOfRangeException instead of a System.Exception.

Nitpicking

public int Count
{
 get { return (int)size; }
} 

The cast isn't necessary.

Update based on comment

public void CopyTo(T[] array, int arrayIndex)
{
 if (size == 0)
 {
 return;
 }
 var curr = head;
 while (curr != null)
 {
 array[arrayIndex] = curr.Value;
 curr = curr.Next;
 arrayIndex++;
 }
}

In the way you have coded the CopyTo() method, you are using the arrayIndex as the indexer of the passed in T[] array. This is differenet than the Array.CopyTo() implementation of the NET framework.

In the NET implementation arrayIndex would be the starting index of the source array. For the NET CopyTo() the arrayIndex needs to be < sourcearray.Length. If you had the intention that your method behaves like the Array.CopyTo() method you would need to rewrite it like

public void CopyTo(T[] array, int arrayIndex)
{
 if (size == 0 || arrayIndex >= size)
 {
 return;
 }
 var current = Get(arrayIndex);
 int destinationCounter = 0;
 int arrayLength = array.Length;
 while (current!= null && destinationCounter < arrayLength)
 {
 array[destinationCounter] = current.Value;
 current= current.Next;
 destinationCounter++;
 }
}

• levi: thanks for response. Re-consider your third point: arrayIndex >= array.Length. Would you agree that if(arrayIndex + Count >= array.Length) should throw ArgumentOutOfRangeException instead of arrayIndex >= array.Length?
• Heslacher: No, I won't agree. See the updated answer.

Answer 2

• You could make MyLinkedListNode private nested class of MyLinedList. It is implementation detail, so it shouldn't be visible to the end user. Making it nested you also hide it from other top-level classes of your module (assembly). Invisible things can't be broken.

• You could also create two or three private helper methods. F.e. Remove(int), Insert(int, T), this[int] all are implements the loop to find i-th element. Do not repeat yourself, avoid duplicate the code. It simplify both testing and maintain of the code.

You can make the code more uniform. These two statements looks completely different:

if (size == 0)
{
 return false;
}

and

while (curr != null && curr != node) { curr = curr.Next; }

Uniform code easier to read.

Otherwise, it's good code: readable, understandable.

• janos: He certainly could. Buy why should he? Your answer would be much better if you included some justification for your recommendations.
• levi: @MarkShevchenko, thanks for your input. Don't you think users (I mean class users) should be able to create instance of MyLinkedListNode? - This is the reason of leaving the node class public instead of nested private.
• Mark Shevchenko: It seems that none of public methods has parameters or return values of type MyLinkedListNode. It just means that users doesn't need this type.
• levi: public bool Add(MyLinkedListNode<T> node) public bool Remove(MyLinkedListNode<T> node) These two have... Do you think it's better to change the arguments just to T?
• Mark Shevchenko: You can declare any method as a public, but disclose details of the implementation considered VERY BAD IDEA. As a rule, it's enough to open methods of IList<T> only. Since IList<T> has Add(T) and Remove(T) you should implement them anyway. Add(MyLinkedListNode<T>) may be useful to simplify the implementation, so you can make it private and call from your other methods only.

Answer 3

I would make Size a read-only property, rather than a method that returns a backing field. This requires some small refactoring, but the main change is removing the int size and changing the Size() method to a read-only property:

public long Size { get; private set; }

In your Add() method, instead of walking the list, you could just use the Get() method to grab the last node. This reduces some code duplication.

public void Add(MyLinkedListNode<T> newItem)
{
 if (Size == 0)
 {
 head = newItem;
 }
 else
 {
 var last = Get(Size - 1);
 last.Next = newItem;
 newItem.Prev = last;
 }
 Size++;
}

In your Get method, you should probably not allow negative numbers. You also need to change your comparison between index and Size to be if (index >= Size). Also, a small nit-pick, I would use a for rather than a while, since your condition and counting variable is defined, checked, and incremented in one place.

public MyLinkedListNode<T> Get(long index)
{
 if (index < 0) throw new IndexOutOfRangeException("Index cannot be negative");
 if (index >= Size)
 throw new IndexOutOfRangeException(
 String.Format("List Size is {0} but the index {1}", Size, index)); 
 var curr = head;
 for (int i = 0; i < index; i++)
 {
 curr = curr.Next;
 }
 return curr;
}

You might also consider adding another private Remove function that does the legwork of repointing the Prev and Next properties to reduce code duplication. Note I'm also calling Clearr() if both Prev and Next are null, since this can only be the head in that case:

private void RemoveNode(MyLinkedListNode<T> node)
{
 if (node == null) return;
 if (node.Prev == null && node.Next == null) 
 { 
 Clear();
 return;
 }
 if (node.Prev != null) node.Prev.Next = node.Next;
 if (node.Next != null) node.Next.Prev = node.Prev;
 Size--;
}

Also, in your Remove() method, you need to change your comparison between index and Size to be if (index >= Size). You could also simplify the code by using your Get() method. I don't see how this can fail, so I'm returning void:

public void Remove(long index)
{
 if (index < 0) throw new IndexOutOfRangeException("Index cannot be negative");
 if (index >= Size)
 throw new IndexOutOfRangeException(
 String.Format("List Size is {0} but the index {1}", Size, index)); 
 var itemToRemove = Get(index);
 RemoveNode(itemToRemove);
}

Now in your other Remove function we can again take advantage of our private RemoveNode method. You can also simplify the code by using a for loop which will initialize, validate, and increment your nodes in one place. Also, this one could fail (without throwing) if the node doesn't exist, so it returns a bool:

public bool Remove(MyLinkedListNode<T> node)
{
 var foundNode = false;
 for (var curr = head; curr != null; curr = curr.Next)
 {
 if (curr == node)
 {
 foundNode = true;
 break;
 }
 }
 if (foundNode) RemoveNode(node);
 return foundNode;
}

For IndexOf the only change I would make is to use a for loop because I think it looks cleaner:

public int IndexOf(T item)
{
 if (item == null) return -1;
 int index = 0;
 for (var curr = head; curr != null; curr = curr.Next)
 {
 if (curr.Value.Equals(item))
 {
 return index;
 }
 index++;
 }
 return -1;
}

For the Insert method, you should check for a negative index. Also, I would allow someone to specify Size as an index (which is one more than the last index), and just call the Add() method in that case. Otherwise, the code can be simplified greatly by using the Get() method:

public void Insert(int index, T item)
{
 if (index > Size || index < 0)
 {
 throw new Exception("Index if out of range of the linked list");
 }
 var itemToInsert = new MyLinkedListNode<T>(item);
 // Inserting at the end is the same as Adding...
 if (index == Size)
 {
 Add(itemToInsert);
 return;
 }
 var existingNodeAtIndex = Get(index);
 itemToInsert.Prev = existingNodeAtIndex.Prev;
 itemToInsert.Next = existingNodeAtIndex;
 existingNodeAtIndex.Prev = itemToInsert;
}

Next, I think the index check in your this implementation needs to be changed. After that, I don't see why you couldn't just call your Get() methods here? The error handling in those methods should do, I think.

public T this[int index]
{
 get
 {
 return Get(index).Value;
 }
 set
 {
 Get(index).Value = value;
 }
}

Finally, your Contains() method can use the already implemented IndexOf() method:

public bool Contains(T item)
{
 return IndexOf(item) >= 0;
}

• littlerufe: Just finished some edits, should be done now!