Introduction to Data Structures

C++

The C++ standard library data structures are designed to store any type of data. We put the desired data type within the <> brackets when declaring the data structure, as follows:

Copy
vector<string> v;

This creates a vector structure that only stores objects of type string.

For our examples below, we will primarily use the int data type, but note that you can use any data type including string and user-defined structures.

Nearly every standard library data structure supports the size() method, which returns the number of elements in the data structure, and the empty() method, which returns true if the data structure is empty, and false otherwise.

Java

Python

C++

Arrays

You already know one of the simplest data structures: the array! In C++11, in addition to normal arrays, there exists an array class in the STL. For example, an array of 25 ints can be initialized using the following line of code:

Copy
array<int, 25> arr;

The array class supports the normal STL operations (such as .empty() or .size()) as well as the normal square-bracket access operator:

Copy
arr[5]  // accesses the element at the 5th index

In C++, arrays initialized locally using either the default syntax (i.e. int arr[25]; ) or the array class are initialized to random numbers because C++ doesn't have built-in memory management. In order to initialize an array to zero, you have several options:

• Use a for loop (or nested for loops).
• Declare the array globally.
• Declare the array with an empty initializer list (i.e. int arr[25]{}; ) as mentioned here.
• Use a built-in function such as std::fill_n(arr, 25, 0) or std::fill(arr, arr+25, 0).

Dynamic Arrays

Dynamic arrays (vector in C++) support all the functions that a normal array does, and can resize itself to accommodate more elements. In a dynamic array, we can also add and delete elements at the end in $\mathcal{O}(1)$ time.

For example, the following code creates a dynamic array and adds the numbers $1$ through $10$ to it:

Copy
vector<int> v;
for (int i = 1; i <= 10; i++) { v.push_back(i); }

g++ will allow you to create an array of variable length:

Copy
int n;
cin >> n;
int v[n];

However, variable-length arrays are not part of the C++ standard. We recommend that you use a vector for this purpose instead:

Copy
vector<int> v(n);  // one way
vector<int> v;
v.resize(n);  // another way

In array-based contest problems, we'll use one-, two-, and three-dimensional static arrays much of the time. However, we can also have dynamic arrays of dynamic arrays (e.g. vector<vector<int>>) static arrays of dynamic arrays (e.g. array<vector<int>,5>), dynamic arrays of static arrays (e.g. vector<array<int,5>>), and so on.

Iterating

One way to iterate through all elements of a static or dynamic array is to use a regular for loop.

Copy
vector<int> v{1, 7, 4, 5, 2};
for (int i = 0; i < int(size(v)); i++) { cout << v[i] << " "; }
cout << endl;

We can also use iterators. An iterator allows you to traverse a container by pointing to an object within the container. However, they are not the same thing as pointers.

For example, v.begin() or begin(v) returns an iterator pointing to the first element of the vector v. Apart from the standard way of traversing a vector (by treating it as an array), you can also use iterators:

Copy
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
	cout << *it << " ";  // prints the values in the vector using the iterator
}

Here is another way to write this. auto (since C++11) automatically infers the type of an object:

Copy
vector<int> v{1, 7, 4, 5, 2};
for (auto it = begin(v); it != end(v); it = next(it)) {
	cout << *it << " ";  // prints the values in the vector using the iterator
}

We can also use a for-each loop.

Copy
for (int element : v) {
	cout << element << " ";  // prints the values in the vector
}

Inserting and Erasing

Keep in mind that insertion and erasure in the middle of a vector are $\mathcal{O}(n)$.

Copy
vector<int> v;
v.push_back(2);          // [2]
v.push_back(3);          // [2, 3]
v.push_back(7);          // [2, 3, 7]
v.push_back(5);          // [2, 3, 7, 5]
v[1] = 4;                // sets element at index 1 to 4 -> [2, 4, 7, 5]
v.erase(v.begin() + 1);  // removes element at index 1 -> [2, 7, 5]
// this remove method is O(n); to be avoided
v.push_back(8);        // [2, 7, 5, 8]
v.erase(v.end() - 1);  // [2, 7, 5]

