1 post tagged “linked list”
For archive purposes, I am posing a custom, generic, sortable, event-driven, doubly-linked list. In the future I will run some tests on it to see if it beats the current linked list implementation provided by the .NET framework. For those unsure of what a linked list is, here is a small tutorial on it.
Collections
When programming a computer, it is very common to store many items of the same type. Some different types of storing methods include array's, lists, and linked lists. The array is probably the most common for those attempting to store items. When an array of items is specified, the computer goes into memory and searches for a place to allocate the array. If it cannot allocate the entire array, it will keep searching. until it can.
Note: I put 5 spaces in the array definition. This is because of a manifest placed in the array, however, the inter workings of memory is beyond the scope of this article.
Now the problem with the array rises when someone runs out of room in their array. If they have an array that is 5 items large, and they want to hold a 6th, they must now re-define an entirely new array that can hold the new information. This requires the computer to go through and find another spot in memory that is big enough, place the new array in there, and then copy the elements from the original array to the new array. This problem is where a linked list comes in handy.
The Linked List
When a linked list is used, every item is stored in a chain of items. The linked list works by housing the references to the next (and previous in doubly linked lists) items in the chain. To do this, it is common to house your value inside a node. That node contains a reference in memory to the next node. Thus, you can define nodes anywhere you want in memory as long as you link to it making it easy to add and remove any amount of elements in the chain. The code would look something like this if you are trying to store integers:
public class LinkedList
{
Node firstNode;
public class Node
{
Node previous;
Node next;
int value;
}
}
Problems
With anything in computer science, there are downfalls to using Linked Lists. In order to get to an element in the linked list, you must traverse the entire list until you get to that element. This can be time consuming if there are a lot of nodes. Another problem is if you lose a reference to one of the nodes, you break the entire list. However, in a lot of circumstances, it is very useful to be able to add and remove items on the fly just by changing references.
Source
Here is an example doubly linked list example that I wrote. Thank dusda for the event driven idea. It is a doubly linked list that will convert to an array if needed. It supports any data type, and automatically sorts if specified. There is even support for getting an item by it's location (index). I hope you all find it useful.
using System;
namespace Systepic.Collections
{
/// <summary>
/// Event Handler designed to be thrown
/// when a collection's list items change.
/// </summary>
/// <param name="sender">The list that
/// fired the event.</param>
/// <param name="e">Information about
/// what the event did.</param>
public delegate void CollectionEventHandler(
Object sender, CollectionEventArgs e);
/// <summary>
/// Class inheriting from EventArgs designed
/// to hold information about the state change
/// of a collection.
/// </summary>
public class CollectionEventArgs : EventArgs
{
public CollectionEventArgs():base(){}
}
/// <summary>
/// A generic sortable linked list.
/// </summary>
/// <typeparam name="T">The type
/// that the linked list is. The type
/// should be a valuetype or a string
/// in order to be sorted.</typeparam>
public class LinkedList<T>
{
/// <summary>
/// An event fired whenever the collection
/// contents change.
/// </summary>
public event CollectionEventHandler ListChanged;
/// <summary>
/// The initial node to iterate in the list.
/// </summary>
private Node<T> firstNode;
/// <summary>
/// The number of items in the linked list.
/// </summary>
private int count;
/// <summary>
/// Whether or not it is a sorted list.
/// </summary>
private bool sorted;
/// <summary>
/// Create a new unsorted
/// linked list.
/// </summary>
public LinkedList() : this(false) { }
/// <summary>
/// Create a new linked list that
/// can be a sorted linked list.
/// </summary>
/// <param name="sorted">Whether or not
/// the linked list should be sorted.</param>
public LinkedList(bool sorted)
{
this.count = 0;
this.sorted = sorted;
}
/// <summary>
/// Adds an item to the end of the current
/// linked list. If the linked list is a
/// sorted list, the list is re-sorted.
/// </summary>
/// <param name="item">The item that should
/// be added to the linked list.</param>
/// <returns>Whether or not the item was
/// added successfully.</returns>
public bool Add(T item)
{
// Add if there is none
if (this.count == 0)
this.firstNode = new Node<T>(item);
else
{
Node<T> temp = this.firstNode;
for (int x = 1; x < this.count; ++x)
temp = temp.Next;
// Add a new item to the list
temp.Next = new Node<T>(
item, temp, null);
}
// increment the counter.
++count;
if (this.sorted) this.Sort();
// fire the event
if (this.ListChanged != null)
this.ListChanged(this,
new CollectionEventArgs());
// Call the insertAt method.
return true;
}
/// <summary>
/// Insert an item at a specified index in
/// the linked list. If the linked list is
/// a sorted list, the list is re-sorted.
/// </summary>
/// <param name="item">The item to add to the
/// linked list.</param>
/// <param name="index">The 0 based index of where
/// it should be added at.</param>
/// <returns>Whether or not the item was added
/// successfully.</returns>
public bool InsertAt(T item, int index)
{
// make sure the index is valid
if (index < 0)
throw new IndexOutOfRangeException();
if (index >= this.count)
throw new IndexOutOfRangeException();
// make sure there is an actual place to insert
if (count == 0)
return false;
// Create temp node to store info
Node<T> tempNode = new Node<T>(item);
// Create a temporary for iteration
Node<T> temp = this.firstNode;
// get to the specified index
for (int x = 1; x <= index; ++x)
temp = temp.Next;
// get the current reference.
if (index > 0)
{
Node<T> prev = temp.Previous;
prev.Next = tempNode;
tempNode.Previous = prev;
}
// set the references
tempNode.Next = temp;
temp.Previous = tempNode;
if (index == 0)
this.firstNode = tempNode;
// update the list information
++count;
if(this.sorted) this.Sort();
// fire event
if (this.ListChanged != null)
this.ListChanged(this,
new CollectionEventArgs());
return true;
}
/// <summary>
/// Find a particular item and remove
/// it from the linked list.
/// </summary>
/// <param name="item">The item to find
/// in the list.</param>
/// <returns>Whether or not the item
/// was removed successfully.</returns>
public bool Remove(T item)
{
// make sure we can remove
if (count < 1)
return false;
Node<T> temp = this.firstNode;
// Iterate and find item
for (int x = 1; x <= this.count; ++x)
{
if ((item as object) == (temp.Value as object))
{
// Change the references
if (temp.HasNext && temp.HasPrevious)
{
temp.Previous.Next = temp.Next;
temp.Next.Previous = temp.Previous;
}
else if (temp.HasNext)
temp.Next.Previous = null;
else if (temp.HasPrevious)
temp.Previous.Next = null;
else
temp = null;
// Reset the first Node if we
// removed it.
if (x == 1 && temp != null)
this.firstNode = temp.Next;
// Handle the counter
--count;
}
if (temp != null && temp.HasNext)
temp = temp.Next;
}
// Resort the algorithm if it is
// a sorted algorithm
if (this.sorted) this.Sort();
// fire event
if (this.ListChanged != null)
this.ListChanged(this,
new CollectionEventArgs());
return true;
}
/// <summary>
/// Sorts a list using insertion sort. Although
/// this algorithm is considered slow, since the
/// list is always almost sorted, the time to sort
/// the list is really fast whereas most high speed
/// algorithms will not beat this in this particular
/// instance because they handle near-sorted
/// algorithms the same as unsorted.
/// </summary>
/// <returns>Whether or not the
/// list was sorted successfully.</returns>
public bool Sort()
{
if (this.firstNode.Value is IComparable)
{
// check index out of range
if (this.firstNode.Next == null)
return true;
// get the base comparison
Node<T> baseNode = this.firstNode.Next;
// traverse the nodes
for (int x = 2; x <= this.count; ++x)
{
if ((baseNode.Previous.Value as
IComparable).CompareTo(
baseNode.Value) == 1)
{
Node<T> comp = this.firstNode;
bool found = false;
for (int y = 1; y < x && found != true; ++y)
{
if ((baseNode.Value as
IComparable).CompareTo(comp.Value) != 1)
{
// We need to change the references
// to all of the nodes to re-order them.
if (baseNode.HasNext)
{
baseNode.Next.Previous =
baseNode.Previous;
baseNode.Previous.Next =
baseNode.Next;
}
else
baseNode.Previous.Next = null;
baseNode.Next = comp;
if (comp.HasPrevious)
{
comp.Previous.Next =
baseNode;
baseNode.Previous =
comp.Previous;
}
else
baseNode.Previous = null;
comp.Previous = baseNode;
// the references are set... make
// sure the first node gets reset
// if needed.
if (y == 1)
this.firstNode = baseNode;
found = true;
}
// Set the next node
if (comp.HasNext)
comp = comp.Next;
}
}
// Set the next node
if (baseNode.HasNext)
baseNode = baseNode.Next;
}
return true;
}
else
return false;
}
/// <summary>
/// Clears all of the items in the
/// list by removing the reference
/// to the first node. The remaining
/// nodes no longer have references to
/// the application and will be collected
/// by the GC.
/// </summary>
public void Clear()
{
// kill the reference
this.firstNode = null;
// reset the count
this.count = 0;
// let everyone know.
if (this.ListChanged != null)
this.ListChanged(this,
new CollectionEventArgs());
}
/// <summary>
/// Converts the linked list to
/// an array.
/// </summary>
/// <returns>An array of the items
/// in the linked list ordered by
/// their location in the list top
/// down.</returns>
public T[] ToArray()
{
if (this.count < 1)
return default(T[]);
T[] newArray = new T[this.count];
// create a temp node
Node<T> temp = this.firstNode;
newArray[0] = temp.Value;
// iterate and get the node
for (int x = 1; x < this.count; ++x)
{
temp = temp.Next;
newArray[x] = temp.Value;
}
return newArray;
}
/// <summary>
/// Allows the use of this linked list
/// like it is an array. Get an item
/// in the linked list by it's location
/// in the list.
/// </summary>
/// <param name="index">The 0 based location
/// of the item to get in the list.</param>
/// <returns>The item at the specified
/// location.</returns>
public T this[int index]
{
get
{
// make sure we can do it before traversal.
if (index + 1 > count)
throw new IndexOutOfRangeException();
// create a temp node
Node<T> temp = this.firstNode;
// iterate and get the node
for (int x = 1; x <= index; ++x)
temp = temp.Next;
// return the node value
return temp.Value;
}
set
{
// make sure we can do it before traversal.
if(index + 1 > count)
throw new IndexOutOfRangeException();
// create a temp node
Node<T> temp = this.firstNode;
// iterate and get the node
for (int x = 0; x < index; ++x)
temp = temp.Next;
// set the node to value
temp.Value = value;
}
}
/// <summary>
/// How many nodes are contained in the
/// Linked List.
/// </summary>
public int Length
{
get { return this.count; }
}
/// <summary>
/// Whether or not this list sorts
/// automatically.
/// </summary>
public bool IsSorted
{
get { return this.sorted; }
set { this.sorted = value; }
}
/// <summary>
/// Generic node with pre and post references
/// for use in a linked list.
/// </summary>
/// <typeparam name="U">The type of
/// information contained within the node.</typeparam>
private class Node<U>
{
/// <summary>
/// The node reference to the node
/// before this node reference.
/// </summary>
Node<U> pre;
/// <summary>
/// The node reference to the node after
/// this node reference.
/// </summary>
Node<U> post;
/// <summary>
/// The generic information stored within
/// the node.
/// </summary>
U assignment;
/// <summary>
/// Create a new node with references
/// to both sides of the node.
/// </summary>
/// <param name="info">What the node actually
/// contains.</param>
/// <param name="previous">The node before this
/// node.</param>
/// <param name="next">The node after this
/// node.</param>
public Node(U info, Node<U> previous, Node<U> next)
{
this.assignment = info;
this.pre = previous;
this.post = next;
}
/// <summary>
/// Create a new node with no references
/// to nodes.
/// </summary>
/// <param name="info">The information
/// that the node actually contains.</param>
public Node(U info) : this(info, null, null) { }
/// <summary>
/// The node before this node in the chain.
/// </summary>
public Node<U> Previous
{
get { return this.pre; }
set { this.pre = value; }
}
/// <summary>
/// The node after this node in the chain.
/// </summary>
public Node<U> Next
{
get { return this.post; }
set { this.post = value; }
}
/// <summary>
/// Whether or not the node has a node
/// reference to the previous node.
/// </summary>
public bool HasPrevious
{
get { return (this.pre == null) ? false : true; }
}
/// <summary>
/// Whether or not the node has a node
/// reference to the next node.
/// </summary>
public bool HasNext
{
get { return (this.post == null) ? false : true; }
}
/// <summary>
/// The actual value stored in this node.
/// </summary>
public U Value
{
get { return this.assignment; }
set { this.assignment = value; }
}
}
}
}
