There are 4 new terms that we defined in this unit which we will be using throughout the course:
Let’s start by looking at some examples of each, then we’ll settle on a definition.
Examples of ADTs:
For each ADT, here are some data structures that we discussed either in this course, or that you saw in a previous course:
From here, we can start making a distinction between the notion of an ADT and a data structure. For starters, an ADT is a more general idea. In particular, an ADT encapsulates how we would use a particular data type.
For example, as experienced programmers we immediately understand some of the ways that we might interact with a list. We know lists may contain duplicate elements, that elements are maintained in some sequence, and that there are certian operations we can do on the list (e.g. add, remove, indexing).
For this class, defining an ADT requires providing two things: 1. The notion of what the ADT represents 1. The operations that are able to do with the data
We can then define ADTs for list, set, and queue as follows (note: the list of operations given is not intended to be exhaustive, but should just give an idea of what makes each ADT distinct from the others on this list):
A data structure is a strategy for satisfying an ADT. For each of our data structures we will describe how we will represent the contents, and we will describe the algorithms we will use for each operation. The algorithms we design for each operation should correctly update the representation to match the behavior outlined in the ADT.
For example: - A linked list data structure stores its elements in node objects, then maintains the sequence of elements by adding a reference from each node to the next one in sequence. - An array list data structure stores its elements in an array. The sequence is maintained by the order of storage in the array itself. Because the add operation’s functionality does not depend on the size of the list, we will copy elements into a larger array if we ever need to add an element when the array is full.
Between lists and queues we have seen two different designs for data structure design: 1. Linked Nodes - Data is stored in node objects, each of which has a reference to another node object - List: the linked lists data structure - Queue: the linked nodes queue data structure 1. Resizing Array - Data is stored in an array, where contents must be copied into a new larger array if it ever becomes full - List: the array list data structure - Queue: the circular array data structure
Challenge Question: Which of these two designs does a binary search tree most resemble? Can you think of a way to represent trees that resembles the other design?
The final vocabulary term we presented was an implementation of a data structure, which is specifically computer code which puts a data structure into effect.
We’ll now provide an illustration of each of the queue data structures presented in class. In exercise 0 you will build stacks which behave similarly to the queue data structures.
Below we have some slides stepping through the behavior of the enqueue and dequeue algorithms for a linked nodes queue. You may download the source pptx by clicking this link.
Below we have some slides stepping through the behavior of the enqueue and dequeue algorithms for a circular array queue. You may download the source pptx by clicking this link. Note that this does not demonstrate resizing, as this is a challenge we’ve reserved for exercise 0.