CS 2114 Chapter Notes - Chapter Queue and Deque Implementations: Modular Arithmetic, Double-Ended Queue, Java Class Library
Document Summary
Add a tail reference, an external reference to the last node in the chain. Must be able to remove the entry at the front of the queue, so if it"s at the beginning of the chain, it will be easy to remove it. If it is at the end of the chain, removing it requires a reference to the preceding node (must traverse the chain) not a good option since it is not efficient and takes too much time. Will have firstnode and lastnode fields which contain the front and back entries, respectively. Adding to the back: allocate a new node and add it to the end of the chain, if the queue/chain is empty, both the firstnode and lastnode data fields will reference the same new node. Node newnode = new node(newentry, null) ; if (isempty()) firstnode = newnode; else lastnode. setnextnode(newnode); lastnode = newnode;