Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
2  
you said: "O(n) + O(n) > O(n) + O(1)" ... this is extremely not true; they are the same. In fact, in this specific example, 1 find + 1 insert is likely faster in an arraylist than a linkedlist (due to constant factors) –  sparkleshy Jan 12 '13 at 2:24
    
Good point, 2 * O(n) is still O(n). I don't know enough about the specifics of a Java linkedlist or arraylist to know that one would surely be faster or slower, come to think of it. I edited the OP to reflect that. –  The111 Jan 12 '13 at 3:10
    
it is pretty obvious: first, the implementations aren't important; they're just straightforward impls of vector and (doubly) linked-list. And simple profiling shows that linked lists have a constant factor of around three times vectors, iirc. It's a lot. Enough that you rarely want to use linked lists. –  sparkleshy Jan 12 '13 at 12:22

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
3  
We tend to discourage one line answers that don't explain anything. Can you please provide a bit of context why you think this is the best approach? –  maple_shaft Jan 12 '13 at 3:05
1  
Yeah, I (the OP) would be curious as well. I can sort of see how circular references can create problems, but I'd think if you design each class well enough you could avoid those problems (i.e. make sure that for every possible way to mutate one class, the other automatically updates to reflect it). I also will admit an ArrayList would probably be fine because it's not like these chains are going to be millions of elements long. But it still irks me to choose an implementation which is less than the most efficient. –  The111 Jan 12 '13 at 3:09
    
@maple_shaft :( verbosity is annoying –  sparkleshy Jan 12 '13 at 16:49
    
@The111 premature optimization. AND arraylists are so much faster than linkedlists for almost everything (like, including use-cases you'd expect you'd want a linkedlist for) prolly because cache locality or smth –  sparkleshy Jan 12 '13 at 16:52
    
@sparkleshy Thank you for capitulating to dude's demands. The annoying verbosity was helpful. Another thing which I didn't even think of - as you say, all the the elements will be on screen... which means no matter how I represent them I will already have an O(n) operation when I draw them all on a screen repaint! –  The111 Jan 12 '13 at 21:23

You really want to leverage Java-provided "list maintenance" functionality. Go with ease of use first and worry about performance later. "pre-optimization" is a dog chasing its tail.

Class Waypoint {
    string name;
    double lat;  // I'm not saying double is necessarily the ideal type here.
    double long;
    // other stuff as needed for GPX

   RouteCollection myRoutes; // all the routes containing this waypoint
}

Class Route {
    LinkedList<Waypoint> myRoute;
    string name;
    Waypoint start { return myRoute[0]; }
    Waypoint end { return myRoute[myRoute.Length-1] };
}

Class RouteCollection {
    ArrayList<Route> myRoutes;
    // maybe a dictionary/hash instead, the key being the Route.name perhaps
    // order is not important in this collection, I suspect.
}

Class WaypointJanitor {
    // keeps cross references in the various classes in sync
    // for example updates the Waypoint.myRoutes when a Route object is edited

    // I can see the main add/delete/insert functionality in this class,
    // passing routes & waypoint parameters. And all the complexity is contained, keeping your data structure classes clean and simple.
}

The UI Provides Context for Inserting

If the node belongs to a linked list, it will need to maintain a reference to its encompassing list

"if the node belongs.." This is confusing. Seems to me that in the UI I create routes/chains/tracks explicitly, giving each a name probably. Thus there is no question about. When I want to insert a waypoint I designate through the UI what route I'm manipulating. Further, any given waypoint (arbitrary lat/long coordinate) could be part of any number of routes; by explicitly selecting the route to edit there is no ambiguity.

share|improve this answer
    
Thanks. That seems like a reasonable suggestion. But it still bothers me that with this design, when a waypoint is chosen in the UI, even if we know without a doubt which route it belongs to, the route still will need to walk through its entire linked list from the beginning until it locates this waypoint so that it can insert something before it (please correct me if any of that is wrong). In my solution the waypoint itself (rather than the list) keeps track of its neighbors, so you never have to do O(N) search on a list. Maybe I'm just stubborn, but I'm still tempted to try it this way. –  The111 Jan 12 '13 at 6:15
    
just a wag - read this for possible inspiration: stackoverflow.com/questions/8725387/… 2 choices - the linkedList defining waypoint order, or some sorted collection but then I expect you need "previous" & "next" references. Off hand, to implement this wrap Waypoint in your original Node Class. Anyway, my spider-sense says users will not likely notice UI lag due to linear search during route editing. –  radarbob Jan 13 '13 at 8:18
    
Yeah, I ended up just going with an arraylist anyway, especially since as I noted in comments below, I have to go through my collection linearly to paint it all on screen anyway. Thanks for your thoughts though. :-) –  The111 Jan 13 '13 at 8:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.