Data structure is fundemental to programming.
Today, we will talk about basic data structure and it’s manipulation using C#. We will cover the most commonly used data structures including:
- Array
- List
- HashSet
- Dictionary
- Queue
- Stack
Array
Array holds certain number of items in consecutive memory. It is useful if you know how many items you are dealing with at the start.
It provides
- O(1) access/modify via index
- O(N) iteration (memory friendly)
- O(N) search for a particular value in an unsorted array
- O(logN) search for a value in a sorted array
Initialize
//T[] arr = new T[s]; T: Type s: length of the array//initialize an array of int with a length of 3int[] myArray = new int[3];
Access & Modify
myArray[0] = 100; //access & modify by index
Iteration
//.Length : the length of the arrayfor(int i=0; i<myArray.Length; i++){//print each elementConsole.Write(myArray[i]);}
List
List is implemented as dynamic array in C#. Dynamic array is an array that automatically doubles its length when it has reached it’s capacity. Therefore, it’s useful when you don’t know how many items you are dealling with from the start.
Similar to Array, It provides:
- O(1) : access/modify via index
- Amotized O(1) : Append
- O(N) iteration (memory friendly)
- O(N) search for a particular value in an unsorted List
- O(logN) search for a value in a sorted List
Initialize
//List<T> list = new List<T>();//make a new list of charList<char> myCharList = new List<char>();
Access & Modify
//Add elementmyCharList.Add('a');myCharList.Add('b');//access & modify by indexmyCharList[0] = 'c';
Iteration
HashSet
HashSet is useful to: remove duplicate automatically, track whether you’ve seen an item already.
It provides:
- O(1) insert
- O(1) checking whether it contains a value
Initialize
//HashSet<T> mySet = new HashSet<T>();//make a new HashSetHashSet<string> mySet = new HashSet<string>();
Access & Modify
//Add an element to a HashSetmySet.Add("apple");mySet.Add("orange");mySet.Add("apple";
Iteration
//using System.Linq;foreach(string item in mySet){//do something}
Dictionary
Dictionary is useful to find a value by key efficently.
It provides
- O(1) access & modify via Key
- O(1) insert
- O(1) check if it contains certain Key
- O(N) to look for a particular value
Initialize
Access & Modify
Iteration
Queue
Queue is a data structures offer : FIFO. (First in first out)
It provides:
- O(1) to add to the end of the queue (Enqueue)
- O(1) to remove the front of the queue (Dequeue)
- O(N) to iterate
Initialize
Access & Modify
Stack
Stack is a data structures offer : LIFO. (Last in first out)
It provides:
- O(1) to add to the top of the stack (Push)
- O(1) to remove the top of the stack (Pop)
- O(N) to iterate
Initialize
Access & Modify
Iteration
