Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C# (http://www.go4expert.com/articles/c-sharp-tutorials/)
-   -   Lists, Queues, Stacks & Sets in C# (http://www.go4expert.com/articles/lists-queues-stacks-sets-c-sharp-t30028/)

shabbir 21Mar2014 15:01

Lists, Queues, Stacks & Sets in C#
 
In almost every software application, you need to handle a list of data of any type. The list can contain, users registered on the website, the list of items purchased by the user or the list of items that have been sold and so on and so forth. In order to handle lists of data we have data structures such as arrays and linked lists etc. But they are limited in capability. Managing data in the list is much more than simple insertion, deletion and searching functionalities provided by an ordinary array. .NET framework contains special namespaces and types that can be used for storing collection of data in the form of lists. The two major namespaces that contain collections are System.Collections and System.Collections.Generic namespaces where former contain the ordinary collection types and the latter contain strongly typed collections. The generic collections are far more superior in terms of capabilities and flexibility when compared with their non-generic counterparts. Almost all of these collections implement the collection interfaces which have been explained in detail in previous articles. Today, we will discuss some of these collection and we will see how they can be leveraged to store and manipulate collections of data. You will see that how these collections can be used to store data in the form of Lists, Queues, Stacks and Sets. So let us begin with our firs collections.

List<T> & ArrayList



These are the most widely used collections owing to their maximum capabilities by virtue of implement the IList & IList<T> interfaces. We described in our previous articles that IList<T> & IList interfaces have maximum capabilities of all the collection interfaces. Therefore the collections that implement these interfaces arguably contain maximum capabilities. The ArrayList collection implements the IList interface only, whereas the List<T> collection implements IList<T> IReadOnlyList<T> and finally the IList interface. Both IList<T> and ArrayList collection allows to create an array of data of dynamic size. An important thing to note here is that these collections are ordinary classes that actually implement collection interfaces. You can also write similar collection classes yourself according to your requirements.

Internally what happens is that List<T> and ArrayList contains an array of object. When this array is filled and reaches its capacity, a new array with larger size is created and the items are copied into that array. The operations where items are to be added at the end of the list are fastest because most of the time, a free slot is available at the end of the array. However, inserting an element in between an array is slow because all the elements after the insertion point will have to be shifted forward to create a slot for the new element at the insertion point. Now, with the help of a working example, we will explain salient functionalities of the List<T class>. We have used List<T> class when we explained the IList interface but in upcoming example, we are going to explain in detail, more exciting features of the List<T> class. Have a look at the Example1.

Example1

Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
namespace CSharpTutorial {
    class Program {
        public static void Main() {
            List<string> cars = new List<string> {
                "Honda", "Mercedez", "BMW"
            }
            ;
            cars.Add("Suzuki");
            cars.AddRange(new[] {
                "Ford", "Audi", "Cameri"
            }
            );
            cars.Insert(0, "Toyota");
            cars.InsertRange(0, new[] {
                "Cuore", "Lexus", "Safari"
            }
            );
            IEnumerator enumer = cars.GetEnumerator();
            int i = 0;
            while(enumer.MoveNext()) {
                i++;
                Console.WriteLine(i+ "-"+ enumer.Current);
            }
            cars.Remove("Audi");
            cars.RemoveAt(2);
            cars.RemoveRange(0, 2);
            cars.RemoveAll(c => c.StartsWith("c", true,System.Globalization.CultureInfo.InvariantCulture));
            i = 0;
            enumer = cars.GetEnumerator();
            Console.WriteLine("\n*****************\n");
            while(enumer.MoveNext()) {
                i++;
                Console.WriteLine(i+ "-"+ enumer.Current);
            }
            Console.WriteLine("\n*****************\n");
            Console.WriteLine(cars[4]);
            Console.WriteLine(cars[cars.Count - 1]);
            List<string> carsubset = cars.GetRange(0, 3);
            string [] cararray = cars.ToArray();
            i = 0;
            Console.WriteLine("\n*****************\n");
            foreach (string car in cararray) {
                i++;
                Console.WriteLine(i+"-"+car);
            }
            Console.ReadLine();
        }
    }
}

Now, pay attention to the code in Example1. Here we have a List<strings> type collection class which we have named ‘cars’. We have initialized this collection with three car names using this line.
Code:

List<string> cars = new List<string> { "Honda", "Mercedez", "BMW"};
This way you can add items into a collection by default while initializing it, apart from adding items using Add() method which we have done in the next lines where first we called a simple Add() method and passed it a string. Then we called AddRange() method that takes an array of elements and append them at the end of the collection on which this method is called. Same is the case with insertion where Insert(index, item) would add one item at the specified index and InsertRange(index, array of elements ) would insert they array of elements starting from the specified index.

