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 abstractdata 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 #6: Basic Data Structures — Arrays and Linked Lists
Required Reading
- Lecture Notes:: [ PDF ] [ Video ]
- Supplement — The Amortized Cost of a Sequence of ArrayList Operations: [ PDF ]
Lecture Presentation
Additional Material
- Explanation of Code Provided
- Code for a Bounded Array: [ Source ] [ Documentation ]
Tutorial #7: Basic Data Structures — Arrays and Linked Lists
Lecture #7: Basic Abstract Data Types — Stacks and Queues
Required Reading
Lecture Presentation
Additional Material
-
Explanation of Code Provided with This Lecture
- Code for an Unbounded Stack
- Stack.java — Interface [ Source ] [ Documentation ]
- ListStack.java — List-Based Implementation [ Source ] [ Documentation ]
- TestListStack.java — Tests
[ Source ]
- Code for a Bounded Stack
- BoundedStack.java — Interface [ Source ] [ Documentation ]
- StackFullException.java — Exception [ Source ] [ Documentation ]
- ArrayStack.java — Array-Based Implementation [ Source ] [ Documentation ]
- TestArrayStack.java — Tests [ Source ]
Tutorial #8: Basic Abstract Data Types — Stacks and Queues
-
Problems To Be Solved
- Code for an Unbounded Queue
- Queue.java — Interface [ Source ] [ Documentation ]
- ListQueue.java — List-Based Implementation for You to Provide [ Documentation ]
- TestListQueue.java — Tests for a List-Based Implementation
[ Source ]
- Code for a Bounded Queue
- BoundedQueue.java — Interface [ Source ] [ Documentation ]
- QueueFullException.java — Exception [ Source ] [ Documentation ]
- ArrayQueue.java — Array-Based Implementation for You to Provide [ Documentation ]
- TestArrqyQueue.java — Tests for an Array-Based Implementation [ Source ]
