Java Data Structures – Custom Node/Chain Implementation

collectionsdata structuresdesignjava

I am designing a simple GUI that will allow a user to create a GPX route by clicking repeatedly on a map panel. I am faced with a design dilemma for how to represent the nodes and route. This construct can be abstracted as follows:

the user clicks n times on the screen in sequence to create a chain of n nodes
after a chain has been completed, a user can add more nodes to it, either by selecting nodes in the middle (inserting between existing nodes) or by simply automatically appending to the end with his next click

At first I was determined to use a Java Collections class to represent the chain, but there are unexpected difficulties with that. On the surface, this would appear to be a perfect example of a LinkedList, but consider as follows. If the user wishes to insert a node in the middle of the chain, he first chooses some node on screen that he wishes to insert a new node before. If the node belongs to a linked list, it will need to maintain a reference to its encompassing list (a somewhat unusual practice, I'd think), and even then we will still have to locate the node in the list before we can insert. So we have to:

find the node (linear time)
insert the new node (constant time)

Or if I try the same thing with an ArrayList, it also performs at best in linear time.

find the node (linear time)
insert the new node (linear time)

But neither case really seems desirable. I briefly flirted with the idea of using a LinkedHashSet, but it does not allow insertion into the middle of the linked list, nor does it seem fundamentally correct to use a set implementation for something like this.

So here is what I came up with:

class Node {
    Node previous;
    Node next;
    Chain chain;
}

A Node maintains only a reference to its previous and next nodes, as well as the chain it belongs to (again, this latter part seems unconventional and possibly even wasteful to me, but I'm convinced it may be necessary here).

class Chain {
    Node first;
    Node last;
}

The chain knows only what its first and last nodes are.

Now, if a user wants to insert a node in the middle of the chain? He selects the node, which simply updates the first/last references of itself and its neighbors. If he wants to add nodes to the end of a chain? He simply selects any node on screen (which is aware of what chain it belongs to, and therefore what the last node in that chain is), and the chain immediately begins updating link references for the last node and each node added after it, as well as keeping its own "last" reference up to date.

I really wanted to use a Collections class, but this approach seems better to me. But I'd love to here thoughts/criticisms from more experienced programmers. Thanks.

Best Answer

Mutable circular references are nasty. Just use an ArrayList and don't worry about it.

You can see all of the elements on screen: it's not going to be so long that linear time takes any time.

re dude demanding an explanation why mutable circular references are nasty: like, as in bad code. It's an inefficient use of programmer-thinky-time, not unavoidably problematic.

Related Solutions

Database Design Data Structures – Should Database Table Structure Match Its Intended Data Structure?

As a database person I want to throw up at the idea of someone designing a database table that way.

Database tables should be designed using three main criteria:

Data integrity
Performance of querying the database
Data security

A good database design often needs fields that are not used by the application in any way (but may be needed for data imports or auditing or for some other reason) and in many databases, multiple applications will need to access the data and have differing needs.

What looks easy to do for data entry screens may not work at all for reporting (which is often a totally different application that the developer designing only for his logic doesn't even know about) because reports tend to deal with larger data sets than data entry screens which typically only concern one record at a time. So a database struture that looks logical from the application programmers perspective (Like an EAV table, shudder!) can be the worst possible thing to use when getting data back out of the database later. Especially if there will be millions of records.

Databases are optimized to use normalized tables and should be designed with normalization priciples in mind not using Object-oriented principles. Yes there is mismatch between what is best for the database and what is best for an object-oriented application. Yes you have to deal with that and no it isn't a good idea to deal with it by making the database match the orject-orientation.

Design Efficient Random Access Queue Using LinkedList in Java

Warning: this is not something that you'd ever want to do. But I'm guessing it's in the "Creative Problems" section (looking at the fourth edition non-Java-specific version of Algorithms, it seems like it might be question 1.2.38 -- which refers the reader to chapter 3 for possible solutions).

OK, with that out of the way, what are some basic constraints on the problem?

To find an element M in a linked list of size N, you must linearly search each element in the list. While M <= N, this is still O(N).
In order to reduce the big-O runtime, we must find another way to access the nodes in the list.
A divide-and-conquer algorithm is O(logN)
An array is O(1), but if you had that, you wouldn't need the linked list.

So, how do you divide-and-conquer a linked list? The answer: each non-leaf element in the list contains another list.

L0
+--L1
|  +--E0
|  +--E1
+--L2
   +--E2
   +--E3

So, the top-level list holds two child lists, and those child lists hold the actual elements. We need a couple more constraints:

Any list L knows (1) whether it contains sublists or elements, and (2) the total number of elements held by all descendents.
Any list L has a limited number of children. In this case 2, but it could be any number. This is critical to the big-O evaluation: any set of operations that has a fixed size not dependent on N is equivalent to O(1).

So, let's look at how this works to find element E2:

Start with node L1, which we know is a list that contains 2 elements.
Since E2 is the third element, move on to node L2.
We know that L2 has two children, and they're elements, so we can return element E2.

It may not be immediately obvious that search is a logN operation. If that's the case, then take a piece of paper and draw out a 14-element list.

Adding elements to this list is also an O(logN) operation, unlike a normal linked-list (which is either O(1) or O(N) depending on whether it's a singly- or doubly-linked list). Here's how it works:

Find the last descendent sublist. This is again a recursive operation (so logN), which for every list element follows its right child.
If that descendent sublist has only 1 element, add the new element, and recompute the sizes of all parents.
If the sublist is full, you need to add another child to its parent; this is also a recursive operation, up the tree of lists.
You might have to add a new root element, where the left child is the previous root and the right element is the new element.

Confused? Here's a walk-through of adding the elements to the list shown above. It starts with a single element, which is the left child of the root (I'm keeping the numbering the same as in the 4-element list).

L1
+-- E0

When we add the next element, we can store it in the right child of the root:

L1
+-- E0
+-- E1

At this point our list is full, so we have to add another level. The original root of the list is the left child of the new root, and we add another list as the right child. This new list (L2) is where we put element E2.

L
+-- L1
|   +-- E0
|   +-- E1
+-- L2
    +-- E2

Best Answer

Related Solutions

Database Design Data Structures – Should Database Table Structure Match Its Intended Data Structure?

Design Efficient Random Access Queue Using LinkedList in Java

Related Topic