List, Stack, and Queues (Chapter 3)

Goals:

1. Introduce the concept of Abstract Data Type (ADT).
2. Define list (ADT) and discuss several implementations of lists.
3. Define stack (ADT), its implementation and use.
4. Define queue and deque (ADT), its implementation and use.
 

Modularization of Programs:

Discuss the concept of breaking down a program into modules. (i.e. functions) Each module devoted to a single task. No module should be more than a page in length.

Reasons for this approach:

1. Program easy to read.
2. Program easy to debug.
3. More than one person can work on it.
4. Easy to maintain. (80% of all programming maintenance.  Maintenance is not as trivial as it sounds)
5. Allows the creation of libraries.

Note that classes provide a higher degree of modularization.  Much bigger brush strokes with classes.

Discuss evils of global variables, goto, etc.
 

Abstract Data Types:


An Abstract Data Type (ADT) is a mathematical abstraction. It consists of the definition of a data structure and a set of operations. There is no description of implementation in an ADT. Why have ADT? For the sake of having well-defined data structures.  ADT also provide a framework from which general programming elements may be created.  Discuss STL.   It also provides a basis for mathematical analysis of the various data structures.

Note: even though an ADT is independent from its implementation, it is clear that its implementation should be done with a class.  Why?

Think of how algebra abstracts basic mathematics
 

The List ADT


The general form of a list is:

A1, A2 , A3 , . . . ,AN

This is a list of size N. A list of size 0 is called an empty list.

Definition: For legal subscripts Ai precedes Ai+1 and Ai+1 follows Ai.

The position of Ai is i.

Operations on a list.

PrintList, MakeEmpty, Find (returns the position of the first occurrence of a key), Insert (inserts a key at a given position.), Delete (deletes a key from a given position), FindKth (returns the element at a specified position.), SizeList. Could add more. See text.

Implementations of lists.
 

  1. Implementation of lists using a simple array. (Often called a linear list or a dense list.)  Discuss how each of the functions are implemented and their big O values. We will write code later.  We will show how data at a given array index is accessed.
  2. Implementation of lists using linked lists. Mention that the elements of a linked list are called cells or nodes. Again discuss how each function is implemented and their big O values.

Example implementation


Create a class to implement lists using arrays. We will use an array of doubles. 

It would be good to have a general solution.  But, with what you know right now, this cannot be done.  When you know templates, it will be trivial to turn our solution in to one that works for a variety of data types.  

Note: C++ classes are a lot better for this example than using functions.  So. this is what we will use.  We will first talk through the functions without coding and then we will look at the code that I have written.

The solution is in the following files  ArrayList.h, ArrayList.cpp, testList.cpp
 

Notes on example

  1. As is tradition in C++, the class declaration is put in a .h file of the same name.  This is necessary so it can be included in any .cpp files that use it.
  2. The class implementations are in a .cpp file with the same name as the class.
  3. We never build software without testing it.  That is why we have the testList.cpp file.  This file contains a main program which is used to exercise the class.
  4. We are using an approach similar to lab2.  Namely, we are using new to allocate space for the array.  If the array gets full, we increase its size by allocating more space.  So that we can see the algorithm work, we just increase the array by 2 positions each time we run out of space.  More typically, we would double the size.
  5. All the operations that are part of the ADT are implemented in the class.
  6. Because we might have to expand the size of the array in a number of place, we have a function to do this.

 

Lab4

Finish the implementation of the ArrayList class by creating the definition of the FindKth and Delete member functions. and enhance the implementation of the list by implementing and testing the following function:

                   int Replace( double a, double b );

The function will replace all the occurrences of a by b in the list x.
 

Please look at the various functions presented in the text.