In the next lines we have simply iterated upon the ‘cars’ collection to display the cars that are currently in the collection.

Then, we have written three remove methods. The first one is simple Remove(object) method that takes the object to remove as parameter. The second method is RemoveAt(index) method that takes the index from which we want to remove the item and lastly the RemoveRange(index, number of elements) method takes two parameters. First one is the index from which we want to start removing the items and the second one is the number of elements that should be removed starting from the specified index. A

An interesting method is RemoveAll() which takes a lambda expression to specify which elements to be removed. We have removed all the cars starting with “c” using c=> c.StartsWith(“c”, true, CultureInfo.InvariantCulture), where the first element is string which specifies the strings to be removed that start with it, the second one is the bool IgnoreCase which we have set to true and then the CultureInfo which we set to invariant info.

After removing these items, we have again iterated on the ‘cars’ collection. We displayed the elements in the car collection and you will see that it will not contain the elements that we removed.

After iterations, we showed that how we can get an element by index. We did that in these lines where we printed the element based on the index.
Code:

Console.WriteLine(cars[4]);
Console.WriteLine(cars[cars.Count - 1]);

We can also get a subset of collection from a collection which will also be a collection. This is done via a GetRange() method which takes two parameters: first one is the index of the first element and the second parameter is the number of elements from the starting index.

We then, called ToArray() method on the cars collection which will return an array of elements. We stored this array in “cararray” and then again iterated on this array. You will see that it will have same result as the cars collection. It shows that ToArray() method successfully converted the cars collection into array.

The output of the code in Example1 is as follows:

Output1

http://imgs.g4estatic.com/c-sharp/li...ts/output1.png

Now come towards the ArrayList. Basically this class is used only for backward compatibility with the older versions of .NET framework which used non-generic collections. These collections were not type-safe as we would see in our next example. Have a look at Example2.

Example2

Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
namespace CSharpTutorial {
    class Program {
        public static void Main() {
            ArrayList arr = new ArrayList();
            arr.Add("john");
            arr.Add("mike");
            string[] sarr = (string[])arr.ToArray(typeof(string));
            foreach (string str in sarr) {
                Console.WriteLine(str);
            }
            int num =(int) arr[0];
            Console.ReadLine();
        }
    }
}

The code in Example2 is straightforward; here we have an ArrayList object ‘arr’ in which we added two string values. We then called ToArray method to convert into string type array by passing string type into ToArray() method and then casting it into a string array. Then, using foreach loop, the elements in the ‘sarr’ have been displayed.

Next line is very important and it explains that why generic collections are preferred over the non-generic collections. Consider this line of code:

Code:

int num =(int) arr[0];
The element at the 0th index of the ArrayList ‘arr’ is a string but in the above line we are casting it into an int. At compile time, no error will be generated, but at runtime an exception will occur. This is due to the reason that compiler didn’t know the type of the elements in the ArrayList because it is non-generic collection where we don’t have to specify the types. It is due to this reason, we use generic collection so that these casting exceptions can be handled at compile time and our code remains type-safe. The output of the code will be as follows.

Output2

http://imgs.g4estatic.com/c-sharp/li...ts/output2.png

You can see in the output that InvalidCastException has occurred on the line where we are casting the first element of ‘arr’ into an integer.

LinkedList<T>



Another extremely important collection that is often very useful while storing a list of data is the LinkedList<T> collection. As the name suggests, LinkedList<T> stores data in the form of a famous linked list data structure. In fact, LinkedList<T> is a doubly linked list where each node actually contains three elements: the reference of the previous node, the reference of the next node in the list and the element stored at the node itself. In .NET framework, LinkedList<T> belongs to the System.Collections.Generic namespace and implements ICollection<T> and IEnumerable<T> interfaces along with their non-generic counterparts. The IList<T> interface is not implemented by the LinkedList<T> class because index functions are not supported by the linked list. In our next example, we will explain that how LinkedList<T> class can be used to store collection of elements in the form of linked list. Have a look at our next example.

Example3
Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

