C# Data Structures
An overview of data structures in C# with examples.
- If you need to iterate over a specific size of data that will not grow or shrink and you will not be searching it frequently, use an Array.
- If you need to iterate over a set of data that may grow or shrink and you will not be searching it frequently, use a List, Queue (first in, first out), or Stack (last in, first out).
- If you need to iterate over a set of data that you will search frequently, use a SkipList.
- If you need to store a large set of data and access it frequently, use a Dictionary.
Table of Contents
Arrays
- Homogeneous (all elements of an array must be of the same type or of a derived type)
- If unsorted, has O(n) access speed and each element can be directly accessed.
- Fixed size
- In most cases you should use a List instead, unless you know you are working with a specific size of data and will not be searching it frequently (iteration operations are fine).
When Not To Use
- Storing a large amount of data that is searched frequently.
Working with arrays (Examples)
Creation:
bool[] b = new bool[10];
Reading an element:
bool b = booleanArray[7];
Writing to an element:
booleanArray[0] = false;
Resizing an array:
int[] fib = new int[3];
int[] temp = new int[10]
fib.CopyTo(temp, 0); // This causes unassigned elements to initialize with a value of 0
fib = temp;
Sorting an array of type int, double, or string:
// sort int array
int[] intArray = new int[5] { 8, 10, 2, 6, 3 };
Array.Sort(intArray);
// write array
foreach (int i in intArray) Console.Write(i + " "); // output: 2 3 6 8 10
Sorting a custom type by implementing IComparable:
// custom type
public class User : IComparable
{
// ...
// implement IComparable interface
public int CompareTo(object obj)
{
if (obj is User) {
return this.Name.CompareTo((obj as User).Name); // compare user names
}
throw new ArgumentException("Object is not a User");
}
}
You can then just call Array.Sort() since the method internally calls IComparable.CompareTo():
// sort using IComparable implemented by User class
Array.Sort(users); // sort array of User objects
Searching an unsorted array (linear search; performance impact equal to size of the array):
public bool existsInArray (int numberToFind)
{
// loop through array until we find the right element.
for (int i = 0; i < array.Length; i++)
{
if (array[i] == numberToFind)
{
return true;
}
}
return false;
}
Searching a sorted array of type int, double, or string using BinarySearch method:
int index = array.BinarySearch(myArray, elementToFind);
If index equals a number 0 or greater, then that is the index of the element in the array. If index is less than zero, then the element does not exist in the array.
The reason this works with int, double, and string types is because these types implement IComparable.
Searching a sorted array that does not implement IComparable using BinarySearch method:
You must provide a comparing function that BinarySearch() can use to compare values. The most common way is to implement the IComparer interface, which requires a single Compare(Object x, Object y) method to be implemented:
using System;
using System.Collections;
public class CompareCustomDataType : IComparer {
public int Compare(Object x, Object y)
{
if (x == null) return -1;
if (y == null) return 1;
       // Cast from type object to type student and then compare using String.Compare()
Student xStudent = (Student) x;
Student yStudent = (Student) y;
return String.Compare(xStudent.Name, yStudent.Name);
}
}
Now we can use BinarySearch() to search the array:
// Create an array of 5 students
Student[] myArray = new Student[4];
myArray[0] = new Student("Scott", 24);
myArray[1] = new Student("Jisun", 23);
myArray[2] = new Student("Spacey", 21);
myArray[3] = new Student("John", 23);
myArray[4] = new Student("Josh", 20);
// Sort the array
Array.Sort(myArray, New CompareCustomDataType);
// Determine if a particular student exists in the array
Student studentTemp = new Student();
studentTemp.Name = "Jisun";
int location = Array.BinarySearch(myArray, studentTemp, New CompareCustomDataType);
if (location < 0)
Debug.Log("Student Jisun does not exist in the array");
else
Debug.Log("Student Jisun exists in the array at position " + location);
Note the reason we prefer to use BinarySearch() to search a sorted array is because it has a running time of O(log n), which is faster than the unsorted search O(n).
ArrayList
Do not use this – implement a Generic instead.
- Not type-safe, meaning it can cause runtime errors because a programmer may cast something improperly and the compiler will not see this as an error.
- Performance overhead since everything has to be casted to the correct type.
Generics
- Allows developers to create data structures that defer type selection and removes the need to type check at run-time and eliminates performance costs associated with boxing and unboxing.
- Commonly used to create abstraction. For example, sorting is often independent of type, so a generic sorting method can be very useful.
Working with Generics
For example, if we wanted to create an object-based state machine in Unity where each state was a class (different type), we would need to be able to work with each state the same way regardless of what its name is.
using UnityEngine;
using System.Collections;
public class StateMachine : MonoBehaviour
{
public virtual State CurrentState
{
get { return _currentState; }
set { Transition (value); }
}
protected State _currentState;
protected bool _inTransition;
public virtual T GetState () where T : State
{
T target = GetComponent();
if (target == null)
target = gameObject.AddComponent();
return target;
}
public virtual void ChangeState () where T : State
{
CurrentState = GetState();
}
protected virtual void Transition (State value)
{
if (_currentState == value || _inTransition)
return;
_inTransition = true;
if (_currentState != null)
_currentState.Exit();
_currentState = value;
if (_currentState != null)
_currentState.Enter();
_inTransition = false;
}
}
GetState() is a generic that will work with any object inheriting from State. This allows us to get any State and call its Enter() and Exit() overrides during a transition.
List
- Functions as a homogeneous, self-redimensioning array.
- Elements can be directly accessed via an ordinal index.
- Cost per operation is the same as operating on a standard array.
Working with Lists (examples)
Creation:
List myIntegerList = new List();
// Can also be done like this to populate initial values.
var listA = new List() { 8, 3, 2 };
// Can also create a list that is a copy of another list or an array
// (or anything that implements IEnumerable)
var listB = new List(listA);
Adding an item to a list:
myIntegerList.Add(3);
// Adding another list to the end of a list.
listA.AddRange(listB);
Modifying an element:
myIntegerList[1] = 4;
Removing an element:
// Remove the specified item from the list.
list.Remove(item: 4);
// Remove the item at the specified index.
list.RemoveAt(index: 2);
// Remove all items matching the specified predicate.
list.RemoveAll(x => x < 4);
Sorting an unsorted list:
If the list is of type int, string, or double (or otherwise implements the IComparable interface):
list.Sort();
Implementing IComparable:
// custom type
public class User : IComparable
{
// ...
// implement IComparable interface
public int CompareTo(object obj)
{
if (obj is User) {
return this.Name.CompareTo((obj as User).Name); // compare user names
}
throw new ArgumentException("Object is not a User");
}
}
You can then just use the Sort() method since IComparable has been implemented in the type.
Note that Sort() automatically calls the CompareTo() method of IComparable so a custom comparer does not need to be passed in.
To sort a list using a custom comparer:
list.Sort(new MyComparer() );
Searching a sorted list:
A sorted list of a type that implements the IComparable interface can be searched using BinarySearch():
// Returns the index where 6 is found in the list.
// If 6 is not found, a negative number is returned.
int index = list.BinarySearch(6);
Search a sorted list using a custom comparer:
// Returns the index where 6 is found in the list.
// If 6 is not found, a negative number is returned.
int index = list.BinarySearch(6, new MyComparer() );
To determine if an item exists in a list:
// See if any elements with values greater than 10 exist
bool exists = list.Exists(x => x > 10);
To find an item in a list that meets a requirement:
// Finds the first item in the list that is greater than 2.
int item = list.Find(x => x > 2);
// Finds the last item in the list less than 5.
int index = list.FindLast(x => x < 5);
To find the index of an item in a list that meets a requirement:
// Finds the index of the first element less than 5.
int index = list.FindIndex(x => x < 5);
// Finds the index of the last element less than 5.
int index = list.FindLastIndex(x => x < 5);
Clear a list (capacity remains unchanged):
list.Clear();
Trim a list (only works if excess greatly exceeds the capacity):
list.TrimExcess();
Queue
- Used when you want to add and remove items in a first-in, first-out basis.
- Ideal for processing items in the order in which they were received.
When Not To Use
- When you need random access or specific access to an element (a queue must be handled one item at a time, starting with the first item).
Working with Queues (examples)
Creation:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Initialize help requeust Queue
Queue help = new Queue();
}
}
Adding to the queue:
// ASP.NET website records a Text Problem help request.
help.Enqueue(RequestType.TextProblem);
Removing from the queue:
// You solve the request. It was a simple TextProblem
help.Dequeue();
Copy queue elements to an array:
// Create new array with Length equal to Queue's element count.
int[] array = new int[queue.Count];
// Copy the Queue to the int array.
queue.CopyTo(array, 0);
Look at the top element of the queue without removing it:
queue.Peek();
See if a queue contains an item (linear search, O(n) running time):
bool fourInQueue = queue.Contains("four");
Get number of elements in queue:
int queueSize = queue.Count;
Stack
- Last in, first out data structure. Ideal for processing items in the reverse order they were received.
- Operates very similarly to the queue.
When Not To Use
- When you need random access or specific access to an element.
Working with stacks (examples)
Creation
Stack phrases = new Stack();
Adding to the top of a stack:
myStack.Push("Hello");
Removing the top item in the stack:
string nextPhrase = phrases.Pop();
Look at top item in the stack without removing it:
string upcomingPhrase = phrases.Peek();
Check if an item exists in the stack:
bool hasPhrase = phrases.Contains("Hello");
Convert stack to an array:
// Create an array twice the size of the stack and copy the
// elements of the stack, starting at the middle of the
// array.
string[] array2 = new string[phrases.Count * 2];
phrases.CopyTo(array2, phrases.Count);
Clear a stack (retains its capacity):
phrases.Clear();
Hashtable
Don’t use this unless necessary. Instead, use a Dictionary where possible for better performance.
- Associates each element with a ‘key’.
- Duplicate entries are not allowed.
- Great for searching for specific elements in a very large or potentially very large set of data.
NOTE: Expanding a hashtable’s size is an expensive operation. You should estimate how many items your hashtable will contain and set the initial capacity accordingly in the constructor.
When Not to Use
- When you need to iterate through an entire collection that may or may not have duplicate values.
Working with Hashtables (examples)
Creation:
// Example of a static hashtable.
static Hashtable employees = new Hashtable(100,000);
Adding an element to a hashtable:
employees.Add("Joe", "Software Engineer");
Check if a key exists in a hashtable
bool JoeExists = employees.ContainsKey("Joe");
Iterate through elements in a hastable:
// Step through all items in the hashtable
foreach (string key in employees.Keys)
Console.WriteLine ("Value at employees[\"" + key + "\"] = " + employees[key].ToString());
Remove an element in a hashtable:
// Removes the previously added employee based on key.
employees.Remove("Joe");
Remove all elements in a hashtable:
employees.Clear();
Dictionary
- Type-safe hashtable that is optimized for better performance.
Working with Dictionaries (examples)
Creation
Dictionary employeeData = new Dictionary();
Adding an element:
employees.Add("Joe", "Software Engineer");
Look up a value based on key:
Note this is the preferred method of looking up a value based on key.
Employee ourEmployee;
// Returns true if Joe exists, and writes the value to ourEmployee.
bool employeeFound = employees.TryGetValue("Joe", out ourEmployee);
Check if a key exists
bool JoeExists = employees.ContainsKey("Joe");
Iterate through elements:
// Step through all items in the dictionary
foreach(KeyValuePair<string, string> entry in employees)
{
// do something with entry.Value or entry.Key
}
Remove an element:
// Removes the previously added employee based on key.
employees.Remove("Joe");
Remove all elements:
employees.Clear();
SkipList
A sorted linked list with decent search times.
Implementation
Base Node class:
using System.Collections.Generics;
public class Node
{
// Private member-variables
private T data;
private NodeList neighbors = null;
public Node() {}
public Node(T data) : this(data, null) {}
public Node(T data, NodeList neighbors)
{
this.data = data;
this.neighbors = neighbors;
}
public T Value
{
get
{
return data;
}
set
{
data = value;
}
}
protected NodeList Neighbors
{
get
{
return neighbors;
}
set
{
neighbors = value;
}
}
}
Base NodeList class:
public class NodeList : Collection<Node>
{
public NodeList() : base() { }
public NodeList(int initialSize)
{
// Add the specified number of items
for (int i = 0; i < initialSize; i++)
base.Items.Add(default(Node));
}
public Node FindByValue(T value)
{
// search the list for the value
foreach (Node node in Items)
if (node.Value.Equals(value))
return node;
// if we reached here, we didn't find a matching node
return null;
}
}
The SkipListNode class extends the Node class:
public class SkipListNode : Node
{
private SkipListNode() {} // no default constructor available, must supply height
public SkipListNode(int height)
{
base.Neighbors = new SkipListNodeList(height);
}
public SkipListNode(T value, int height) : base(value)
{
base.Neighbors = new SkipListNodeList(height);
}
public int Height
{
get { return base.Neighbors.Count; }
}
public SkipListNode this[int index]
{
get { return (SkipListNode) base.Neighbors[index]; }
set { base.Neighbors[index] = value; }
}
}
It requires a SkipListNodeList to be implemented, which extends the NodeList class:
public class SkipListNodeList : NodeList
{
public SkipListNodeList(int height) : base(height) { }
internal void IncrementHeight()
{
// add a dummy entry
base.Items.Add(default(Node));
}
internal void DecrementHeight()
{
// delete the last entry
base.Items.RemoveAt(base.Items.Count - 1);
}
}
Here is the SkipList class itself:
public class SkipList : IEnumerable, ICollection
{
SkipListNode _head;
int _count;
Random _rndNum;
private IComparer comparer = Comparer.Default;
protected readonly double _prob = 0.5;
public int Height
{
get { return _head.Height; }
}
public int Count
{
get { return _count; }
}
public SkipList() : this(-1, null) {}
public SkipList(int randomSeed) : this(randomSeed, null) {}
public SkipList(IComparer comparer) : this(-1, comparer) {}
public SkipList(int randomSeed, IComparer comparer)
{
_head = new SkipListNode(1);
_count = 0;
if (randomSeed < 0)
_rndNum = new Random();
else
_rndNum = new Random(randomSeed);
if (comparer != null) this.comparer = comparer;
}
const double _prob = 0.5;
protected virtual int ChooseRandomHeight()
{
int level = 1;
while (_rndNum.NextDouble() < _prob)
level++;
return level;
}
protected virtual int ChooseRandomHeight(int maxLevel)
{
int level = 1;
while (_rndNum.NextDouble() < _prob && level < maxLevel)
level++;
return level;
}
public bool Contains(T value)
{
SkipListNode current = _head;
for (int i = _head.Height - 1; i >= 0; i--)
{
while (current[i] != null)
{
int results = comparer.Compare(current[i].Value, value);
if (results == 0)
return true; // we found the element
else if (results < 0) current = current[i]; // the element is to the left, so move down a leve; else // results > 0
break; // exit while loop, because the element is to the right of this node,
//at (or lower than) the current level
}
}
// if we reach here, we searched to the end of the list without finding the element
return false;
}
public void Add(T value)
{
SkipListNode[] updates = BuildUpdateTable(value);
SkipListNode current = updates[0];
// see if a duplicate is being inserted
if (current[0] != null && current[0].Value.CompareTo(value) == 0)
// cannot enter a duplicate, handle this case by either just returning or by throwing an exception
return;
// create a new node
SkipListNode n = new SkipListNode(value, ChooseRandomHeight(head.Height + 1));
_count++; // increment the count of elements in the skip list
// if the node's level is greater than the head's level, increase the head's level
if (n.Height > _head.Height)
{
_head.IncrementHeight();
_head[_head.Height - 1] = n;
}
// splice the new node into the list
for (int i = 0; i < n.Height; i++)
{
if (i < updates.Length)
{
n[i] = updates[i][i];
updates[i][i] = n;
}
}
}
protected SkipListNode[] BuildUpdateTable(T value)
{
SkipListNode[] updates = new SkipListNode[_head.Height];
SkipListNode current = _head;
// determine the nodes that need to be updated at each level
for (int i = _head.Height - 1; i >= 0; i--)
{
while (current[i] != null && comparer.Compare(current[i].Value, value) < 0)
current = current[i];
updates[i] = current;
}
return updates;
}
public bool Remove(T value)
{
_count--;
// We found the data to delete
for (int i = 0; i < _head.Height; i++)
{
if (updates[i][i] != current)
break;
else
updates[i][i] = current[i];
}
// finally, see if we need to trim the height of the list
if (_head[_head.Height - 1] == null)
// we removed the single, tallest item... reduce the list height
_head.DecrementHeight();
return true; // item removed, return true
}
else
// the data to delete wasn't found – return false
return false;
}
}
Graph (Adjacency List Model)
A collection of nodes and edges with no rules dictating the connection among nodes.
Edges can be directed or undirected as well as weighted or unweighted.
- By default, an edge is assumed to be bidirection (undirected). If an edge only goes in one direction, it is directed.
- If edges have no cost, then they are unweighted. If there is a cost associated with a connection from one node to another, the edge is weighted.
Implementation
The GraphNode<T> class:
This extends the Node class created in the section on SkipLists.
public class GraphNode : Node
{
// A list of weights from this GraphNode to any specific neighbor.
private List costs;
public GraphNode() : base() { }
public GraphNode(T value) : base(value) { }
public GraphNode(T value, NodeList neighbors) : base(value, neighbors) { }
// A public reference to the base class's Neighbors property.
new public NodeList Neighbors
{
get
{
if (base.Neighbors == null)
base.Neighbors = new NodeList();
return base.Neighbors;
}
}
// A List mapping a weight from this graph node to a specific neighbor.
public List Costs
{
get
{
if (costs == null)
costs = new List();
return costs;
}
}
}
The Graph class:
The graph maintains a list of its nodes. Each node maintains a list of adjacent nodes. In creating the Graph class, we need to have a list of GraphNodes. This set of nodes is maintained using a NodeList instance. The Graph class exposes its set of nodes through the public property Nodes.
Additionally, the Graph class has a number of methods for adding nodes and directed or undirected and weighted or unweighted edges between nodes. The AddNode() method adds a node to the graph, while AddDirectedEdge() and AddUndirectedEdge() allow a weighted or unweighted edge to be associated between two nodes.
In addition to its methods for adding edges, the Graph class has a Contains() method that returns a Boolean indicating if a particular value exists in the graph or not. There is also a Remove() method that deletes a GraphNode and all edges to and from it.
public class Graph : IEnumerable
{
private NodeList nodeSet;
public Dictionary, Edge> Connections = new Dictionary, Edge>();
public Graph() : this(null) {}
public Graph(NodeList nodeSet)
{
if (nodeSet == null)
this.nodeSet = new NodeList();
else
this.nodeSet = nodeSet;
}
public void AddNode(GraphNode node)
{
// adds a node to the graph
nodeSet.Add(node);
}
public void AddNode(T value)
{
// adds a node to the graph
nodeSet.Add(new GraphNode(value));
}
public void AddDirectedEdge(GraphNode from, GraphNode to, int cost)
{
from.Neighbors.Add(to);
from.Costs.Add(cost);
Connections.Add(new GraphNodePair(from, to), new Edge(from, to, cost));
}
public void AddUndirectedEdge(GraphNode from, GraphNode to, int cost)
{
from.Neighbors.Add(to);
from.Costs.Add(cost);
to.Neighbors.Add(from);
to.Costs.Add(cost);
Connections.Add(new GraphNodePair(from, to), new Edge(from, to, cost));
}
public bool Contains(T value)
{
return nodeSet.FindByValue(value) != null;
}
public GraphNode GetNode(T value)
{
return nodeSet.FindByValue(value);
}
public bool Remove(T value)
{
// first remove the node from the nodeset
GraphNode nodeToRemove = (GraphNode) nodeSet.FindByValue(value);
if (nodeToRemove == null)
// node wasn't found
return false;
// otherwise, the node was found
nodeSet.Remove(nodeToRemove);
// enumerate through each node in the nodeSet, removing edges to this node
foreach (GraphNode gnode in nodeSet)
{
int index = gnode.Neighbors.IndexOf(nodeToRemove);
if (index != -1)
{
// remove the reference to the node and associated cost
gnode.Neighbors.RemoveAt(index);
gnode.Costs.RemoveAt(index);
}
}
return true;
}
public NodeList Nodes
{
get
{
return nodeSet;
}
}
public int Count
{
get { return nodeSet.Count; }
}
}
GraphNodePair declaration:
public struct GraphNodePair
{
GraphNode from;
GraphNode to;
public GraphNodePair (GraphNode from, GraphNode to)
{
this.from = from;
this.to = to;
}
}
The definition for an Edge is:
public class Edge
{
GraphNode from;
public GraphNode From
{
get { return from; }
}
GraphNode to;
public GraphNode To
{
get { return to; }
}
int cost;
public int Cost
{
get { return cost; }
}
public Edge (GraphNode from, GraphNode to, int cost)
{
this.from = from;
this.to = to;
this.cost = cost;
}
}
Common Graph Algorithms
Minimum Spanning Tree
For a connected, undirected graph, there exists some subset of the edges that connect all the nodes and does not introduce a cycle. Such a subset of edges would form a tree (because it would comprise one less edge than vertices and is acyclic), and is called a spanning tree. There are typically many spanning trees for a given graph.
For graphs with weighted edges, different spanning trees have different associated costs, where the cost is the sum of the weights of the edges that comprise the spanning tree. A minimum spanning tree, then, is the spanning tree with a minimum cost.
Dijkstra’s Algorithm
The late Edsger Dijkstra, one of the most noted computer scientists of all time, invented the most commonly used algorithm for finding the shortest path from a source node to all other nodes in a weighted, directed graph. This algorithm, dubbed Dijkstra’s Algorithm, works by maintaining two tables, each of which have a record for each node. These two tables are:
- A distance table, which keeps an up-to-date “best distance” from the source node to every other node.
- A route table, which, for each node n, indicates what node was used to reach n to get the best distance.
Initially, the distance table has each record set to some high value (like positive infinity) except for the start node, which has a distance to itself of 0. The route table’s rows are all set to null. Also, a collection of nodes, Q, that need to be examined is maintained; initially, this collection contains all of the nodes in the graph.
The algorithm proceeds by selecting (and removing) the node from Q that has the lowest value in the distance table. Let this selected node be called n and the value in the distance table for n be d. For each of the n‘s edges, a check is made to see if d plus the cost to get from n to that particular neighbor is less than the value for that neighbor in the distance table. If it is, then we’ve found a better way to reach that neighbor, and the distance and route tables are updated accordingly.
There are many ways to implement Dijkstra’s Algorithm available on the Internet with various running times based on what kinds of assumptions can be made about the graph.