Introduction to Collections

What is a collection?

What's the first thing that comes to your mind when you hear 'collection'? Right, a group of something. Collection is a data structure that can store a group of data values. Languages provide many such Collections (each implementing the features of a specific data structure) as a library. You can readily use any of these Collections to create an instance of the required data structure and do various operation on it - insert, update delete, search, sort etc.
This way, you don't have to worry about implementing different data structures from scratch and focus on the logic to solve the problem.

Very inspiring, give me an example.

Suppose you want to store elements such that you're able to retrieve the last stored element in constant time, without knowing the index. With a normal array, it's hard. With collections, all you have to do is use a data structure known as a stack, wherein you can store elements as a 'stack', (think of it as a stack of bread, or a stack of papers). To remove the topmost element, all you have to do is pick it up. And this stack structure provides a method that allows you to retrieve that topmost/most recently added element immediately, without knowing the index or the total number of elements there are in the stack.

Okay, but I could create an array and tweak it a little to have the same functionality myself, no?

Sure you could. But how many times would you do it? If you're an enterprise level developer and regularly work with stacks and other data structures, would you set about implementing the stack as an array every time? That's where these inbuilt collections provide ready made structures and methods to ease your life.

I am impressed. Give me some more examples.

Stack is one such collection. There's another one called queue, which, like the name suggests, looks like a queue for getting tickets. The first person who entered the queue, gets out first. Queue is a structure that provides methods to ensure that the first element can be retrieved in constant time and the queue resizes itself when that happens.

Another one is called a priority queue, which is a queue, but with the elements sorted on the basis of a predefined priority. For instance, a queue in height order, as you used to do in school. A shorter person comes to the front of the queue, a tall one to the back.

Another important one is called a hashtable or a map, or a dictionary in Python, which is a set of key: value pairs. This is very useful in creating mappings between a character and its occurrences and so on.

Cool, how do I use these?

They are usually present in libraries or modules in these languages. You'd need to import these libraries in your code to be able to use them. Standard Template Library is used to refer to all such pre-defined pieces in C++. Python and Java have modules/libraries called Collections.

Talk is cheap - show me the code

C++

// C++ stack

// Importing the library which has the stack collection

#include<bits/stdc++.h>

// Defining the stack - notice the data type

stack<int> my_stack;

// Adding a value to stack

my_stack.push(21);

Java

// Java Stack

import java.util.Stack

Stack myStack= new Stack<>();

myStack.push(78);

Python

// Python Stack

my_stack = []

my_stack.append(78)

my_stack.pop()

Some points to keep in mind

1. Syntax and implementations of collections differs across programming languages, so make sure you understand and remember the syntax in at least one language. You can use the library documentation to find the methods. IDEs allow auto-complete to show methods available.

2. Carefully note the time complexities of the methods for collections, such as searching for a key in a map, popping element off a stack and so on, since they're interview favorites.

3. It is not necessary to know about all the collections and methods that exist, since there are many. You only need to know the important ones which have been addressed in the Crio curriculum. The others can be learned/looked up on a use-case basis.

Some good resources on collections

Note that collections are a language specific topic - each language will have a specific implementation. Here we list some general resources to get started on collections with each language. More resources will be given for each problem, when you get to the Collection related problems on the Crio platform.

Javascript

Note that Javascript does not have built in collections for DS like Stack, Queue or Priority Queue. These are to be implemented as custom classes. It does, however, provide implementations for Map and Set

Python

Python doesn't have implementations for Stack, queue, priority queue and so on. These are implemented using some of the existing data structures like deque, from the collections library.