Skip to content

Instantly share code, notes, and snippets.

@frankbryce
Last active May 5, 2016 19:44
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 frankbryce/dc62b1288cba997acaa00c37b924468c to your computer and use it in GitHub Desktop.
Save frankbryce/dc62b1288cba997acaa00c37b924468c to your computer and use it in GitHub Desktop.
public class DoublyLinkedList<T> : ICloneable, IEnumerable where T : ICloneable
{
private class Node<U>
{
public U Value;
public Node<U> Next;
public Node<U> Prev;
public Node(U value, Node<U> next, Node<U> prev)
{
Value = value;
Next = next;
Prev = prev;
}
/// <summary>
/// Adds a node after this node, then returns the newly created node
/// </summary>
/// <param name="value">value to go into the node</param>
/// <returns>the newly created Node object</returns>
public Node<U> AddNodeAfter(U value)
{
var newNode = new Node<U>(value, this.Next, this);
Next = newNode;
return newNode;
}
/// <summary>
/// Adds a node before this node, then returns the newly created node
/// </summary>
/// <param name="value">value to go into the node</param>
/// <returns>the newly created Node object</returns>
public Node<U> AddNodeBefore(U value)
{
var newNode = new Node<U>(value, this, this.Prev);
Prev = newNode;
return newNode;
}
}
private Node<T> head;
private Node<T> tail;
public DoublyLinkedList()
{
head = null;
tail = null;
}
// copy constructor
public DoublyLinkedList(DoublyLinkedList<T> list)
{
head = list.head;
if (head == null)
{
tail = null;
return;
}
var position = head;
while (position.Next != null)
{
position.Next = new Node<T>((T) position.Next.Value.Clone(), position.Next.Next, position.Next.Prev);
position = position.Next;
}
tail = position;
}
public void Append(T value)
{
if (tail == null)
{
head = tail = new Node<T>(value, null, null);
}
else
{
var newNode = tail.AddNodeAfter(value);
tail.Next = newNode;
tail = newNode;
}
}
public void Prepend(T value)
{
if (tail == null)
{
head = tail = new Node<T>(value, null, null);
}
else
{
var newNode = head.AddNodeBefore(value);
head = newNode;
}
}
public object Clone()
{
return new DoublyLinkedList<T>(this);
}
// basically like an iterator
public IEnumerator<T> GetEnumerator()
{
// This is C# syntax... not sure if Java has "yield return"
var node = head;
while (node != null)
{
yield return node.Value;
node = node.Next;
}
}
// C# likes to be pedantic about this... this doesn't really matter but I need it to
// officially "implement" IEnumerable
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
// "new" is pedantic, but I wanted to remove the compiler warning.
public new string ToString()
{
var builder = new StringBuilder();
builder.Append("[ ");
foreach (var value in this)
{
builder.Append(value);
builder.Append(" ");
}
builder.Append("]");
return builder.ToString();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment