Ordered Doubly Linked List

[Mark Herschberg]

Does anyone have some good code for an ordered doubly linked list? It's actually trickier then I expected.
I created an object which contains an int value, as well as a pointer to a previous and next object. the catch is, I need it to be ordered.
I'm not sure I want to bother with a TreeSet. Seems like a hassle, because doing the in comparison is pretty strightfoward and lightweight. Also, most of the time, I'll be doing inserts and removals near the head of the list, so a tree won't save me much time, and may even be more expensive to constantly rebalance it.
The catch is when creating it, I'm always running into null pointer exceptions. I either need to handle a couple base cases on both ends (0-1-2 elements in list to start, or adding to last or second to last element), or I need to keep direct references to two elements at once, either current and previous, or current and next.
I'm just wondering if anyone has an implamentation I could grab.
--Mark

[John Lee]

There is one link I find on internet:
http://www.cs.rochester.edu/u/brown/172/assts/DblLnk.html
Hope this helps.

[John Lee]

Some sample code by Liyan Zhang:
http://www.cs.unr.edu/~lzhang/CppApp.html#DbList

[Mark Herschberg]

I appreciate the links, but neither is helpful. The first link describes the requirements, but does not include any sample code. In the second link the double linked list was not ordered.
--Mark

[John Lee]

The definition of Ordered Doubly Linked List:
Ordered doubly-linked list: list items are placed into the list in order specified by the value of one data field, called the key field. Each item is linked both to the previous item in the list and the next item in the list.
Type definition -- see type definition for V

Operations:
Add to list -- may occur at beginning, middle, or end of list depending on key field value of specific item to be added. New item must be connected to both previous and next items in list; previous item and next item in list must both be connected to new item.
Delete from list -- may occur at beginning, middle, or end of list depending on specific item to be deleted. Requires also connecting "prev" field of item after deleted item to item before deleted item.
Traverse/search list -- always sequential, from beginning of list to end of list. Can also reverse direction on traversal/search.
http://www.gpc.peachnet.edu/~jbenson/csci1302/ddsnotes.htm

[John Lee]

Originally posted by Mark Herschberg:
The catch is when creating it, I'm always running into null pointer exceptions. I either need to handle a couple base cases on both ends (0-1-2 elements in list to start, or adding to last or second to last element), or I need to keep direct references to two elements at once, either current and previous, or current and next.

I think to create a Ordered Doubly Linked List, some values will be provided, which will become the key fields of each element in Ordered Doubly Linked List.
Start from first values, the only element will have,
key field = vale;
forward point = null;
backward point = null;
add second value to the list,
compare first and second values, if second value is greater than first value, then the second element will have:
key field = value;
forward point = null;
backward point = first element;
for first element:
key field = value;
forward point = second element;
backward point = null;
add third value to list, follow the binary search algorithm,
.........
So eventually you will create the Ordered Doubly Linked List.
Then define delete, insert, search methods. Insert is the same process to create the list. Delete is the reverse process to that. Search is similar to binary search algorithm, because my understanding is: the only big difference between Ordered Doubly Linked List and binary tree is: in Ordered Doubly Linked List, everything is Doubly Linked.

[Mark Herschberg]

Apparently I'm not being clear.
I know what a double linked ordered list is.
I created an implementation of one.
I actually created a few impelmentations.
I'm not sure if they are as efficent as possible. Rather then try to optimize mine, and reinvent the wheel, I'd prefer to use something someone else created. I am looking for source code for such a list.
--Mark

[Jim Yingst]

Just off the top of my head, I'd probably look at the implementation of java.util.LinkedList. Assuming it's not already adequate for your needs, you can probably speed it up by modifying it to take an int value directly rather than an Object. (Skipping a lot of annoying object creation/destruction and casting.) There are probably other implementations out there closer to what you want, but I don't know where offhand (Jakarta commons?) and haven't time to look at the moment. Will check later if no one else does.
Also, it seems that the standard "Intermediate Java" answer would be "just use a LinkedList" - since you evidently want something more performant, perhaps this topic would do better in Performance?

[David O'Meara]

I'm coming in late, but do you really need a doubly linked list?
I'm thinking that using a plain old List (like an ArrayList) plus a Comparator to sort, then you can use Collections.sort(List, Comparator) for sorting, and get the reverse list using Collections.reverse(List)
There are two immediate problems I see with this:
The first is that reverse is destructive (ie it reverses the current List rather than returning a new list that is the reverse of the original). You can get around this using Collections.copy to clone the List.
The second problem is that there isn't any real relationship between two lists. If you are looking at item 7 on the 'forward' list and want to see the previous, item, you need to find that object in the reverse list and go forward one.
How hard would it be to provide a wrapper on the above behaviour and use the List/Collections built in functionality to provide a Doubly Linked List?
Dave

[Mark Herschberg]

Originally posted by David O'Meara:
I'm coming in late, but do you really need a doubly linked list?
I'm thinking that using a plain old List (like an ArrayList) plus a Comparator to sort, then you can use Collections.sort(List, Comparator) for sorting, and get the reverse list using Collections.reverse(List)

This list will be used to store limit orders in my trading simulation program. Here is the behavior.
1) People will be doing arbitrary inserts every few miliseconds, but most inserts will be towards the front or middle of the list.
2) There will be lookups/removals on this list at the same frequency. 99% of the time, these lookups are done in order, i.e. I will first lookup/remove the first item, then the second, and so forth.
3) The comparison is done on an int.

My thoughts for using a doubly linked list were as follows:
The list will be changing dynamically enough that sorting it would be inefficent. I need to keep it always ordered.
People may potnetially change elements, including potentially the int on which the item is sorted, or simply cancel their orders removing them entirely. I was thinking of also having a hashtable mapping to the elements, allowing for quick direct reference by the unique ID (order ID) for each element. If I want to use a hashtable, I need a doubly linked list, so when the item is removed, the neighering elements can be linked to each other.
I need to double check on the weighting of the change/removal described above. It may be rare enough that I can take the hit of searching the list and just using a regular linked list, sans hashtable.

Originally posted by Jim Yingst:
Just off the top of my head, I'd probably look at the implementation of java.util.LinkedList. Assuming it's not already adequate for your needs, you can probably speed it up by modifying it to take an int value directly rather than an Object.
...
Also, it seems that the standard "Intermediate Java" answer would be "just use a LinkedList" - since you evidently want something more performant, perhaps this topic would do better in Performance?

Yeah, but I'd have to add back links and modify all appropriate methods. And it has methods I don't really need. Basically, I was hoping someone would say, "we did that in my CS 301 class, here's some sample code." Either that, or someone would comment about theoretical limitations and minimal cost of operating on such a list (but I wasn't really expecting the latter). I figured this isn't a Beginning Java question, but it is a fairly basic data structure, so it's not too hard.

--Mark

[Jim Yingst]

Ah, I now see that when you say "ordered" you seem to mean what I would call "sorted". (I think.) Would it kill you to use terminology consistent with the Java collections framework? Anyway in that case I see that LinkedList is not as close a match as I thought, for what you want. I suppose I'd probably check a good algorithms book (which I don't have with me at the moment). I'm guessing it wouldn't be too much trouble to convert something from C/C++ or whatever, for something like this - so don't limit yourself to Java implementations.
[ January 02, 2003: Message edited by: Jim Yingst ]