Java class subset of C++ std::list with efficient std::list::sort()

Question

Issues with generics < E > and < E extends Comparable > in code below. What changes are needed in the code below to prevent DLList.push_front() and DLList.push_back() from accepting strings instead of Integers?

The following code is a sub-set of C++ std::list, implemented as a circular double linked list that includes an internal node list where list.next is a reference to the first node, and list.prev is a reference to the last node. list is the equivalent of std::list::end(). References to nodes are used instead of std::list::iterator.

DLList.sort() is a recursive merge sort, but instead of scanning lists to split them, it recursively divides a count (size) by 2 until a base case of size == 1 is reached. DLList.merge() uses DLList.splice() to move one or more nodes at a time within a list to sort the list. Visual Studio 2022 now uses this method in std::list::sort(). On my old desktop with Intel 3770K CPU, it takes about 2 seconds to sort 4,194,304 Integers from sequentially allocated nodes, and about 3 seconds for scattered nodes (tested by refilling sorted list with random numbers and sorting again).

In the Visual Studio 2022 and my C++ implementations for std::list::sort() a pointer to the beginning node is passed by reference and a pointer to the ending node is returned. Java doesn't have pass by reference, so a static instance (one time allocation) of a node pair np is used instead, passed to and returned by sortr(). sortr() uses np.beg and sz as inputs, returns np, and only sets np.end in base cases where sz == 1.

I use one working directory with NetBeans, copying source files to x.java for testing, which is why package x is used.

