Java Deque Feedback

Question

To make my question a bit more clear, I am asking about (1) how to implement thread safety in this context as well as (2) whether I should cache the first and last nodes. I remember the teacher explaining that it is a solution but not a great solution and I thought part of the point of not exposing the "bare data structure" was to leave the pointers to the inner object aside from "sentinel" but maybe I am misunderstanding.

I am having a lot of trouble evaluating how I am doing with this assignment. I can't share the github repo publically per the course guidelines but I will share my code here because I don't know where else to go for feedback... I created a "LinkedListDeque" per the project instructions, which contains within it a vtNode which is just a generic node that contains its item and next and prev pointers. All the code in main was just for me to use the functions a bit.

One person I know who is a professional programmer told me this: "Your Deque is in no way thread safe (and probably doesn't need to be for this course), but years of getting wrecked by multithreaded code has alarm bells going off in my head"

^I haven't done multithreaded code before (I think that might be what async means but I have only done that like once or twice)

They also said: "Hint: consider having more than one instance variable pointing to the chain of nodes in your Deque implementation to take advantage of the fact it's double ended"

I asked "By having more than one instance variable, do you mean kind of like caching the first and last nodes?" - They said that is the idea but I am still a little lost. Can I get feedback and maybe further clarification/support?

//an attempt to construct my own SLList for generics
import java.util.Scanner;
/*Main data structure, a "double-ended-queue" or "deck" allows access at both ends*/
public class LinkedListDeque<vT> {
 private vNode<vT> sentinel;
 private int size;
 /*Empty constructor (I will refer to LinkedListDeque as LLD)*/
 public LinkedListDeque() {
 sentinel = new vNode(null, null, null);
 sentinel.next = sentinel;
 sentinel.prev = sentinel;
 size = 0;
 }
 /*Constructor with input*/
 private LinkedListDeque(vNode<vT> first) {
 sentinel = new vNode(first, null, null);
 sentinel.next = new vNode(first, sentinel, sentinel);
 sentinel.prev = sentinel.next;
 size = 1;
 }
 /*vNode class definition, nested naked data structure.*/
 private static class vNode<vT> {
 public vT item;
 public vNode<vT> next;
 public vNode<vT> prev;
 public vNode (vT v, vNode<vT> n, vNode<vT> p)
 {
 item = v;
 next = n;
 prev = p;
 }
 }
 /*returns true if the LLD is empty*/
 public boolean isEmpty() {
 if (size == 0)
 return true;
 return false;
 }
 /*Retrieves item at index*/
 public vNode get(int index) {
 if (index == 0)
 {
 return this.sentinel.next;
 } else {
 if (index > 0)
 {
 this.sentinel = this.sentinel.next;
 return this.get(index-1);
 }
 }
 return null;
 }
 /*Creates a "deep copy" of the LLD*/
 public LinkedListDeque<vT> copy() {
 LinkedListDeque<vT> newList = new LinkedListDeque<>();
 vNode<vT> current = this.sentinel.next;
 for (int i = 0; i < this.size; i++) {
 newList.addLast(current.item);
 current = current.next;
 }
 return newList;
 }
 /*Returns the size of the LLD*/
 public int size() {
 return size;
 }
 public static void printValsandSize(LinkedListDeque theList)
 {
 System.out.println("The FIRST item: " + theList.sentinel.next.item);
 System.out.println("The SECOND item: " + theList.sentinel.next.next.item);
 System.out.println("The Penultimate item: " + theList.sentinel.prev.prev.item);
 System.out.println("The LAST item: " + theList.sentinel.prev.item);
 System.out.println("Size: " + theList.size());
 }
 public void printDeque() {
 LinkedListDeque.vNode<vT> current = sentinel.next;
 for (int i = 0; i < size; i++) {
 System.out.print(current.item);
 current = current.next;
 if(i < size - 1)
 System.out.print(", ");
 }
 System.out.println();
 }
 /*This appends to the front of the vNode contained within*/
 public void addFirst(vT itemToAdd) {
 LinkedListDeque.vNode<vT> newNode = new LinkedListDeque.vNode<>(itemToAdd, sentinel.next, sentinel);
 if (isEmpty()) {
 sentinel.prev = newNode;
 } else {
 sentinel.next.prev = newNode;
 }
 sentinel.next = newNode;
 size += 1;
 }
 /*Removes the front vNode*/
 public void removeFirst() {
 if (isEmpty()) {
 System.out.println("The list is empty");
 return;
 }
 sentinel.next = sentinel.next.next;
 sentinel.next.prev = sentinel;
 if (size == 1) {
 sentinel.prev = sentinel;
 }
 size -= 1;
 }
 /*This appends to the back of the vNode contained within*/
 public void addLast(vT itemToAdd) {
 LinkedListDeque.vNode<vT> newNode = new LinkedListDeque.vNode<>(itemToAdd, sentinel, sentinel.prev);
 if (isEmpty()) {
 sentinel.next = newNode;
 } else {
 sentinel.prev.next = newNode;
 }
 sentinel.prev = newNode;
 size += 1;
 }
 /*This deletes the prev vNode*/
 public void removeLast() {
 if (isEmpty()) {
 System.out.println("The list is empty");
 return;
 }
 sentinel.prev = sentinel.prev.prev;
 sentinel.prev.next = sentinel;
 if (size == 1) {
 sentinel.next = sentinel;
 }
 size -= 1;
 }
 public static void main(String[] args) {
 boolean on = true;
 LinkedListDeque<String> instanceVarListJava = new LinkedListDeque<>();
 int n = instanceVarListJava.size();
 while(on) {
 Scanner s = new Scanner(System.in); //Used to take user input
 System.out.println("Enter choice: ");
 String c = s.nextLine();
 System.out.println("Choice: "+ c);
 switch(c) {
 case "addFirst":
 System.out.println("Enter what you want to add: ");
 String start = s.nextLine();
 instanceVarListJava.addFirst(start);
 printValsandSize(instanceVarListJava);//prints the state of the LLD
 break;
 case "addLast":
 System.out.println("Enter what you want to add: ");
 String end = s.nextLine();
 instanceVarListJava.addLast(end);
 printValsandSize(instanceVarListJava);
 break;
 /*Retrieve by index*/
 case "get":
 System.out.println("What index?: ");
 int index = Integer.parseInt(s.nextLine());
 System.out.println(instanceVarListJava.get(index).item);
 break;
 case "removeFirst":
 instanceVarListJava.removeFirst();
 printValsandSize(instanceVarListJava);
 break;
 case "removeLast":
 instanceVarListJava.removeLast();
 printValsandSize(instanceVarListJava);
 break;
 case "print":
 instanceVarListJava.printDeque();
 break;
 case "quit":
 System.exit(0);
 default:
 LinkedListDeque<String> instanceVarList = new LinkedListDeque<>();
 instanceVarList.addLast("Check1!");
 instanceVarList.addLast("Check2!");
 System.out.println(instanceVarList.sentinel.item);
 System.out.println(instanceVarList.sentinel.next.item);
 instanceVarList.addFirst("Stay away from the summoner!");
 System.out.println(instanceVarList.sentinel.item);
 System.out.println(instanceVarList.sentinel.next.item);
 LinkedListDeque<String> newList = instanceVarList.copy();
 System.out.println(newList.sentinel.item);
 }
 }
 }
}

• pebble unit: a simple way to ensure thread safety is to use synchronize to synchronize on your sentinel node inside your methods that modify your linked list. Otherwise, you can take inspiration from LinkedBlockingQueue which uses two reentrantlocks (takelock and putlock) to ensure thread safety
• TorbenPutkonen: Two users have voted to close this due to "code not working". Would either of you care to specify why? A mere mention that "it is not thread safe" is not a reason for dismissal as thread safety is not a requirement.
• πάντα ῥεῖ: @TorbenPutkonen First mentioned in the close reason is Code not implemented ..., and this applies here.
• TorbenPutkonen: @πάνταῥεῖ As far as I can see, OP asked for a generic review for the given asignment and those two issues are just additional information from previous reviews. I don't see it as a reason to categorize the code as "not implemented". As for future reference, please try to add clarification on the reasons for the close vote. It really helps new users.
• user284985: @πάνταῥεῖ Thank you! These two points I think clarify and capture my main questions due to the feedback I received. I will even try to edit the post to make that more clear.

Answer 1

meaningful identifiers

Local variable names like n, and s = new Scanner..., are just fine. But for c = s.nextLine() I would have preferred to see choice or command.

I guess a vNode is a "value" node? No idea why that's helpful. Just call it a Node and be done with it. And I guess vT is value type, fine, whatever.

This is an unfortunate name for a variable, far too verbose: instanceVarListJava = new LinkedListDeque<>(); Call it deque or lld.

In printValsandSize you may as well spell out "value". Also fix the camelCase typo -- we should see a capital And.