namespace CSharpTutorial
{
    class Program
    {
        public static void Main()
        {
            LinkedList<string> cars = new LinkedList<string> { };

            cars.AddFirst("Toyota"); // cars = Toyota
            cars.AddLast ("Honda"); // cars = Toyota Honda
            cars.AddAfter(cars.First, "Suzuki"); // cars = Toyata Suzuki Honda;
            cars.AddAfter(cars.First.Next, "Audi"); // cars = Toyota Suzuki Audi Honda;
            cars.AddBefore(cars.Last.Previous, "BMW"); // cars = Toyota Suzuki BMW Audi Honda;

            foreach (string s in cars)
            {
                Console.Write(s + " .");
            }

            cars.Remove("BMW"); // cars = Toyota Suzuki Audi Honda
            cars.RemoveFirst(); // cars = Suzuki Audi Honda
            cars.RemoveLast();  // cars = Suzuki Audi
            Console.WriteLine("\n\n********************************\n");

            foreach (string s in cars)
            {
                Console.Write(s + " .");
            }

            LinkedListNode<string> snode = cars.Find("Audi");
            cars.Remove(snode);
            cars.AddFirst(snode);

            Console.WriteLine("\n\n*************\n");

            foreach (string s in cars)
            {
                Console.Write(s + " .");
            }
            Console.ReadLine();
        }
    }
}

Before dwelling into the code in Example3, first bear in mind that you cannot simply add the elements in a LinkedList<T>, by providing an index. You can add elements in the LinkedList<T> in three ways: You can add the elements in the start; you can add elements at the end or you can add elements relative to the other elements.

Now, come towards Example3, here we have a LinkedList<string> class that we have named ‘cars’ and this class will hold car names strings in it. We first called AddFirst() on the cars collection and passed it string “Toyota”; this will be the first node. We then called AddLast() and passed it “Honda”; this will be the last node.

Then we called AddAfter() on cars, this method takes two parameters, the first one is the node after which you want to add the element and the second parameter is the element itself. We passed it “Cars.First” as the first parameter and “Suzuki” as the second, telling it that it should add the node “Suzuki” after the node “Toyota” which is the first node.

After that we again called AddAfter() on cars, this method. We passed it “Cars.First.Next” as the first parameter and “Audi” as the second parameter, telling it that it should add the node “Audi” after the next of the first node, which would be “Suzuki”. So the “Audi” would be added after “Suzuki”.

Similarly, we called the AddBefore() method on cars and it again takes the node before which we want to add new node, as the first parameter and the second parameter is the element. We passed it “Cars.Last.Previous” as the first parameter “BMW” as the second parameter. It will add “BMW” before the previous node from the last node i.e. “BMW” would be added before the “Audi” node. The resulting cars collection would have nodes in this sequence: “Toyota Suzuki BMW Audi Honda”. We have then displayed the items in the cars collection using foreach loop.

Next, we have removed item from the cars list thrice. First we called simple Remove() method and passed it the item to be removed i.e. “BMW” which will be removed from the list. Then we called RemoveFirst() and RemoveLast() methods respectively which would result in removing first and last element of the cars collection, respectively. Now the elements, “Toyota” and “Honda” would also be removed from the list and we would be left with two items only i.e. “Suzuki” and “Audi”. We have again iterated on the cars collection to confirm that whether elements have been removed or not.

Pay attention on the next line of code i.e.
Code:

LinkedListNode<string> snode = cars.Find("Audi");
Here LinkedListNode<T> is a class that can store one node from the collection of nodes in LinkedList<T> collections. Here we have called Find() method on ‘cars’ collection and have passed “Audi” as a parameter. This method would return the node that contains “Audi”. We stored this node in LinkedListNode<string> instance which we named ‘snode’.

After getting a node using the Find() method, we will first remove that node from the “cars” collection. Now we will be left with only one node in the linked list i.e “Suzuki”. Then we again called the AddFirst() method on the car collection and will pass it the “snode” which will insert the element ”Audi” at the first place. Now the ‘cars’ collection would contain 2 nodes i.e “Audi” “Suzuki”. At the end of Example3, we again iterated upon the ‘cars’ collection and displayed its nodes. The output of the code in Example3 is as follows.

Output3

http://imgs.g4estatic.com/c-sharp/li...ts/output3.png

Queue <T> and Queue



If you have got slightest idea of data structures, then you must know what a queue is. A queue is basically a linear data structure that stores data and retrieves data following the FIFO (First In, First Out) principle. In a queue a new node is added at the tail of the queue via an Enqueue method. In order to retrieve as well as remove data, you can call Dequeue method which will return the element at the head of the queue and will remove it as well. If you want the queue to only return the header element, without removing it, you can use Peek method.

In order to implement queues in your applications, .NET Framework provides generic Queue<T> & non-generic Queue classes. The Queue<T> class implements, IEnumerable <T>, IEnumerable and ICollection interfaces. Like LinkedList<T>, Queue<T> doesn’t implement the IList<T> and IList interface due to the reason that index operations are not supported by queues.

Now, as always, let us explain Queue<T> class with the help of a working example. Have a look at Example4.