package x; import java.util.Random; class DLNode<E>{ DLNode<E> next; DLNode<E> prev; E element; DLNode(){ next = null; prev = null; element = null; } DLNode(E e){ next = null; prev = null; element = e; } } class NodePair{ DLNode beg; DLNode end; NodePair(){ beg = null; end = null; } } class DLList<E>{ DLNode<E> list; int size; DLList(){ list = new <E> DLNode(); list.next = list; list.prev = list; size = 0; } public int size() { return size; } public DLNode<E> begin(){ return list.next; } public DLNode<E> end(){ return list; } public E front() { if(size == 0) return null; return (E) list.next.element; } public E back() { if(size == 0) return null; return (E) list.prev.element; } public void push_front(E element) { DLNode<E> node = new DLNode(element); size++; node.next = list.next; node.prev = list; list.next.prev = node; list.next = node; } public void push_back(E element) { DLNode<E> node = new DLNode(element); size++; node.next = list; node.prev = list.prev; list.prev.next = node; list.prev = node; } public E pop_front() { if(size == 0) return null; size--; DLNode<E> node = list.next; DLNode<E> next = node.next; next.prev = list; list.next = next; return (E) node.element; } public E pop_back() { if(size == 0) return null; size--; DLNode<E> node = list.prev; DLNode<E> prev = node.prev; prev.next = list; list.prev = prev; return (E) node.element; } // move rgt node to just before lft node public void splice(DLNode lft, DLNode rgt){ rgt.prev.next = rgt.next; // remove rgt node rgt.next.prev = rgt.prev; rgt.prev = lft.prev; // insert before lft rgt.next = lft; lft.prev.next = rgt; lft.prev = rgt; } // move rgt to end.prev nodes to just before lft node public void splice(DLNode lft, DLNode rgt, DLNode end){ DLNode lst = end.prev; // reference to last node rgt.prev.next = end; // remove rgt nodes end.prev = rgt.prev; rgt.prev = lft.prev; // insert before lft lst.next = lft; lft.prev.next = rgt; lft.prev = lst; } // merge two sorted runs using splice to rearrange nodes within list private <E extends Comparable> DLNode<E> merge(DLNode<E> lft, DLNode<E> rgt, DLNode<E> end){ DLNode<E> nxt; DLNode<E> rtn = lft; // set reference to first merged node if(lft.element.compareTo(rgt.element) > 0) rtn = rgt; while(true){ // merge runs // advance lft until lft > rgt while(lft.element.compareTo(rgt.element) < 1){ lft = lft.next; if(lft == rgt) return rtn; } // advance nxt undil nxt >= lft */ nxt = rgt.next; while(nxt != end && nxt.element.compareTo(lft.element) < 1) nxt = nxt.next; // move rgt to nxt.prev to before lft splice(lft, rgt, nxt); rgt = nxt; if(rgt == end) return rtn; } } // merge sort using stack to track sorted run boundaries // lft and sz are local, np is one time allocation private NodePair sortr(NodePair np, int sz){ if(sz == 1){ np.end = np.beg.next; return np; } np = sortr(np, sz-sz/2); // lft run DLNode lft = np.beg; np.beg = np.end; // rgt run np = sortr(np, sz/2); np.beg = merge(lft,np.beg,np.end); // merge return np; } public void sort(){ if(size() < 2) return; NodePair np = new NodePair(); np.beg = list.next; sortr(np, size); } } public class x { public static void main(String[] args) { DLList list = new <Integer> DLList(); final int COUNT = 4*1024*1024; Random r = new Random(); DLNode<Integer> node; Integer i; Integer j; long bgn, end; // test sort with sequentially allocated nodes for(i = 0; i < COUNT; i++) list.push_back((Integer)r.nextInt()); bgn = System.currentTimeMillis(); list.sort(); end = System.currentTimeMillis(); System.out.println("milliseconds " + (end-bgn)); // test sort with scattered nodes for(node = list.begin(); node != list.end(); node = node.next) node.element = (Integer)r.nextInt(); bgn = System.currentTimeMillis(); list.sort(); end = System.currentTimeMillis(); System.out.println("milliseconds " + (end-bgn)); // verify sort worked node = list.begin(); i = node.element; j = i; for(node = node.next; node != list.end(); node = node.next){ j = node.element; if(i.compareTo(j) > 0) break; i = j; } if(i.compareTo(j) == 0) System.out.println("passed"); else System.out.println("failed"); // remove all nodes from list while (0 != list.size()) list.pop_front(); } } ```

Answer 1

Code Structure / Encapsulation

Class DLList representing your doubly-linked list implementation should be public and its attributes private.

Auxiliary classes should be encapsulated within the list as nested privatestatic since they are only supposed to be used internally by the list.

External code should have no notion of list-nodes, list should be a designed as a user-friendly abstraction instead of leaking its implementation details.

Comparable

Your list is broken because it allows adding elements that are non-comparable. And then when it comes to sorting, it stipulates that values should implement Comparable.

This issue can be resolved in two ways.

• You can mandate upfront that list-elements should be comparable by changing the class declaration:

public class DLList<E extends Comparable<? super E>> 

^{Where Comparable<? super E> means that either E or one of its super-types implements Comparable (which is more flexible than E extends Comparable<E>, i.e. E type itself implements comparable, and not inherits implementation).}

• Use Comparator

Since Comparable is supposed to be implemented only by types that have natural ordering, demanding that elements should be comparable is a very strict constraint that will limit the usage of the list.

For example, it's almost never the case when domain types have natural ordering (there's no unified widely recognized way to compare students, employees, books, etc.).

A better option would be to use a Comparator to determine the ordering of elements.

public class DLList<E> { private final Comparator<? super E> comparator; } 

^{Where Comparator<? super E> means that this comparator is capable of dialing with instances of type E or one of its super-types.}

If you choose this route, your list would need to expose a constructor expecting a Comparator as a parameter.

Optionally it might also expose a constructor which does not require a comparator, and in such a case while sorting elements they should be treated as comparable; i.e. you need to cast the values of nodes into a Comparable of raw type. That's one of the rare cases when use raw types is justifiable (but you have many others that are not, more on that below), and don't forget to apply annotation @SuppressWarnings("unchecked") while performing this cast.

---

Regardless of which of the two strategies listed above you choose, method merge() should not declare its own generic type parameter before its return type.

Redundant Constructors / Initialization to null

• No-args constructors (in classes that do not declare parameterized constructors), which initialize attributes to default values defined by the language specification (such as null for reference types) only create noise.

You don't need them, Java-compiler will autogenerate them for you.

NodePair() { beg = null; end = null; } 

• When a class has more than one constructor, you can call constructors from one another (so-called telescopic constructors). But, please, doesn't perform the automatic assignment to null manually. If a developer has chosen to use a certain technology (language, framework), it should be well-understood and trusted.

So instead of this:

DLNode() { next = null; prev = null; element = null; } DLNode(E e) { next = null; prev = null; element = e; } 

I'll suggest the following:

