Overview of data structures

The following is a table providing an overview of some of the most common and advanced data structures, along with their advantages and disadvantages:

Table 1.2 – Overview of Data Structures

Data Structure	Advantages	Disadvantages
Array	Very fast access to elements if index is known, fast insertion of new elements.	Fixed size, slow deletion, slow search.
Sorted array	Quicker search over non-sorted arrays.	Fixed size, slow insertion, slow deletion.
Queue	Provides FIFO (First In, First Out) access.	Slow access to other elements.
Stack	Provides LIFO (Last In, First Out).	Slow access to other elements.
List	Quick inserts and deletes.	Slow search.
Hash table	Very fast access if key is known, quick inserts.	Slow access if key is unknown, slow deletes, inefficient memory usage.
Heap	Very fast inserts and deletes, fast access to largest or smallest item.	Slow access to other items.
Trie (pronounced Try)	Very fast access, no collisions of different keys, very fast inserts and deletes. Useful for storing a dictionary of strings or doing prefix searches.	Can be slower than hash tables in some cases.
Binary tree	Very fast inserts, deletes, and searching (for balanced trees).	Deletion algorithm can be complex, tree shape depends on the order of inserts and can become degraded.
Red-black tree	Very fast inserts, deletes, and searching, tree always remains balanced.	Complex to implement because of all the operation edge conditions.
R-tree	Good for representing spatial data, can support more than two dimensions.	Does not guarantee good worst-case performance historically.
Graph	Models real-world situations.	Some algorithms are slow and complex.

Overview of algorithms

In studying algorithms, we often concern ourselves with ensuring their stingy use of resources. The time and space needed to solve a problem are the two most common resources we consider.

	"Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output."
	--Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms 3rd Edition (2009)

Specifically, we're interested in the asymptotic behavior of functions describing resource use in terms of some measure of problem size. We'll take a closer look at asymptotic behavior later in this chapter. This behavior is often used as a basis for comparison between methods, where we prefer methods whose resource use grows slowly as a function of the problem size. This means we should be able to solve larger problems quicker.

The algorithms we'll discuss in this book apply directly to specific data structures. For most data structures, we'll need to know how to:

• Insert new data items
• Delete data items
• Find a specific data item(s)
• Iterate over all data items
• Perform sorting on data items