.Open CS202 session 11 -- linked data structures
. Previous -- Algorithms + Sorting and Searching
.See ./10.html
. Preparation
Study
Chapter 12
and do Review Questions.

Here
.See ./list1.cpp
is the example at the start of the chapter.

. Introduction to linked lists on Wikipedia
.See http://en.wikipedia.org/wiki/Linked_list
. Stacks and queues on Wikipedia
.See http://en.wikipedia.org/wiki/Stack_(data_structure)
.See http://en.wikipedia.org/wiki/Queue_(data_structure)

. Due in
Hand in one even question+answer at the start of class.

Perfect projects can earn a 5 point bonus if handed in at the start
of this class.
.Open Class Work
. Exercise using list iterators
.See ./tlist.cpp
. When should you use an array -- a vector -- a list
. When should you use a stack
. When should you use a queue
. Demo
.See ./13frame.html
. Example of simple linked list queue
.See ./LinkedQueue.cpp
.See ./LinkedQueue.h
.See ./testLinkedQueue.cpp

. You need to think clearly about linked data lists
I had some real problems with the above program because I
forgot that when you move or erase an item in the list
other iterators that point to the moved or erased node
`become invalid`.  They stay attached to the old position
in RAM, after the node has moved...

SImilarly inserting an item before the first item does
not update iterators... I had a `begin` iterator that ended
up attached to the 4th item, not the 1st!
.Close
. Next -- Overloaded operators in Chapter 14
.See ./12.html

Next project due next class.
Quiz on
Chapter 10,11,12, algorithms, and P2 in next class.
. Do not study chapter 13 until later
Arrays, vectors, lists, stacks, and queues are all 
.Key Containers
in the Standard Library($STL).  It has other Containers as well: sets, maps, priority_queues,
and so on.  We will study these ate the end of the course using Chapter 13 and the first part of chpter 20.
You can use my notes
.See ./stl.html
if you wish.  Some of these are mentioned in laboratories, exercises, but not in quizzes.
They are covered in detail in CSE330 Data Structures.
.Close