/// <summary>
/// Represents a node
/// </summary>
/// <typeparam name="T"></typeparam>
public sealed class Node<T>
{
/// <summary>
/// Gets the item
/// </summary>
public T Item { get; private set; }
/// <summary>
/// Gets next node
/// </summary>
public Node<T> Next { get; set; }
/// <summary>
/// Initializes a new <see cref="Node"/> instance
/// </summary>
/// <param name="item">Item to be assigned</param>
public Node(T item)
{
this.Item = item;
}
}
/// <summary>
/// Represents a strongly typed list of objects that can be accessed in a
/// circular linked list fashion
/// </summary>
/// <typeparam name="T">Type of the object</typeparam>
public sealed class CircularLinkedList<T> : IEnumerable<T>
{
readonly List<Node<T>> items;
/// <summary>
/// Initializes a new instance of <see cref="CircularLinkedList"/>
/// </summary>
public CircularLinkedList()
{
items = new List<Node<T>>();
}
/// <summary>
/// Initializes a new instance of <see cref="CircularLinkedList"/>
/// </summary>
/// <param name="collection">Collection of objects that will be added to linked list</param>
public CircularLinkedList(IEnumerable<T> collection)
{
foreach (T item in collection)
this.Add(item);
}
/// <summary>
/// Initializes a new instance of <see cref="CircularLinkedList"/>
/// </summary>
/// <param name="capacity">Capacity of the list</param>
public CircularLinkedList(int capacity)
{
items = new List<Node<T>>(capacity);
}
/// <summary>
/// Gets Tail node. Returns NULL if no tail node found
/// </summary>
public Node<T> Tail { get { return items.Count > 0 ? items[items.Count - 1] : null; } }
/// <summary>
/// Gets the head node. Returns NULL if no node found
/// </summary>
public Node<T> Head { get { return items.Count > 0 ? items[0] : null; } }
/// <summary>
/// Returns a node at the supplied position
/// </summary>
public Node<T> this[int index]
{
get
{
return items[index];
}
}
/// <summary>
/// Add a new item to the end of the list
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
Node<T> tailNode = this.Tail;
Node<T> headNode = this.Head;
Node<T> newNode = new Node<T>(item);
newNode.Next = headNode;
if (tailNode != null)
tailNode.Next = newNode;
items.Add(newNode);
}
public IEnumerator<T> GetEnumerator()
{
foreach (Node<T> node in items)
yield return node.Item;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
Refactorings
No refactoring yet !
Ants
August 14, 2009, August 14, 2009 20:09, permalink
I think that you are missing the point of a circular linked list. The idea is to not to have to use List<Node<T>> items, but to simply have Node<T> head. The Head property will return head, but Tail will have to walk the linked list to find the tail (e.g. when the Node<T>.Next == head); Count property will count the number of nodes until the tail is found; this[i] access will walk the linked list to the i-th item; Insert() will walk to the tail and tack on the new node; etc.
As you can see, all of this walking the list tends to give almost all operations performed on a circular linked list an O(n) complexity. Most people try to optimize for the insert and count cases, and will add Node<T> tail, and int count as member variables to give these O(1) complexity.
navaneethkn
August 15, 2009, August 15, 2009 14:59, permalink
Hi Ants,
Thanks. That was a great suggestion. I changed the code as per your suggestion. Here is the updated one. No change made to Node class. I am still using a List<T> just for enumeration purpose. I couldn't find a best way to recursively enumerate using "yield return".
Will that be good if enumeration loops forever? So user can keep on walking through the circle until they stop it manually.
public sealed class CircularLinkedList<T> : IEnumerable<T>
{
Node<T> head = null;
Node<T> tail = null;
List<T> items = new List<T>(); // just for enumeration
/// <summary>
/// Initializes a new instance of <see cref="CircularLinkedList"/>
/// </summary>
public CircularLinkedList()
{
}
/// <summary>
/// Initializes a new instance of <see cref="CircularLinkedList"/>
/// </summary>
/// <param name="collection">Collection of objects that will be added to linked list</param>
public CircularLinkedList(IEnumerable<T> collection)
{
foreach (T item in collection)
this.Add(item);
}
/// <summary>
/// Gets Tail node. Returns NULL if no tail node found
/// </summary>
public Node<T> Tail { get { return tail; } }
/// <summary>
/// Gets the head node. Returns NULL if no node found
/// </summary>
public Node<T> Head { get { return head; } }
/// <summary>
/// Add a new item to the end of the list
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
// if head is null, then this will be the first item
if (head == null)
{
head = new Node<T>(item);
tail = head;
head.Next = tail;
}
else
{
Node<T> newNode = new Node<T>(item);
tail.Next = newNode;
newNode.Next = head;
tail = newNode;
}
// keeping in a list just for enumeration purpose
items.Add(item);
}
public IEnumerator<T> GetEnumerator()
{
return items.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
Ants
August 15, 2009, August 15, 2009 16:39, permalink
Try something like this for GetEnumerator():
public IEnumerator<T> GetEnumerator()
{
Node<T> current = head;
if (current != null)
{
do
{
yield return current.Item;
current = current.Next
} while (current != head)
}
}
whizack
January 28, 2010, January 28, 2010 03:04, permalink
Is IEnumerable<T> really an appropriate interface to implement for a circular reference?
The point of a circular buffer would be to read/write live data and IEnumerable doesn't support list manipulation during iteration.
Here is my circular linked list implementation. Your feedback's are most welcome. This contains two classes, CircularLinkedList and Node. "Node" will have a "Next" property which will give the next element it is pointing to. For last node, the "Next" property points to the first element(head).