Intro to Data Structures


C++ has some built-in methods of storing compound data in useful ways, like arrays and structs.  There are other methods of storing data in unique ways that have useful applications in computer science. 

The general concept of what a data container stores, along with general operations we want on that data, is an example of an Abstract Data Type. Note that a typical ADT does not mandate HOW the storage is set up inside, but rather what the general concept is from the user's point of view. Examples:

Sometimes these ADT concepts have mulitple possible implementations. So the study of data structures involves looking at the various possible implementations, along with the advantages and disadvantages of each. C++ classes allow a nice mechanism for implementing such data types so that the interface (the public section) provides for the necessary operations, and the actual implementation details are internal and hidden.   The implementation of the class can be made to handle all of the storage details, along with any necessary dynamic allocation and cleanup.  Common data structures include:  stacks, queues, vectors, linked lists, trees, hash tables, sets, and others.  We will introduce a few of these concepts here.
 

Stacks

This is an ADT (abstract data type).

Queues

This is an ADT (abstract data type).

Vector

This is a specific implementation of the sequence/list ADT.

Linked List

This is a specific implementation of the sequence/list ADT.


Note: Some abstract types, like Stacks and Queues, can be implemented with a vector or with a linked list.  A stack can use a linked list as its underlying storage mechanism, for instance, but would limit the access to the list to just the "push" and "pop" concepts (insert and remove from one end).
 

Code Examples:

Examples from the textbook (Savitch)

Some code examples from Deitel (previously used textbook)

These examples are all implemented as class templates.