Skip to content

Instantly share code, notes, and snippets.

@erdomke
Created March 15, 2017 18:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save erdomke/3cff125596a4cc359820c0ed8a72360a to your computer and use it in GitHub Desktop.
Save erdomke/3cff125596a4cc359820c0ed8a72360a to your computer and use it in GitHub Desktop.
Custom linked list implementation which avoids extra data classes
public interface ILink<T> where T : ILink<T>
{
string Term { get; }
T Next { get; set; }
}
static class LinkedListOps
{
public static void Add<T>(ref T lastLink, T newLink) where T : class, ILink<T>
{
if (lastLink == null)
{
newLink.Next = newLink;
}
else
{
newLink.Next = lastLink.Next;
lastLink.Next = newLink;
}
lastLink = newLink;
}
public static IEnumerable<T> Enumerate<T>(T lastLink) where T : class, ILink<T>
{
var curr = lastLink;
if (curr == null)
yield break;
do
{
curr = curr.Next;
yield return curr;
}
while (curr != lastLink);
}
public static T Find<T>(T lastLink, string name) where T : class, ILink<T>
{
if (lastLink == null)
return null;
var curr = lastLink;
if (string.Equals(curr.Term, name, StringComparison.Ordinal))
return curr;
curr = curr.Next;
while (curr != lastLink)
{
if (string.Equals(curr.Term, name, StringComparison.Ordinal))
return curr;
curr = curr.Next;
}
return null;
}
public static IEnumerable<T> FindAll<T>(T lastLink, string name) where T : class, ILink<T>
{
if (lastLink == null)
yield break;
var curr = lastLink;
do
{
curr = curr.Next;
if (string.Equals(curr.Term, name, StringComparison.Ordinal))
yield return curr;
}
while (curr != lastLink);
}
public static void Remove<T>(ref T lastLink, T removeLink) where T : class, ILink<T>
{
if (lastLink == null
|| (lastLink == removeLink && removeLink.Next == removeLink))
lastLink = null;
T prev;
var curr = lastLink;
do
{
prev = curr;
curr = curr.Next;
if (curr == removeLink)
{
prev.Next = curr.Next;
lastLink = curr == lastLink ? prev : lastLink;
}
}
while (curr != lastLink);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment