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.
Upon successful completion of this unit, you will be able to:
- show how lists, stacks, and queues are used to implement specific requirements.
- describe the differences between stacks and queues.
- relate lists to stacks and queues.
- create structures or objects as items being managed by a list, stack, or queue.
- construct software to employ lists, stacks, and queues within larger applications.
- state the operations common to all lists.
- describe the additional list operations required by stacks.
- describe the additional list operations required by queues.
- use lists, stacks, and queues as independent entities within an application.
- show how lists, stacks, and queues are used to implement specific requirements.
5.1: Linked Lists
Read this section on linked lists. Understanding this topic is essential to understanding linked stacks and linked queues, since those are special uses of linked lists.
This section introduces the basic concept of lists and how lists are used as stacks and queues. Read this page to get an introduction to the concept of a node. A node is a component within a list of objects that are related in some way. Our particular concern is with lists, stacks, and queues. The article discusses nodes from that perspective.
We have looked at some code implementations, but it is worth examining at another approach, since there are many ways to use linked lists, and some are better than others depending on the application. Do not let yourself become dependent on one specific ways of doing things.
Doubly-linked lists have many applications, and it is useful to have knowledge of their implementation.
5.2: Linked Stacks
Read this section on linked stacks, which expands linked lists so that stacks can be implemented. We ignore recursion since, while academically elegant, it leads to uncertain memory-use expansion and is thus not suited for many industrial applications.
We've seen several code implementations thus far, but it is worth looking at another approach, since there are many possible approaches. Some are better than others, depending on the application. Do not let yourself become set on one specific way of doing things.
5.3: Linked Queues
Read Sections 4.3.2 and 4.3.3 on this page. The discussion is short, since queues are not much different from stacks. While the difference is subtle, it is important in many applications.
This is another approach to linked queues. As with linked lists and linked stacks, don't get too attached to any one implementation.
Unit 5 Assessment
- View Receive a grade
Take this assessment to see how well you understood this unit.
- This assessment does not count towards your grade. It is just for practice!
- You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.