• Unit 5: Linked Stacks, Queues, and Lists

    In Unit 2, we discussed three common uses of abstract data types: lists, stacks, and queues, which we implemented via arrays. Now that we have discussed memory pointers in detail, we can see how to move through contiguous and non-contiguous memory. As our applications become increasingly complex and use greater volumes of data, it will become more difficult to allocate contiguous memory for all the data, or even to know how much memory to allocate. That is where linked data structures come into play. We can allocate contiguous memory relatively easy for a particular object (class or structure instance). When that object is no longer needed, it can be deallocated and the memory used for something else. If it is needed in relationship to another object, inter-object links can be created. Thus, we can have lists, stacks, and queues of constantly varying lengths as data arrives or its usefulness in active memory ends.

    Completing this unit should take approximately 3 hours.