You will quickly realize the challenges involved in designing a priority queue based on our linked list package while keeping a general well-encapsulated linked list.
First, a priority queue (PQ) needs both a data-item and a separate priority key. We need to pass two items to a linked list designed to store 1 item. (Hint: pass a PQNode object). Second, we need to maintain proper encapsulation. A linked list should not know the internal details of its stored items. A PQ should not mess with the internals of the linked list.
You will soon realize that there is no clear “good” decision about how to implement the PQ operations quickly and maintain isolation from the existing linked list.
Here are some choices:
- Have the PQ package maintain two linked lists: one for data items and the other for priorities. The queue needs to track which item goes with which item-priority. Alternatively, priority values may be kept in an internal array.
- Limit knowledge of priority to special linked list methods designed for the PQ package (so that you can scan the list for a priority field, for example).
- You can allow your PQ methods to directly process the linked list in some cases (as needed), which involves directly manipulating linked list internals from the PQ package.
The last two design choices violate object-oriented programming principles, both bad decisions, particularly on a bigger or a longer-term project. Yet, the last is the choice I would recommend in this case. The reasoning is as follows.
We already know that this implementation is short-term. We have decided to do a heap-based high-performance version later. The reason for using the ready linked list was to be able to quickly implement the greedy algorithms which require a PQ (you only have a few days). So, it seems that choice 3 is justified, given the quick-and-dirty nature of the implementation.
The thinking above illustrates an important design rule: compromises are sometimes necessary if you have good reasons and you document them well. Even though there are better options, the extra complexity and time, in this case, are probably not worth it for now.