Basic Data Structures and Abstract Data Types
Overview
Data types, data structures, and abstract data types are introduced. Static and dynamic arrays and various kinds of linked lists are introduced as basic data structures that are supported (or are easily implemented) by many programming languages, including Java, C, and C++. Two basic kinds of abstract data types, stacks and queues, are then introduced, with both unbounded and bounded variants of each being described. Simple implementations and significant applications of each of these are also introduced.
The abstract data types that have been introduced are examples of containers — they hold collections of elements of some other “base type”. As discussed in lectures one can therefore think of families of abstract data types as being introduced — including one abstract data type for each base type that might be used. When implementing these in Java one should use generic programming, which has probably not been discussed in detail in prerequisite courses. Coding examples and problems are supplied to help students become familiar with this.
Thus, fundamental concepts that will be used throughout the rest of the course, and data structures, abstract data types, and a programming concept that will serve as “bedrock” when more complicated things are described, later on, are provided.
Lecture #7: Basic Data Structures — Arrays and Linked Lists
Required Reading
- Lecture Notes:
[ PDF ]
[ Video ]
- Supplement — The Amortized Cost of a Sequence of ArrayList
Operations:
[ PDF ]
- Questions for Review: [ PDF ]
Lecture Presentation
-
What Will Happen During the Lecture
- Java Program Discussed: [ SinglyLinkedList.java ]
Additional Material for Consideration
Tutorial #7: Basic Data Structures — Arrays and Linked Lists
Lecture #8: Basic Abstract Data Types — Stacks and Queues
Required Reading
- Lecture Notes:
[ PDF ]
[ Video ]
- Supplement — Example of the Use of a Call Stack:
[ PDF ]
- Questions for Review: [ PDF ]
Lecture Presentation
Additional Material about Generic Programming in Java
As noted during this lecture, generic programming will be extremely useful when using abstract data types and data structures — but this has probably not been introduced in prerequisite courses. This is, ideally, something that students can learn gradually and independently, by working through tutorials and studying examples that are supplied.
Oracle’s tutorial on this appears to be reasonably brief and readable:
The following class is provided, just to make it easier to use a “Bounded Array” when programming with generics. As an examination of the code should show, it is really just a wrapper for an “ArrayList”.
- BoundedArray.java: [ Source ] [ Documentation ]
Java programs for the Stack-related abstract data types, and implementations, are also available — along with a “StackFullException”, which is used on an attempt to push an element onto a bounded stack that is already full.
Please note, when considering these examples, that the source code is actually quite short and simple! Quite a lot of the text in these files is documentation, needed to provide “Javadoc” documentation for these classes.
- Stack.java (Abstract Data Type): [ Source ] [ Documentation ]
- ListStack.java (List-Based Implemention): [ Source ] [ Documentation ]
- TestListStack.java (Tests):
[ Source ]
- StackFullException.java (Exception for Bounded Stacks):
[ Source ]
[ Documentation ]
- BoundedStack.java (Abstract Data Type): [ Source ] [ Documentation ]
- ArrayStack.java (Array-Based Implementation): [ Source ] [ Documentation ]
- TestArrayStack.java (Tests): [ Source ]
Additional Material for Consideration
Tutorial #8: Basic Abstract Data Types — Stacks and Queues
Queue-related programs for the Java programming exercise, included at the end of the tutorial exercises. are given below.
- Queue.java (Abstract Data Type): [ Source ] [ Documentation ]
- ListQueue.java (Implemenation for You to Complete): [ Documentation ]
- TestListQueue.java (Tests for Your Implementation):
[ Source ]
- QueueFullException.java (Exception for Bounded Queues):
[ Source ]
[ Documentation ]
- BoundedQueue.java (Abstract Data Type): [ Source ] [ Documentation ]
- ArrayQueue.java (Implementation for You to Complete): [ Documentation ]
- TestArrayQueue.java (Tests for Your Implementation): [ Source ]