Example4

Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

namespace CSharpTutorial
{
    class Program
    {
        public static void Main()
        {
            Queue<string> cars = new Queue<string> { };

            cars.Enqueue("toyota");
            cars.Enqueue("honda");
            cars.Enqueue("Suzuki");

            Console.WriteLine(cars.Peek());
            cars.Dequeue();
            Console.WriteLine(cars.Peek());
            cars.Dequeue();
            Console.WriteLine(cars.Peek());
            Console.ReadLine();
        }
    }
}

The code in Example4 is probably the most straight-forward of all the previous examples. Like our previous examples, we have created a Queue<string> class which we named car. We then called Enqueue() method on this ‘cars’ collection thrice and passed values “toyota”, “honda” and “Suzuki” respectively. The queue cars would contain string “toyota“ at head, “honda” in the middle and “Suzuki” at the tail.

We then called Peek() method on ‘cars’ which would return us the element at the head of the queue which is ‘toyota’ at the moment; we displayed this to the user console. Next we called Dequeue() method which would remove the element from the head. We then again called Peek() method and this time it will return us “honda” because after “toyota” is removed from the head, the next element at the head will be “honda”. We then again repeat the same procedure and next time the element at head will be “Suzuki” which we have displayed in the output. The output of the code in Example4 is as follows

Output4

http://imgs.g4estatic.com/c-sharp/li...ts/output4.png

Stack<T> & Stack



Another extremely important data structure is the stack, which works on the principle of LIFO (Last in first out). Usually a stack has a push method which stores the data on the top of a stack and a pop method which retrieves the last inserted element from the top of the stack. Like Queue<T>, Stack<T> also contains a Peek () method as well as count property that returns the element in stack. And lastly, Stack<T> also contains ToArray() method which converts the stack into array of elements. Another similarity between Queue<T> and Stack<T> is that Stack<T> also implements IEnumerable<T>, IEnumerable<> and ICollection interface as implemented by the Queue<T> class.

To have an insight of how Stack<T> class actually works, have a look at our 5th example.

Example5

Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

namespace CSharpTutorial
{
    class Program
    {
        public static void Main()
        {
            Stack<string> cars = new Stack<string> { };

            cars.Push("Toyota");
            cars.Push("Honda");
            cars.Push("Suzuki");

            Console.WriteLine(cars.Count);
            Console.WriteLine(cars.Peek());
            cars.Pop();
            Console.WriteLine(cars.Peek());
            cars.Pop();
            Console.WriteLine(cars.Peek());
            Console.ReadLine();
        }
    }
}

The code in Example5 will look quite similar to one in Example4 but is actually reverse in terms of functionality. Here we have a ‘Stack<string> cars’ collection class. We inserted three elements in this stack using Push() method to which we passed “Toyota”, “Honda” and “Suzuki” strings. In case of Queue<T> Toyota would be stored at the head, followed by Honda and Suzuki. But here in case of Stack<T>, Toyota would be stored at the bottom, on top of it, Honda and on top of Honda, Suzuki would be stored. The last item inserted would be on top.

We then displayed the number of elements in the ‘cars’ stack using Count property and then we called Peek() method on car to display the item on top of the stack which would be “Suzuki”. Next we called Pop method which would remove the item from the top of the stack, thus “Suzuki” would be removed. Now when we call the Peek() method, it will return “Honda” because now Honda would be on top of the stack. Next, we again called Pop and then Peek() which will return “Toyota” which would be the only element left in the ‘cars’ stack. The output of the code in Example5 is as follows.

Output5

http://imgs.g4estatic.com/c-sharp/li...ts/output5.png

SortedSet<T> & HashSet<T>



Another relatively new but important collection classes are the SortedSet<T> and HashSet<T>. Both of these classes are generic collection and belong to System.Collections.Generic namespace. SortedSet<T> class was introduced in .NET Framework 4.0 whereas HashSet<T> was introduced in 3.5. Good thing about these classes is that their Contains method is extremely quick owing to the fact that these classes use hash-based lookup technique for searching. However, elements in these classes cannot be accessed via indexing and it is for this reason that these classes do not implement IList interfaces. Another very important thing to note is that these classes do not store duplicate elements. So if you store an element that is already present in the collection, that element will be silently ignored. Finally, HashSet<T> does not store elements in an order whereas SortedSet<T> as the name suggests, store elements in a particular order. Now as we have done previously, we will explain with the help of examples, how HashSet<T> and SortedSet<T> can be implemented in applications. First have a look at Example6 for the implementation of HashSet<T>.

Example6
Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