Strings

You should be familiar with basic string manipulation techniques:

• Reading in strings from standard input
• Knowing how to use getline and cin together (more rare; refer to LCPP resource above)
• Knowing how to sort strings, concatenate strings, loop through a string's characters
• Get the ith character of a string
• Know how to get substrings with string::substr

Java

Arrays

Java default Collections data structures are designed to store any type of object. However, we usually want our data structures to only store one type of data, like integers or strings. We do this by putting the desired data type within the <> brackets when declaring the data structure, as follows:

Copy
ArrayList<String> list = new ArrayList<String>();

This creates an ArrayList structure that only stores objects of type String.

For our examples below, we will primarily use the Integer data type, but note that you can have Collections of any object type, including Strings, other Collections, or user-defined objects.

Collections data types always contain an add method for adding an element to the collection, and a remove method which removes and returns a certain element from the collection. They also support the size() method, which returns the number of elements in the data structure, and the isEmpty() method, which returns true if the data structure is empty, and false otherwise.

Dynamic Arrays

Dynamic arrays (ArrayList in Java) that support all the functions that a normal array does, and can repeatedly reallocate storage to accommodate more elements as they are added.

In a dynamic array, we can also add and delete elements at the end in $\mathcal{O}(1)$ time. For example, the following code creates a dynamic array and adds the numbers $1$ through $10$ to it:

Copy
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 1; i <= 10; i++) { list.add(i); }

In array-based contest problems, we'll use one-, two-, and three-dimensional static arrays most of the time. However, we can also have static arrays of dynamic arrays, dynamic arrays of static arrays, and so on. Usually, the choice between a static array and a dynamic array is just personal preference.

Iterating

To iterate through a static or dynamic array, we can use either the regular for loop or the for-each loop.

Copy
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(7);
list.add(4);
list.add(5);
list.add(2);
int[] arr = {1, 7, 4, 5, 2};
for (int i = 0; i < list.size(); i++) {  // regular
	System.out.println(list.get(i));
}
for (int element : arr) {  // for-each
	System.out.println(element);
}

Adding and Removing

We can add and remove at any index of a dynamic array in $\mathcal{O}(n)$ time.

Copy
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(2);     // [2]
list.add(3);     // [2, 3]
list.add(7);     // [2, 3, 7]
list.add(5);     // [2, 3, 7, 5]
list.set(1, 4);  // sets element at index 1 to 4 -> [2, 4, 7, 5]
list.remove(1);  // removes element at index 1 -> [2, 7, 5]
// this remove method is O(n); to be avoided
list.add(8);                   // [2, 7, 5, 8]
list.remove(list.size() - 1);  // [2, 7, 5]
// here, we remove the element from the end of the list; this is O(1)
System.out.println(list.get(2));  // 5

Python

Lists

The default way to store data in Python is using a list, which can automatically resize itself to accommodate more elements. We can add and delete elements at the end in $\mathcal{O}(1)$ time. A list can be initialized as follows:

Copy
arr = []

Python lists are generic. This means that they can store any kind of data type, including objects. For example, the following code creates a dynamic array and adds the numbers $1$ through $10$ to it:

Copy
for i in range(1, 11):  # Note that range(i, j) includes i, but does not include j
	arr.append(i)

In Python, we can give a dynamic array an initial size. The code below creates a dynamic array with $30$ zeroes.

Copy
arr = [0] * 30

Iterating

We can use a regular for loop to iterate through all elements of a list.

Copy
arr = [1, 7, 4, 5, 2]

for i in range(len(arr)):
	print(arr[i], end=" ")
print()

for element in arr:
	print(element, end=" ")
print()

We can also use iterators. An iterator allows you to traverse a container by pointing to an object within the container. iter(arr) returns an iterator pointing to the first element of the list arr.

Copy
arr = [4, 2, 0, 0, 5]
it = iter(arr)

print(next(it))  # 4
print(next(it))  # 2
print(next(it))  # 0

Inserting and Erasing

