Data Structures

Question	Answer
What is a data structure?	> A programming construct which allows us to organise different data elements in a clear, structured and efficient way. > Represented by different reference types, some of which are provided as part of the language, others you can define yourself.
Why do we use data structures?	They allow us to manipulate the collection of data for use in our program for our needs in the most efficient way.
Give examples of some data structures. Several Little Horses Spit Quills Simultaneously	> Static array > Linked list > Hash table > String > Queue > Stack
Describe and give an example of a static array.	A collection of fixed size. Useful when we know the number of items we need to store and we know this won't change. E.g. The nine planets in the solar system.
Describe and give an example of a Linked list.	A series of nodes each containing a value, a link to the next node, and a link to the previous node. Useful for collections we need to grow and shrink by adding and removing items. More flexible than an array but causes slower performance. adding values to the middle of the list is much faster compared to any other Array type of data structure. It also keeps memory costs down to a minimum. Lists on the other hand use extra space to make future insertions as fast as possible. E.g. A list of contacts on a phone.
Describe and give an example of a Hash table.	A collection of key value pairs. Useful for looking up values very quickly when their key is known. E.g. A List of thousands of addresses which need to be looked up quickly by their owner's names. The C# Hashtable data structure is very much like the Dictionary data structure. A Hashtable also takes in a key/value pair, but it does so as generic objects as opposed to typed data. Values are then stored in order according to their key's HashCode. Meaning that the order in which items are added to a C# Hashtable is not preserved. On the other hand, the Dictionary data structure does keep items in the same order. The reason is speed. A C# Hashtable stores items faster than a C# Dictionary, which sacrifices speed for the sake of order.
Describe and give an example of a String. ???AND THEIR USE????	A collection of characters which come with useful methods for manipulating them. E.g. A sentence, "Hello world In C#, you can use strings as array of characters, However, more common practice is to use the string keyword to declare a string variable. The string keyword is an alias for the System.String class.
Describe and give an example of a Queue.	A collection in which the first item added will be the first item removed. Adding and removing usually by enqueue and dequeue methods. E.g. A queue of people in a shop.
Describe and give an example of a Stack.	A collection of data in which the last item added will be the first item removed. Adding and removing usually done with push and pop methods. E.g. A stack of plates.
Explain Static Arrays, their design and their use. ????INSTANTIATION???	Static arrays are for fixed size collections of data. Initialise: 1. int[] numbers = new int[3]; 2. int[] numbers = {12, 15, 11}; (object initialisation syntax) If 1. then to populate one by one: numbers[0] = 12; Access: Console.WriteLine(numbers[0]); This will return first element.
Explain 2D Arrays, their design and their use.	2D arrays are where each slot contains another array creating 2 dimensions. E.g. A grid. Initialisation: int[,] seaMapGrid = new int [5,5] (5 by 5 grid) Populate: seaMapGrid[0,3] = 300; Access: Console.WriteLine(seaMapGrid[0,3]);
Explain Array Lists, their design and their use. __________________________	An Array List is a dynamic array, it can contain any amount of objects of any type. It's designed to simplify the process of adding elements to an array. Overtime it runs out of space it doubles in size. This is effective as it reduces the amount of enlarging in the long run. Instantiate: ArrayList Name = new ArrayList();
Explain Strings, their design and their use.	Data structures specifically designed to contain collections of characters. This data structure is provided in many languages including C#. In OOP languages you use a capital S as it is a class. Initialise: String Name = "This is a string."; Access: Console.WriteLine(Name[0]); This will return T.
Give examples of some common string functions.	ToUpper (Makes characters uppercase) ToLower (Makes characters lower case) Concat or + (Used to add strings together) Trim (Removes whitespace from string) Contains (Checks if one substring is contained in another) Split (Splits string into substrings)
Using a linked list	LinkedList<int> list = new LinkedList<int>(); list.AddLast(6); Retrieving a value is not as straight forward: list.First.Value or list.Last.Value Since inserting and removing elements is done by updating a couple references, they can be done in constant time. The trade-off is that accessing elements is no longer a constant time operation. In an array, with a given index an element can be instantly accessed. With a linked list, the references between nodes need to be followed until the desired element is found.
Using an ArrayList	ArrayList myArrayList = new ArrayList(); myArrayList.Add(56); myArrayList.Add("String"); myArrayList.Add(new Form()); The downside to the ArrayList data structure is one must cast the retrieved values back into their original type: int arrayListValue = (int)myArrayList[0];
Use of a hash table	Hashtable myTable = new Hashtable();
How to create a string	You can create string object using one of the following methods: By assigning a string literal to a String variable By using a String class constructor By using the string concatenation operator (+) By retrieving a property or calling a method that returns a string By calling a formatting method to convert a value or an object to its string representation
Use of stack	The Stack class is one of the many C# data structures that resembles a List. Like a List, a stack has an add and get method, with a slight difference in behaviour. To add to a stack data structure, you need to use the Push call, which is the Add equivalent of an List. Retrieving a value is slightly different. The stack has a Pop call, which returns and removes the last object added. If you want to check the top value in a Stack, use the Peek call. The resulting behaviour is what is called LIFO, which stands for Last-In-First-Out. This particular data structure is helpful when you need to retrace your steps so to speak. There are two formats to define a Stack in C#: Stack stack = new Stack(); Stack<string> stack = new Stack<string>(); The difference between the data structures being that the simple Stack structure will work with Objects while theStack<> one will accept only a specified object. Here is the C# code to add and traverse through a Stack data structure: Stack<string> stack = new Stack<string>(); stack.Push("1"); stack.Push("2"); stack.Push("3"); while (stack.Count
Use of Queue	Another one of the many C# data structures is the Queue. A Queue is very similar to the Stack data structure with one major difference. Rather than follow a LIFO behaviour, a Queue data structure goes by FIFO, which stands for First-In-First-Out. Whenever you submit an article to be approved on a website for example, the site adds your submission to a queue. That way the first objects added are the first ones to be processed. The Add call for a queue (or the Push version) is Enqueue: queue.Enqueue("1"); The Remove call is Dequeue: queue.Dequeue(); Similarly the Peek call allows you to view the top value without removing it. This specific data structure is very often used in conjucture with stack data structures. Here is some simple C# code to add items to a queue and the transverse it: Queue<string> queue = new Queue<string>(); queue.Enqueue("1"); queue.Enqueue("2"); queue.Enqueue("3"); while (queue.Count > 0) { MessageBox.Show(queue.Dequeue()); }

Next up

Description

Resource summary

Similar

	Created by Ruth Hyndman over 8 years ago