namespace CSharpTutorial
{
    class Program
    {
        public static void Main()
        {
            HashSet<string> cars = new HashSet<string> { "Toyota", "Honda", "Audi"};

            cars.Add("Toyota");

            foreach (string s in cars)
            {
                Console.WriteLine(s);
            }

            Console.WriteLine("\n*******************\n");
            Console.WriteLine(cars.Contains("Toyota"));
            Console.WriteLine(cars.Contains("Suzuki"));

            string [] arr = new string []{"Toyota","Audi"};
            cars.IntersectWith(arr);

            Console.WriteLine("\n*******************\n");
            foreach (string s in cars)
            {
                Console.WriteLine(s);
            }

            arr = new string[] { "Honda" };
            cars.UnionWith(arr);
            Console.WriteLine("\n*******************\n");
            foreach (string s in cars)
            {
                Console.WriteLine(s);
            }

            arr = new string[] { "Toyota" };
            cars.ExceptWith(arr);

            Console.WriteLine("\n*******************\n");
            foreach (string s in cars)
            {
                Console.WriteLine(s);
            }

            cars.SymmetricExceptWith(new string[]{"Honda"});
            Console.WriteLine("\n*******************\n");
            foreach (string s in cars)
            {
                Console.WriteLine(s);
            }
            Console.ReadLine();
        }
    }
}

Pay attention to the code in Example1, here we have a declared a HashSet<string> class which we named car and have initialized it with three values. Note, we can initialize the HashSet<T> class during declaration because it implements ICollection interface which allows us to call Add() method on this class. We stored three values during declaration i.e “Toyota”,” Honda” and “Audi”. We then again added an item “Toyota” in the cars collection via the Add() method and then we traversed the collection. You will see that although “Toyota” was added twice in the collection: once during declaration and once by calling the Add() method but when you traversed the collection it displayed it only once. It is due to the reason that we mentioned earlier that duplicate items are ignored by this collection.

Next we called Contains() method and passed it “Toyota” and “Suzuki”, which would return True and False respectively.

The following lines of code are extremely interesting. We called IntersectWith() method on the cars collection and passed it string array arr which contains “Toyota” and “Audi”. The IntersectWith() method compares the collection with collection of elements passed to it and returns the items that are common between the two collections. Therefore, the cars collection would now contain “Toyota” and “Audi” because they were common. In order to confirm that, we iterated on the cars collection and displayed its item.

The next method is the UnionWith() which perform the union operation on two collections returning one collection containing union of the two. We passed a string array arr which now contains “Honda” and passed it to UnionWith method of the car collection. The cars collection already contains “Toyota” and “Audi” so the returned collection would now contain “Toyota”, “Honda” and “Audi”, which we displayed again by iterating on the collection.

In the following lines, we first used ExceptWith() method which would return the collection with all the elements except the element that is passed in the ExceptWith() method. We have passed an array containing only element “Toyota” to the ExceptWith() method of cars collection which will return collection including all elements except “Toyota”. We again displayed the result on the output screen. Similarly, the SymmetricExceptWith() method is used to get elements that are unique to both the collection. For example if one collection has element ”Toyota, Honda & Suzuki” and the other collection has elements “Toyota, Audi and Suzuki” then the elements Honda & Audi would be returned because Toyota & Suzuki are present in both of the collections.

The output of the code in Example6 is as follows.

Output6

http://imgs.g4estatic.com/c-sharp/li...ts/output6.png

SortedSet<T>, like HashSet<T> also implements the ICollection interface and items can be added during declaration as well as they can be added via a AddMethod(). SortedSet<T> contains elements in sorted order. In order to see this behavior, yourself, consider our next example. Have a look at Example7.

Example7
Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

namespace CSharpTutorial
{
    class Program
    {
        public static void Main()
        {
            SortedSet<string> cars = new SortedSet<string> { "Toyota", "Audi", "Honda", "Camery" };

            foreach (string s in cars)
            {
                Console.WriteLine(s);
            }
            Console.ReadLine();
        }
    }
}

The code in Example7 is pretty simple. We have a SortedSet<string> class which we named cars and have initialized this class with three values Toyota, Audi, Honda and Camera. We then iterated upon the cars collection. You will see an interesting output. Though, you have inserted items in the order Toyota, Audi, Honda and Camery, the output would be in the form Audi, Camery, Honda and Toyota. The reason is that SortedSet<string> cars collection stores elements in sorted order and since Audi starts with ‘A’ it is at the start and Toyota starts with ‘T’ it is sorted and placed at the end. The output of Example7 is as follows.

Output7

http://imgs.g4estatic.com/c-sharp/li...ts/output7.png


All times are GMT +5.5. The time now is 20:21.