Copy
arr = []
arr.append(2)  # [2]
arr.append(3)  # [2, 3]
arr.append(7)  # [2, 3, 7]
arr.append(5)  # [2, 3, 7, 5]
arr[1] = 4
# sets element at index 1 to 4 -> [2, 4, 7, 5]
arr.pop(1)  # removes element at index 1 -> [2, 7, 5]
# this remove method is O(n); to be avoided
arr.append(8)  # [2, 7, 5, 8]

List Comprehensions

List comprehensions are extremely useful for simplifying a python for loop that modifies/creates a list into one expression. The general syntax is: [ expression for item in list if conditional ]

An example is provided in the code block below.

Copy
# If a number is odd, add the number times 2 into the array
old_list = [2, 5, 3, 1, 6]
new_list = []
for i in old_list:
	if i % 2 == 1:
		new_list.append(i * 2)
print(new_list)  # [10, 6, 2]
# Simplified one liner with list comprehension
# Recall the form [ expression for item in list if conditional ]
# expression: i * 2
# list: old_list
# conditional: i % 2 == 1 (only include item i if it satisfies the conditional)
new_list = [i * 2 for i in old_list if i % 2 == 1]
print(new_list)  # [10, 6, 2]

A very applicable use of list comprehensions for competitive programming in particular is creating an integer list from space separated input:

Copy
# Example input: 5 3 2 6 8 1
# Note that the conditional in the list comprehension is optional, and defaults to True if not provided
arr = [int(x) for x in input().split()]
print(arr)  # [5, 3, 2, 6, 8, 1]

For more information on list comprehensions, including nesting them to create multidimensional lists, refer to the below resources.

C++

Of course, both vector<vector<int>> and vector<array<int,2>> would suffice for this case, but a pair can also store two elements of different types.

C++ Pairs

• pair<type1, type2> p: Creates a pair p with two elements with the first one being of type1 and the second one being of type2.
• make_pair(a, b): Returns a pair with values a, b.
• {a, b}: With C++11 and above, this can be used as to create a pair, which is easier to write than make_pair(a, b).
• pair.first: The first value of the pair.
• pair.second: The second value of the pair.

Example:

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	pair<string, int> myPair1 = make_pair("Testing", 123);
	cout << myPair1.first << " " << myPair1.second << endl;
	myPair1.first = "It is possible to edit pairs after declaring them";
	cout << myPair1.first << " " << myPair1.second << endl;
	pair<string, string> myPair2 = {"Testing", "curly braces"};
	cout << myPair2.first << " " << myPair2.second << endl;

C++ Tuples

Of course, we can hold more than two values with something like pair<int,pair<int,int>>, but it gets messy when you need a lot of elements. In this case, using tuples might be more convenient.

• tuple<type1, type2, ..., typeN> t: Creates a tuple with N elements, i'th one being of typei.
• make_tuple(a, b, c, ..., d): Returns a tuple with values written in the brackets.
• get<i>(t): Returns the i'th element of the tuple t. Can also be used to change the element of a tuple.

This operation only works for constant i. Namely, it is not allowed to do something like the following since i is not constant:

Copy
tuple<int, int, int> t{3, 4, 5};
int i = 1;
cout << get<i>(t);

• tie(a, b, c, ..., d) = t: Assigns a, b, c, ..., d to the elements of the tuple $t$ accordingly.

Example:

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int a = 3, b = 4, c = 5;
	tuple<int, int, int> t = tie(a, b, c);
	cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;
	get<0>(t) = 7;
	cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;

Java

We can create our own generic Pair class in Java:

Copy
static class Pair<K, V> {
	K first;
	V second;

	public Pair(K first_value, V second_value) {
		first = first_value;
		second = second_value;
	}
}

Then, we can use the Pair class as follows:

Copy
Pair<Integer, String> p = new Pair(5, "hello");
System.out.println(p.first + " " + p.second);

Python

Python Tuples

Use the link below (if you know of a better one, please let us know!) to learn about tuples.

C++

Java

Python

len(l)

count(l)

size(l)

l.length()