DLNode() { this(null); } DLNode(E e) { element = e; } 

Raw Types

You're using raw types in many places of the code without good reason.

• NodePair should be declared as generic, as well as its fields.

• Generic type variables are missing in the parameters type declarations in the splice() and sortr() methods (not a very descriptive name, by the way).

Generic types should be provided while instantiating a generic class. Either explicitly (e.g. new DLNode<E>()), or through the type-inference mechanism by using so-called diamond operator which is more convenient.

• DLNode<E> node = new DLNode(element); -> DLNode<E> node = new DLNode<>(element);

• list = new <E> DLNode(); -> list = new DLNode<>();

The Java compiler will spot all such cases for you and will issue a warning for each of them.

Naming

• In Java, it's not considered a good practice to skimp on characters. Especially, when it comes to publicly exposed names, such as the names of public types and methods, they clearly communicate the purpose to the user.

For instance, DLList is not a very descriptive name, DL isn't a widely-used abbreviation, and it's discouraged by the Java language naming convention

Try to keep your class names simple and descriptive. Use whole words-avoid acronyms and abbreviations (unless the abbreviation is much more widely used than the long form, such as URL or HTML).

A proper convention-aligned name would be DoublyLinkedList.

• Also according to the naming convention method names should be in camel-case: push_front() -> pushFront().

Answer 2

• The two-argument overload void splice(DLNode lft, DLNode rgt) is never called. push_front and pop_back are never called either. If you write a method, at least write a unit test for it.

• I am not sure I understand what do you mean by scattered. Both tests fill the (same) list with the random numbers, don't they?

• The verify sort worked loop deserves a name. Consider making an is_sorted method.

  That said, the first (sequential) sort is not verified.

• sortr base case doesn't feel right. If sz == 1, the np.end must be equal to np.beg.next; if it doesn't, something went awfully wrong. Use an assertion perhaps, and terminate if it failed, but don't blindly reassign np.end.

• I do not endorse use of tla. Please spell left, right, begin, next, etc.

Answer 3

To answer your explicit question:

Revising question: what changes are needed in the code below to prevent DLList.push_front() and DLList.push_back() from accepting strings instead of Integers?

The minimal code change required to prevent that is to replace this line in your main method:

 DLList list = new <Integer> DLList(); 

with:

 DLList<Integer> list = new DLList<Integer>(); 

Actually even fixing the constructor call isn't needed, although you should still do it. The absolute minimum change needed is to replace DLList list on that line with DLList<Integer> list.

Specifically, DLList list declares list as having a raw type. This syntax is allowed for backwards compatibility with (very) old Java code that didn't support generic types at all, and basically bypasses Java's compile-time generic type checking. You shouldn't use it.

Any half-decent Java IDE will warn you if you accidentally try to use a raw type. So will the Java compiler itself, if you run it with the -Xlint:unchecked option.

(Heck, even if you don't, it will still warn you once with a message like Note: x/x.java uses unchecked or unsafe operations. But using -Xlint:unchecked will give you more detailed warnings.)

Frame challenge: Is this wheel worth reinventing?

Just out of curiosity, I tried running your sorting benchmarks and comparing them with equivalent benchmarks using the ArrayList and LinkedList classes from the Java standard library. The results on my laptop (2023 M2 MacBook Pro) look like this:

1. ArrayList: 0.9 seconds (always sequential)
2. LinkedList: 1.2 seconds (sequential) / 1.1 seconds(!) (non-sequential)
3. DLList: 1.4 seconds (sequential) / 2.7 seconds (non-sequential)

Of course this isn't anything like a proper JMH benchmark, and you can clearly see that there's something funny going on e.g. with LinkedList being seemingly faster to sort when the nodes are not initially allocated in sequential order. But I did run the benchmarks several times and got at least qualitatively consistent results: ArrayList is always fastest, followed by LinkedList, and your DLList is consistently slower than either of them.

Of course this doesn't mean that your code is useless as a learning exercise, nor that you couldn't, with sufficient effort, come up with a list implementation that's faster (at least for some use cases) than the ones in the Java standard library. But if that's your goal, you have quite some way to go yet. Especially since you can count on the standard library code being quite well optimized already.

On the other hand, if you just want to have a fast list implementation in Java, the easy path is simple: just use ArrayList. It works. :)