Introduction to Data Structures

Data Structures

A data structure is a scheme for storing data in an organized way that allows the data to be used efficiently.

So far most of you have probably used one data structure for most things: the array (or ArrayList). Arrays are good for many tasks, but there are some things arrays are quite poor at.

In this class, we will learn data structures that solve a variety of problems, such as:

• Quickly inserting into, or removing from, the middle of our data.
• Keeping the data in a specific order based on when it was added to the structure.
• Keeping the data in a specific order based on the values of the elements.
• Being able to search for data as efficiently as possible.
• Storing relationships between data elements.
• Storing data using as little memory space as possible.
• Being able to test whether an element is in the data structure as quickly as possible.

You could use arrays for solving these problems, but using the best data structure for the job will do two things:

1. They will make your programs more efficient (sometimes by a lot).
2. They will make your programs simpler and more natural to write.

Algorithms

An algorithm is a step-by-step procedure for solving some problem, or accomplishing some task.

There are several basic operations that are supported by most data structures:

• Insertion: adding an element.
• Removal: removing an element.
• Search: finding a particular element.
• Traversing: looping through each element.

Each of the data structures we look at will have a different algorithm for accomplishing each of these tasks. So we will learn many different algorithms in this class. Some of these are simple and some are more complex.

We will also learn many algorithms that operate on the different data structures we use, as examples of when the data structure will come in handy.

And finally, we will talk about algorithms independent of any data structures. It turns out that most algorithms can be categorized into one of several categories based on the ways they work. Learning to recognize which type of algorithm can be used to solve various problems is very helpful as a programmer.

Algorithm Analysis

Another important aspect of this course is algorithm analysis which is the study of how efficient an algorithm is. Whenever we come up with algorithms in this class, we will analyze them to see how efficient they are. You might think that this will involve running programs, but algorithm analysis is actually done without actually needing to run a program, or even code it.

Algorithm analysis will let us talk about and compare algorithms without needing to get down to specifics, like what language we are using or what type of computer we are running it on. Being able to determine the efficiency of an algorithm is important in choosing what data structures and algorithms are best for a particular task.

The Importance of Data Structures

Knowing and being able to use data structures effectively is the biggest thing that sets really good programmers apart.

• "I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships." — Linus Torvalds
• "Smart data structures and dumb code works a lot better than the other way around." — Eric S. Raymond
• "Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming." — Rob Pike

The goal of this course is to give you the knowledge of how various data structures work, what problems they are good at solving, and the ability to use them in programs.