Skip to main content
Code Review

Return to Answer

added 89 characters in body
Source Link
J_H
J_H
  • 42.3k
  • 3
  • 38
  • 157

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.

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.

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.

added 452 characters in body
Source Link
J_H
J_H
  • 42.3k
  • 3
  • 38
  • 157

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

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.

Imagine interleaved executions of a pair of threads, each doing a remove. If they both run the first lineread, then both run the second linewrite, 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.

head + tail

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. Prefer to just use a local pointer in the usual way.

Imagine interleaved executions of a pair of threads, each doing a remove. If they both run the first line, then both run the second line, 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.

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

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.

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.

Source Link
J_H
J_H
  • 42.3k
  • 3
  • 38
  • 157

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.

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. 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 run the first line, then both run the second line, 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.