loop forever

 boolean on = true;
 ...
 while (on) {
 ...
 case "quit":
 System.exit(0);

The exit() call is a bit surprising, as return would have sufficed. Didn't we want to clear the on flag? Consider renaming to while (running) or perhaps while (not done).

Consider consolidating all those calls that display the list. Display it at top of loop, right before the command prompt.

automated test suite

Exercising the code via main() is very nice. Next step on your learning adventure: JUnit!

It lets you nail down a particular behavior and keep re-testing it, so you're confident that a refactor edit over here didn't break something over there.

invariants

This class maintains some invariants. For example size reflects the number of linked user nodes, and we carefully maintain doubly linked {.prev, .next} pointers between neighbors. Please write down such invariants explicitly. I think that reading the ctor I formed a certain understanding of how you're using sentinel, and then reading the get() code raised a few doubts.

head + tail

What is going on here?

 private LinkedListDeque(vNode<vT> first) {
 sentinel = new vNode(first, null, null);
 sentinel.next = new vNode(first, sentinel, sentinel);

A sentinel node would be a node that caller can never have a reference to. Or perhaps you were reading this wiki entry a bit too literally?

That earlier new vNode(null, null, null) made perfect sense. But here, we have two references on the user-supplied first node. It looks like you want to make it very hard for the GC to collect it. Please don't do that. The sentinel shouldn't have any data.

Since that node is just being used for its .next + .prev fields, and it has confused you at least once already, I feel you'd be better off discarding it. Also I see no motivation for maintaining a circular list. Prefer to define .head and .tail attributes, with no sentinel node. Likely this would simplify some of the {add, remove} methods.

a boolean is already a boolean expression

 if (size == 0)
 return true;
 return false;

Prefer to simply return size == 0.

fatal exception

In get(), caller has violated the contract if we see a negative index. There's no excuse for a buggy caller. Consider throwing a RuntimeException in that case.

Also, nit, since the zero check did an early return, you can save a level of indent without a nested else.

This is surprising:

 this.sentinel = this.sentinel.next;
 return this.get(index-1);

Recursing is fine, but moving the sentinel along the list is very odd, and you don't put it back at the end, seemingly changing the meaning of "element zero" after a get() call. I wouldn't expect that reading a datastructure with get() is going to mutate it. Prefer to just use a local pointer in the usual way.

As written, this code appears to compute "index modulo size", which seems an adventurous interpretation of the Public API contract. Consider rejecting an index that's too large, with a fatal exception.

thread safety

The OP code works great for single-threaded callers. And it's reasonably fast.

 sentinel.prev = sentinel.prev.prev;
 sentinel.prev.next = sentinel;

Imagine interleaved executions of a pair of threads, each doing a remove. If they both read, then both write, things will get ugly. Acquire a mutex upon entry to each method, and release it upon exit, to avoid unfortunate updates like that. Java's synchronized keyword can help you with this.

Notice that mutex operations will slow down single-threaded callers. So don't incur such overhead if there's no need to pay that price. Developers used to frequently use StringBuffer, which is thread safe, but nowadays we almost always prefer StringBuilder as it doesn't make us pay the mutex cost. Caller might pass in a mutex to the ctor, leaving it null if threads are not in use.

Answer 2

I have three main issues with this code

The first is get. As written, it modifies the list by changing which node is the sentinel (and therefore which node is the first one). This not only re-orders the list, but is likely to hide values (by making a "content node" the sentinel) and introduce spurious nulls (by making the empty former sentinel node look like a "content node"). This is not behaviour I would expect from a method called get. This seems to be a consequence of trying to make the method recursive, where a loop (like in copy or printDeque) would work just fine.

The second also concerns get but is less serious - namely the question of how get should handle an index that's greater than size. Right now, it seems to kinda just wrap around. This is an option, but I would expect an index that's too big and an index that's too small (negative) to behave the same way, and this is not currently the case.

The third concerns removeFirst and removeLast - they strike me as code written to be used by a human rather than by a program - if the list is empty, it displays a message to the user, but the code that tried to remove the item has no idea whether it succeeded or failed. I would suggest providing a way for the calling method to check whether a value was successfully removed - the most obvious way might be to simply throw some manner of Exception (NoSuchElementException seems appropriate) when the list is already empty. Alternatively, you could change the return type of the method - a very natural, and queue-ish, option could be making the operation return the value that was removed (in which case null could be returned if there was none - but see below).

Oh, and it may be worth noting that the person using your list might not want to show a message to the user (and even if they do, they might want to show it by some other means, or in a different language, or...). Regardless of how you signal failure (or whether you choose to do so at all) I would suggest removing the print.

Beyond that, I've got a couple other bits of general (but maybe out-of-scope) advice:

First off, we seem to have a semipredicate problem in get - there's no sign that we can't intentionally add null into the list, and have that be an actual valid value that exists in the list. But get also uses null to signal that the given index was invalid (well, sometimes it does). Which means the caller can't (easily) tell when they get a null back if they passed a bad index, or if the index was valid and actually contains a null. There's a few ways to handle that (personally I usually favor a "don't let people put null in the list in the first place" approach)

I also note the presence of a method to make it easy to print each of the elements, but no easy way to do anything else to each of the elements. Implementing Iterable could make your class more convenient.

Finally, some nitpicking:

• The second constructor is unused and can be removed.
• Maintaining a counter for the loops in copy and printDeque isn't wrong, but it feels like extra work. Just making the loop while (current != sentinel) { /* ... */ ; current = current.next; } feels clearer to me.
• isEmpty() reduces to return size == 0;.
• In get you have an else block containing nothing but a single if. It's conventional to combine the else and the if in that case, leaving if (index == 0) { /* ... */ } else if (index > 0) { /* ... */ }.
• printDeque's name is redundant. print will do.