Sample Question:

sdfsdfsf

JSR Notes:

List ADT B.: Applications

Application of Lists: Stacks and Queues

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

(Beyond the basics: Note that such access, three out of the four times it is most often done - see the next section - can be from the head, which is very easy, since that's what we have direct access to.)

Lists Applied as Stacks

In the case of operation as a stack, the last node "in" is the first node "out" (LIFO). So adding and removing will be (easilly done) from the same end.

(Beyond the basics: Note that we could also add & remove from the "tail", though with direct access only to the head, this would be less efficient.)

List Applied as Queues

In the case of operation as a queue, the first node "in" is the first node "out" (FIFO). So adding and removing will be from opposite ends.

(Beyond the basics: Note that the combination of adding to the "head"/removing from the "tail", along with the combination of adding to the "tail"/removing from the "head", both achieve this.)

 

And, finally, to make a connection to Topic 6 and operating system functions, interrupts are a great example of something that should and does work as a stack, since more urgent things should be attended to first, before the other, less urgent interrupts that are stacked beneath them.

And polling requests are a great example of something that could operate more as a queue, since no one request, or check is more important than another (generally), so first come, first serve should be the way things, work.

 

Non-applications of Lists: Searching and Direct/Random Access

It is very important to note that lists SHOULD NOT BE USED in many situations; the following two in particular. And so you need to keep in mind that we have other structures at our disposal also for these things - namely arrays and binary search trees.

Direct/Random Access - List No No!!!

Do not choose to use a list (stack or queue) if you intend to be accessing individual data from some place in the middle of the structure, which we call direct access, or random access. Lists are only really efficient for accessing data from the head. And in terms of the functionality that is to be expected from lists, access from the tail is usually implemented also (even though that takes a traversal all the way from the head.)

So if needing to access directly/randomly from the middle of a structure some place, an array is a much better approach; if the position of the element is know, then it is pure, direct access, like print(arr[5]) - in this example, if arr were an int array, we would take the address of arr, and add 5 * 32 to that address to directly access this element. And if the exact element of the array is not know, it may be possible to use another approach called hashing (outside the context of this syllabus).

Meantime, searaching through a list, though possible, is not easy, direct access; it is access by traversing through the entire list until we find what we are looking for. (For what it's worth, Big O n, rather than the Big O 1 efficiency of using arrays, and/or hashing.)

Searching - List No No!!!

Do not choose to use a list (stack or queue) if you intend on frequently searching for data; it is not made for this purpose. Any searches have to happen one step at a time, sequentially, starting at the head. In the worst case scenario, you will have to visit all nodes to find what you are looking for. (Again, for what it's worth, a Big O seraching efficiency of Big O n.)

Depending on the situation, two other options are better for searching. The first situation to consider is a static context, in which the size of the structure us generally unchanging. In this case, just use an array, sort it, and then it can be binarily searched. But if it is a dynamic situation, with a structure changing in size, and you still need searching, choose a binary search tree structure.