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
IEnumberableto 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;
}
}
Listwill be faster than both the built inLinkedListand 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. \$\endgroup\$