CS 102 Lecture Notes
Week Fourteen, Thursday: Data Structures
Self-Referential Classes
A self-referential class contains a pointer member that points to an object of
the same class. These are used to create linear data structures (linked list)
and non-linear data structures (trees, for example).
Dynamic Memory Allocation
Dynamic memory is allocated in C++ with the "new" keyword, and deleted with the
"delete" keyword. The "new" function always returns a pointer to the memory
created.
Linked Lists
Linked lists are very good at inserting and deleting data, but have poor
performance finding data (arrays are just the opposite).
Stacks
Stacks are linear data structures with access only at one end (the top). This kind
of data access is called "first in, last out" (FILO). Stacks
are easily built from linked lists.
Queues
Queues are linear data structures with access only at the ends (remove from
front, insert at rear). This kind of data access is called "first in, first
out" (FIFO). Queues are useful for implementing fair waiting for scarce resources.
Trees
Trees are branching (non-linear) data structures, usually accessed via a pointer
to the root node. Trees generally are categorized as binary (each node has at most
two children) and general.
A utility container class has been created that is an example of a general tree
data structure. This tree node class and associated algorithms is called a
String Tree Utility Data Structure
(STUDS).
This example data structure combines a tree with a queue. Each tree node
has a data object queue to store objects with duplicate keys.
This page established April 11, 2000; last updated April 11, 2000.