I've implemented a simple linked list in C# using generic T
for values. I did not inherit from any of .Net's fun and helpful classes like IEnumerable<T>
, or IList<T>
:D. This is just after an hours worth of work. I've tested everything and I believe it all works well enough, but before I go on to add more methods, or make the actual data-structure more complex I'm looking for some feedback on what I have. Critiques on everything are welcome, perhaps there is some glaring issue that I have not addressed.
As far as my nodes having a previous and next value, that is because I did intend to have quicker searching iterating backwards through, and some other stuff that is not yet implemented. While right now do use both properties of the node, I know I could avoid it. But I have kept it in and use it because I do plan to implement more stuff later.
This is supposed to emulate the List class. I've called mine Jist to not confuse anyone. I also have considered taking away the JNode
constructor, because all the properties are public anyway, but I've decided against that, because I don't want any accidentally null
values... while default
values are fine, I don't want any in there by accident.
class JNode<T>
{
public T Value { get; set; }
public JNode<T> Next { get; set; }
public JNode<T> Previous { get; set; }
public JNode(T value) { Value = value; }
}
public class Jist<T>
{
#region Private Members
private JNode<T> _first;
private JNode<T> _last;
#endregion
#region Public Properties
public UInt64 Count { get; private set; }
public T this[UInt64 index]
{
get { return NodeAtIndex(index).Value; }
set { NodeAtIndex(index).Value = value; }
}
#endregion
#region Constructor
public Jist()
{
Count = 0;
_first = new JNode<T>(default(T));
_last = new JNode<T>(default(T));
LinkNodes(_first, _last);
}
#endregion
#region Public Methods
public void Add(T value)
{
InsertBeforeNode(_last, value);
}
public void Clear()
{
LinkNodes(_first, _last);
Count = 0;
}
public bool Contains(T value)
{
return FirstNodeWithValue(value) != null;
}
public void Insert(T value, UInt64 index)
{
if (index > Count)
throw new IndexOutOfRangeException("Index(" + index + ") cannot be greater than Count(" + Count + ")");
InsertBeforeNode(NodeAtIndex(index), value);
}
public UInt64? IndexOf(T value)
{
return IndexOfFirstNodeWithValue(value);
}
public bool Remove(T value)
{
var node = FirstNodeWithValue(value);
if (node != null)
LinkNodes(node.Previous, node.Next);
return node != null;
}
#endregion
#region Private Methods
private void InsertBeforeNode(JNode<T> node, T value)
{
if (Count == UInt64.MaxValue)
throw new ArgumentException("List can not grow larger than " + UInt64.MaxValue + " nodes large.");
var nn = new JNode<T>(value);
LinkNodes(node.Previous, nn);
LinkNodes(nn, node);
Count++;
}
private void LinkNodes(JNode<T> first, JNode<T> second)
{
first.Next = second;
second.Previous = first;
}
private JNode<T> NodeAtIndex(UInt64 index)
{
if (index > Count - 1)
throw new IndexOutOfRangeException("Index(" + index + ") cannot be greater than Count(" + Count + " - 1)");
JNode<T> node = _first.Next;
for (UInt64 i = 0; i < index; i++)
node = node.Next;
return node;
}
private JNode<T> FirstNodeWithValue(T value)
{
JNode<T> node = _first.Next;
for (UInt64 i = 0; i < Count; i++)
if (EqualityComparer<T>.Default.Equals(node.Value, value))
return node;
else
node = node.Next;
return null;
}
private UInt64? IndexOfFirstNodeWithValue(T value)
{
UInt64 i = 0;
for (JNode<T> node = _first.Next; !EqualityComparer<T>.Default.Equals(node.Value, value); node = node.Next)
if (i >= Count) return null;
else i++;
return i;
}
#endregion
}
LinkedList
andLinkedListNode
if my goal was to not be confusing. Otherwise it sounds like something Java related. A namespace will already keep it apart from anything that ends up having the same name. \$\endgroup\$Jist
implies nothing, even that it is a list. Naming itLinkedList
may create a collision, however that's less of a code quality issue than a bad name. You know not only that it is a list, but what kind and presumably how to use it. \$\endgroup\$IndexOfFirstNodeWithValue
:) \$\endgroup\$