Table of Contents

structures.png

1. What are data structures?

A data structure is an object (a class, a struct - some type of structured thing) that holds data. In particular, the entire job of a data structure object is to store data and provide an interface for adding, removing, and accessing that data.

"Don't all the classes we write hold data? How is this different from other objects I've defined?"

In the past, you may have written classes to represent objects, like perhaps a book. A book could have member variables like its title, isbn, and year published, and some methods that help us interface with a book.

Book
- title : string
- isbn : string
- year : int
+ Setup() : void
+ Display() : void

However - this is not a data structure. We could, however, use a data structure to store a list of books.

A data structure will store a series of some sort of data. Often, it will use an array or a linked list as a base structure and functionality will be built on top.

Ideally, the user doesn't care about how the data structure works, they just care that they can add, remove, and access data they want to store.

Ideally, when we are writing a data structure, it should be:

  • Generic, so you could store any data type in it.
  • Reusable, so that the data structure can be used in many different programs.
  • Robust, offering exception handling to prevent the program from crashing when something goes wrong with it.
  • Encapsulated, handling the inner-workings of dealing with the data, without the user (or other programmers working outside the data structure) having to write special code to perform certain operations.
SmartBookArray
- bookArray : Book[]
- arraySize : int
- bookCount : int
+ AddBook( newBook : Book ) : void
+ RemoveBook( index : int ) : void
+ RemoveBook( title : string ) : void
+ GetBook( index : int ) : Book&
+ FindBookIndex( title : string ) : int
+ DisplayAll() : void
+ Size() : int
+ IsEmpty() : bool

The way I try to conceptualize the work I'm doing on a data structure is to pretend that I'm a developer that is going to create and sell a C++ library of data structures that other developers at other companies can use in their own, completely separate, software projects. If I'm selling my data structures package to other businesses, my code should be dependable, stable, efficient, and relatively easy to use.

structures_ad.png

Review 1. Data Structures are _ that store _.

Review 2. Data Structures should be

  • ○ Specific, so it is used only in one context.
  • ○ Generic, so it can be used for any kind of data.

Review 3. In this course, think of yourself as the…

  • ○ rich investor that doesn't actually know what anything does
  • ○ business analyst who doesn't need to touch any code
  • ○ programmer of the data structures

…and your USER as…

  • ○ a college student trying to make sense of your work
  • ○ a programmer at another company that uses your data structure in their application
  • ○ an intern that doesn't even know what a data structure is

2. What is algorithm analysis?

Algorithm Analysis is the process of figuring out how efficient a function is and how it scales over time, given more and more data to operate on.

structures_complexity.png

This is another important part of dealing with data structures, as different structures will offer different trade offs when it comes to the efficiency of data access functions, data searching functions, data adding functions, and data removal functions. Every operation takes a little bit of processing time, and as you iterate over data, that processing time is multiplied by the amount of times you go through a loop.

2.1. Example: Scalability

structures_ad2.png

Let's say we have a sorting algorithm that, for every \(n\) records, it takes \(n^2\) program units to find an object. If we had 100 records, then it would take \(100^2 = 10,000\) time-units to sort the set of data.

What the time-units are could vary - an older machine might take longer to execute one instruction, and a newer computer might process an instruction much more quickly, but we think of algorithm complexity in this sort of generic form.

Review 4. Given Algorithm A:

  • For 1 item to process it will take 5 time-units,
  • and for 10 items to process it will take 50 time-units.
  • Its growth rate is linear. Given some data d and time units T: \(T(d) = 5 \cdot d\)
  • a. How long will it take to process 20 items?
  • b. How long will it take to process 25 items?

Review 5. Given Algorithm B:

  • For 3 items to process it will take 9 time-units,
  • and for 4 items to process it will take 16 time-units.
  • Its growth rate is quadratic. Given some data d and time units T: \(T(d) = d^2\)
  • a. How long will it take to process 20 items?
  • b. How long will it take to process 25 items?

2.2. Example: Efficiency of an array-based structure

value: kansas missouri arkansas ohio oklahoma
index: 0 1 2 3 4

In an array-based structure, we have a series of elements in a row, and each element is accessible via its index (its position in the array). Arrays allow for random-access, so accessing element #2 is instant:

cout << arr[2];

No matter how many elements there are (\(n\)), we can access the element at index 2 without doing any looping. We state that this is \(O(1)\) ("Big-O of 1") time complexity for an access operation on an array.

However, if we were searching through the unsorted array for an item, we would have to start at the beginning and look at each item, one at a time, until we either found what we're looking for, or hit the end of the array:

for ( int i = 0; i < ARR_SIZE; i++ )
{
    if ( arr[i] == searchTerm )
    {
            return i; // found at this position
    }
}
return -1;      // not found

For search, the worst-case scenario is having to look at all elements of the array to ensure what we're looking for isn't there. Given \(n\) items in the array, we have to iterate through the loop \(n\) times. This would end up being \(O(n)\) ("Big-O of \(n\)") time complexity for a search operation on an array.

We can build our data structures on top of an array, but there is also a type of structure called a linked structure, which offers its own pros and cons to go with it. We will learn more about algorithm analysis and types of structures later on.

3. The point of a Data Structures class

which-structure.png

Of course, plenty of data structures have already been written and are available out there for you to use. C++ even has the Standard Template Library full of structures already built and optimized!

vector http://www.cplusplus.com/reference/vector/vector/
list http://www.cplusplus.com/reference/list/list/
map http://www.cplusplus.com/reference/map/map/
stack https://cplusplus.com/reference/stack/stack/
queue https://cplusplus.com/reference/queue/queue/

"So why are we learning to write data structures if they've already been written for us?"

While you generally won't be rolling your own linked list for projects or on the job, it is important to know how the inner-workings of these structures operate. Knowing how each structure works, its tradeoffs in efficiency, and how it structures its data will help you choose what structures to use when faced with a design decision for your software.

Review 6. In the real world (on the job), you probably (○ will / ○ won't) be implementing data structures from scratch.

However, to make good design decisions, you (○ need / ○ don't need) to know how different data structures operate.

Author: RachelWil

Created: 2026-10-14 Wed 11:12

Validate