How to Develop and Submit your Labs

Overview

Aside from the programming with nodes and linked representations, the objective is to have you get a feeling for the 'appropriateness' of an implementation wrt a particular operation, e.g. is a single-linked, linear, single-pointer implementation a good choice when implementing an addLast method.

Supplied Code

• A Dequeinterface for the implementation to implement
  • There is only one copy of this (in the top-level code directory; all the implementations implement the same interface
• A DequeDemo that is essentially the same demo we've been using all along
  • Again, as we're programming to the interface, there is only one of these; it contains a single method demo that receives a i.e., a concrete class that implements Deque and puts it through its paces
• The various Deque implementation
  • Each contains the implementation of the class, minus the removeLast method
  • It also contains the node class of the appropriate type as an inner class
• A Demo app for each implementation that provides the canonical DequeDemo class above with an instantiated Deque of the implementation
• A CollectionException class of the sort presented in class, and provided in lab03

All the above files can be access via the Code link at the bottom of this page/

Choice of Container and Operation

Why Deque?

Why removeLast?

Linked List Flavors

Singly-linked vs Doubly-linked

• As mentioned above, the deque operations work at both ends of the list. In particular removeLast requires access to both the last and next-to-last nodes. To do this without a traversal to the next-to-last node require prev references as well as next references, i.e., a doubly-linked node.
• Having a second reference requires maintaining that properly as well.

Linear vs Circular

• Access to the end of the deque without performing a traversal can be done by imposing a circular structure onto the list and having the external reference be to the last node.
  • Alternatively, the rear can be made efficiently accessible by introducing a tail reference
• Having a circular structure makes the traversing of the list more challenging; one cannot simply use a while (p != null) condition for traversal termination
• Having a circular structure means that none of the nodes (in particular the first and last) have null references on either end.
• Maintaining a circular structure may require special logic to create and maintain the circle.

Single-pointer vs Head-and-Tail Pointers

• Having a tail pointer allows access to the end of the list, but in the case of singly linked list, it ONLY to the end of the list, not the next-to-last node on the list
• Having two pointers (head and tail) require they be synchronized; i.e., when the list goes empty they must BOTH go to null, even though only one end is typically modified by a 'first' or 'last' operation.
• You can see this in the provided methods (e.g. addFirst, removeFirst, addLast).

Header Nodes

• Having a header node means that once the list is created header need never be modified; it will always point to the header node.
• When there is a header node, I user the name header rather than head for the deque's instance variable

Leveraging Methods

'Leveraging' off size and toString

• This was one of the reasons I didn't use a size instance variable (which would be incremented with the add methods, and decremented with the removes) — I wanted you to have the traversal code when appropriate.

Leveraging removeFirst

, i.e., leveraging it. Often much of the special logic involved in going from a non-empty deque to an empty one can be avoided by having removeLast invoke removeFirst in that situation. You can see similar logic in the addLast code (i.e., leveraging addFirst).

OTOH, if you're interested in getting into the weeds, you might consider avoiding invoking removeFirst from removeLast, it forces you to deal with any special case logic on your own, and may give you greater insight into the advantages/disadvantages of the various implementations.

The Supporting Code

Aside from the actual implementation, you are provided with several other source/class files:

• CollectionException: a generic exceptiojn class we will use for our collections/containers
• Deque: the Deque interface that all the implementations adhere to

  interface Deque {
       void addFirst(E value);
       void addLast(E value);
       E removeFirst();                                                                                                                  
       E removeLast();
       int size();
       boolean isEmpty();
       int capacity();
  }
  		

• DequeDemo: a canonical deque demo/test. This has been slight modified from the one presented in the earlier lectures (I've added isolated addFirst/removeFirst and addLast/removeLast sections in addition to alternate first/last operations).
  • this demo app programs to the Deque interface and thus us identical to for all the implementations
    • Each implementation has its own Demo app that creates an object of the corresponding implementation and kicks of the canonical DequeDemo
  • I've also add the output of this demo app

The Implementations

Given four binary attributes — number of links, linear/circular, number of external pointers, header or not — there are 16 flavors of implementations. Some of them require traversals, others have somewhat involved logic (i.e., special cases), and others don't provide any benefit in their implementation. We discuss each of these issues in the particular implementations.

Each of the following sections contains a link to the implementation's code directory containing the skeletal Deque class source for the particular implementation. This code is missing the removeList metho, which you are to supply. The directory also contains the implementation's demo app.

The useless implementations are also listed but have not links.

Suggested Order(s) of Implementation

The ideal order is to start with 8.01 and proceed in order through 8.11. This will give you an opportunity to see how the various attributes of multiple pointers, circularity, and header affect the implementation.

OTOH, if you are feeling a bit unsure of yourself or are intimidated by manipulating references as 'pointers', you might consider doing 8.11 (DC1H) first — it's actually the simplest as you can read in it's notes section. You might then try 8.01 (SL1N) and then 8.02 (SL1H); the former to get you going with the traversal, and the latter to warm you up to the header node.

Either way, if you manage to complete them all, good job! You should be fairly fluent in woring with linked representations by then.

The Labs

Code the removeLast method for each of the following deque implementations. I would recommend you copy the related code into your IDE, add the method, and get it working (i.e., produce the output as shown in the "The Supporting code" section above), before submitting it to CodeLab (see last section below).

Lab 8.01 Singly-Linked, Linear, One Pointer, No Header (SL1N)

Write the removeLast method for a Deque class implemented using a singly-linked, linear, one pointer, no header node list

• Please supply the method only, not the entire class. The first node on the list is referenced by the instance variable head; head should be null when the list is empty.
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

Notes

• If you call removeFirst from removeList, there's no special logic
  • the singleton case (i.e., only one node on the list) is handled by removeFirst
  • if you don't use removeFirst, you need to make sure head is set to null when you remove the only remaining node on the list
• This implementation requires a traversal to the rear

Lab 8.02 Singly-Linked, Linear, One Pointer, Header (SL1H)

Write the removeLast method for a Deque class implemented using a singly-linked, linear, one pointer, with header node list

• Please supply the method only, not the entire class. The header node is referenced by the instance variable header
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

• There's no special logic in this implementation regardless of whether you call removeFirst from removeLast for the singleton case:
  • that's the whole point of using a header node; to eliminate special logic when going from empty-to-singleton or vice-versa
• This implementation requires a traversal to the rear

Lab 8.03 Singly-Linked, Linear, Two Pointers, No Header (SL2N)

Write the removeLast method for a Deque class implemented using a singly-linked, linear, two pointers (head and tail)

• Please supply the method only, not the entire class. The first node is referenced by an instance variable head, and the last node is referenced by the instance variable tail. Both references are null when the list is empty.
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

• The challenge in this implementation is keeping the two pointers in synch, i.e., making sure that when one goes to or from null the other one does as well.
  • Again, using removeFirst avoids this whole issue.
• Notice a traversal is still required for removal from the rear.

Lab 8.04 Singly-Linked, Linear, Two Pointers, Header (SL2H)

Write the removeLast method for a Deque class implemented using a singly-linked, linear, two pointers (head and tail), with header node list

• Please supply the method only, not the entire class. The header node is referenced by an instance variable header, and the last node is referenced by the instance variable tail. tail should be null when the list is empty.
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

• Not sure the header helps much in this implementation
• There's no need nor use for a trailer node; as you can see in the code, is initialized to null (and thus is null for an empty list), and references the last node in a non-empty list. This is one of the more annoying implementations: you have to maintain a header node AND two pointers with essentially no benefit from either.

Lab 8.05 Singly-Linked, Circular, One Pointer, No Header (SC1N)

Write the removeLast method for a Deque class implemented using a singly-linked, circular, one pointer (tail), with no header node list.

• Please supply the method only, not the entire class. The last node on the list is referenced by an instance variable tail. tail should be null when the list is empty.
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

• Making the list circular in structure allows a single pointer (tail), providing convenient access to the last and first nodes on the list
• Having the single pointer removes the synch issue.
• There still is an issue of the transition from empty-to-singleton, and vice-versa, with respect to setting tail from/to null; again calling removeFirst from removeLast handles that situation.
• As with SL2N, a traversal is still required for removal from the rear.
• This implementation, together with DC1N are two of the rare situations where a do … while loop comes in handy

Singly-Linked, Circular, One Pointer, Header (SC1H)

This implementation provides no benefits.

• As this is a singly linked list so we can't move backwards. Placing a header puts it between the last and first nodes on the list proper. Having a tail pointer then pointing at the header does indeed give easy access to the first node (its the one after the header), but getting to the last node requires a traversal, since we can't move back from the tail. As such the header proves to be of no value.

Singly-Linked, Circular, Two Pointers, No Header (SC2N)

This implementation provides no benefits.

• There is no need for a second pointer once a circular structure is used … a tail pointer is sufficient in that is points to the last element and its successor is thus the first element.

Singly-Linked, Circular, Two Pointers, Header (SC2H)

This implementation provides no benefits.

• There is no need for a second pointer once a circular structure is used … a tail pointer is sufficient in that is points to the last element and its successor is thus the first element.

Lab 8.06 Doubly-Linked, Linear, One Pointer, No Header (DL1N)

Write the removeLast method for a Deque class implemented using a doubly-linked, linear, one pointer, no header node list

• Please supply the method only, not the entire class. The first node on the list is referenced by an instance variable head. head is null when the list is empty.
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

• Not much different than SL1N other than having to take the prev field into consideration
• As with the other linear, single pointer implementations, a traversal is still required for operations at the rear.

Lab 8.07 Doubly-Linked, Linear, One Pointer, Header (DL1H)

Write the removeLast method for a Deque class implemented using a doubly-linked, linear, one pointer, with header node list

• Please supply the method only, not the entire class. The header node is referenced by an instance variable header.
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

• Not much different than SL1H other than having to take the prev field into consideration
• As with the other linear, single pointer implementations, a traversal is still required for operations at the rear.

Lab 8.08 Doubly-Linked, Linear, Two Pointers, No Header (DL2N)

Write the removeLast method for a Deque class implemented using a doubly-linked, linear, two pointers, no header node list

• Please supply the method only, not the entire class. The first node is referenced by an instance variable head, and the last node is referenced by the instance variable tail. Both references are null when the list is empty.
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

• With two pointers and double links, no traversals are necessary
• having the first and last nodes of the list contain null in their prev and next fields respectively requires special logic for the empty-to-singleton (and vice-versa) case.
  • this can be avoided by calling removeFirst

Lab 8.09 Doubly-Linked, Linear, Two Pointers, Header (DL2H)

Write the removeLast method for a Deque class implemented using a doubly-linked, linear, two pointers, with header node list

• Please supply the method only, not the entire class. The header node is referenced by an instance variable header, and the last node is referenced by the instance variable tail. tail is null when the list is empty.
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

• With two pointers and double links, no traversals are necessary
• There is still a bit of special logic for the empty-to-singleton case (and vice-versa)
  • This is to set tail to/from null
  • There is no special logic for the prev of the first node, since there's a header.
  • not sure if a trailer node would solve this

Lab 8.10 Doubly-Linked, Circular, One Pointer, No Header (DC1N)

Write the removeLast method for a Deque class implemented using a doubly-linked, circular, one pointer (head), no header node list

• Please supply the method only, not the entire class. The first node of the list is referenced by an instance variable head. head. head is null when the list is empty.
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

• With a circular structure and double links, no traversals are necessary
• The external reference could have just as easily been the tail
• The special logic is setting head to/from null in the empty-to-singleton cases.
  • Again, this can be avoided in removeLast by calling removeFirst
  • The circular structure eliminates the need for any special logic to handle null at either end.
• This implementation, together with SC1N are two of the rare situations where a do … while loop comes in handy

Lab 8.11 Doubly-Linked, Circular, One Pointer, Header (DC1H)

Write the removeLast method for a Deque class implemented using a doubly-linked, circular, one pointer, with header node list

• Please supply the method only, not the entire class. The header node is referenced by an instance variable header. head.
• The other methods of the class have already been implemented; feel free to use them. The interface for Deque can be found above.

• With a circular structure and double links, no traversals are necessary
• There is no special logic in this implementation
  • The circularity eliminates null at either end
  • The header eliminates the transition from (physically) empty to non-empty and vice-versa
  • The single pointer eliminates any need to synchronize two pointers

Doubly-Linked, Circular, Two Pointers, No Header (DC2N)

This implementation provides no benefits.

• There is no need for a second pointer once a circular structure is used … a tail pointer is sufficient in that is points to the last element and its successor is thus the first element.

Doubly-Linked, Circular, Two Pointers, Header DC2H)

This implementation provides no benefits.

• There is no need for a second pointer once a circular structure is used … a tail pointer is sufficient in that is points to the last element and its successor is thus the first element.

Submitting to CodeLab

Each of the above labs has a corresponding CodeLab exercise; all you need to do is submit your method, all the rest of the code has been supplied.

Code Relevant to this Lab