Describe applications of lists.


Teaching Note:

Students should understand that lists can be used to represent stacks and queues.


Sample Question:


JSR Notes:

Since lists can only be directly accessed from one end or the other, they make for a good structure to implement either stacks or queues.

In the case of operation as a stack, the last node "in" is the first node "out" (LIFO). So both adding and retrieval to/from the list is done at the "tail".

In the case of operation as a queue, the first node "in" is the first node "out" (FIFO). So whereas adding takes place also at the "tail", retrieval is from the "head".


And an important note here is that lists SHOULD NOT BE USED if accessing from the middle some place; only for access from the ends. If needing to access from the middle, and array (or a tree) is a much better approach, since you can then use a binary search rather than the slow/inefficient sequential search which would be required for a list.