Transcript Chapter 3
Chapter 3 The easy stuff Lists • If you only need to store a few things, the simplest and easiest approach might be to put them in a list • Only if you need to search or some other more intensive operation on the data would a more complex structure be needed Lists • A list is a finite, ordered sequence of data items know as elements • Each element has a position • It’s empty when it contains no elements • The number of current elements is its length • The first element is the head • The last element is the tail Basic Operations • Must be able to insert and delete anywhere along the list • Should be able to gain access to an elements value • Must be able to create and clear the list • Convenient to gain access to the next element from the current one List ADT • In C++ we will use the notion of an abstract class for the List • We will increase the flexibility by making it a template • The abstract class does not specify how the operations are implemented • Given that we want to support the concept of a sequence, the key decision embodied in the ADT is the notion of position Details • Assuming that we all have implemented a linked list • There are 4 steps for insertion – Create an empty node – Initialize the data member to the value to be stored – Fix the pointers for next and prev – Make sure any head and tail pointers are still valide Deletion • • • • The node to be deleted is targeted A temporary pointer to that node is created The node is redirected around The temporary pointer is used to delete the node Circular Lists • Normally not a good idea • But there are times when one might be useful – When you have multiple processes using a resource • The end of the list simply points back to the head • There is a tail pointer and that’s it. • Data can be inserted either at the front or at the end Skip Lists • Linked lists have the drawback that each node must be searched when looking for data • Ordering the data can solve this to some degree, but you still must sequentially scan the list • Skip lists solve this problem of sequential search. Self Organizing Lists • List are not good at searching • In order to speed up that process, you can use organizing strategies that can help • Here are four methods – Move-to-front – Transpose – Count – Ordering Other Thoughts • Sometimes it is helpful to have sentinel nodes • A sentinel node is a node type that contains no data • It is used to simplify some operations • It can also make others more complicates • In this case, an empty list contains two sentinels and nothing else Other Linear Structures Stacks, Queues and Deques Stacks The stack is a list-like structure in which elements may be inserted or removed from only one end. A stack follows a LIFO access pattern Elements are stored and removed in reverse order of their arrival Elements are pushed on the stack Elements are popped off the stack Useful Operations Clear isEmpty Push Pop TopEl Returns the topmost element without removing it from the stack What are stacks good for? Stacks can be used for a lot of activities Compilers will use them to check for balanced brackets, parenthesis, comment, etc. You can use them to implement an infinite precision calculator And of course, the run-time stack Queues The queue is a list-like structure that provides restricted access to its elements Elements are enqueued at the back Elements are dequed from the front Queues follow a FIFO access pattern Useful Operations Clear isEmpty Enqueue Dequeue firstEl Returns the first element without removing it from the queue What are queues good for? Queues can be used in many situations You can use them to determine if a poem is an acrostic Queuing theory from mathematics obviously will use queues A bank wants to determine the number of tellers required to keep customer wait to a minimum Queue Implementation What are some obvious ways to implement a queue? Linked Array based What is the problem with an array based implementation? The head and the tail will creep. What is the solution? Make the queue circular Deque A double ended queue. You have direct access to both ends of the list. The STL has an interesting implementation of a deque Iterators A pure abstraction Introduction “Iterators are the glue that holds containers and algorithms togther”. P 549 The C++ Programming Language, Bjarne Stroustrup They provide an abstract view of data Iterators support an abstract model of data as sequences. Iterators and Sequences An iterator is pure abstraction Anything that behaves like an iterator is an iterator An iterator is an abstraction of a pointer to an element of a sequence For example, an int* is an interator to int[] More Iterator Issues There is no concept of a “null iterator” An iterator that points to nothing typically points to the same value as “one past the end” and should be compared to that same value If an iterator points to an element, it is said to be valid. Const Iterators Const iterators support the same behavior as non-const interators with the major exception that const iterators are not allow to modify the container to which they point.