Unit 9 -- Csc 115 Spring 2005
Learning Objectives for this unit
- How to implement Stacks and Queues using Double Linked Lists
- Learn about Lists, Double Linked Lists and Vectors and
when to use them
- Understand the space and time needs for these abstract data types
Learning Resources for this week
Lecture slides:
9-Lists.ppt
Sample programs as found in the source directory of this project.
- Examples to show how to implement a queue and a stack using a doubly linked list:
- An example to implement a postfix evaluator using a stack:
- Josephus example from the textbook:
Reading Assignment:
Read Chapter 4.4, 4.5 and Chapter 5.1-5.11)
See also the
textbook website for the examples discussed in the readings.
Activities:
Short Answer Questions
Answer the following questions:
- What operations would you expect a Vector ADT to provide?
- If a vector is implemented using an arraylist, what is the time complexity of
these operations?
Problems in the textbook, Chapter 5:
- R-5.1
- R-5.3
- R-5.4
- R-5.8
- R-5.14
- C-5.1
Go to the course website