Welcome to Programming and Data Structures

The term data structure refers to a system for organizing and storing data in a computer. We are already quite familiar with one data structure - the vector. Vectors are objects that store a set of data elements that can be accessed via an index. But there are other ways to organize data. A stack is a data structure that stores a set of data elements in a way that only gives us access to the most recently added element. A map is a data structure that associates keys with values, allowing us to create a mapping from one set of elements (like "OR" and "CA") and to elements in another set (like "Oregon" and "California").

In previous chapters, we learned how to create a fixed sized block of memory in the form of a C-style array (Section 22.8) as well as how to work with pointers (Section 18.2). At a low level, those are the only two building blocks available for building data structures. We can allocate a block of memory to hold data and we can use pointers to track that memory. Every data structure is essentially a combination of these two elements.

For example, a vector is typically implemented as a single block of memory (an array) that is tracked by a pointer. When we insert values into a vector, they are added to the next available location in that block of memory. When the block of memory is full, a new larger block of memory is allocated, the data is shifted to that block, and the vector updates its pointer to track that new block.

The generic name for this kind of data structure is an array-based list or array list. A list is a structure that allows us to add (and remove) an arbitrary number of items that are accessed via their index. In a list, we identify the elements as item 0, item 1, item 2, and so on. An array list is a list that is implemented using an array. The C++ vector is an example of an array list.

In the next few sections, we will be building an ArrayList data structure. Our class will essentially be a simplified version of the C++ vector class. Normally, programmers would not bother writing their own version of a standard library class. The code in vector is highly optimized and tested, making it a reliable choice for most applications. There are however times when a programmer needs a specialized version of a standard structure, or is programming in an environment where the standard library is not available. In those situations, writing a custom data structure may be called for.

Another good reason to write a custom version is to develop a deeper understanding of how a given data structure actually works. That is why we will be building our own ArrayList. Understanding the code behind something like vector will equip us to analyze the efficiency of various operations and when it is a good (or bad) choice for a particular task.