Inheriting two kinds of Lists into one Class

[gcalvin]

This is off the top of my head, and after a night of no sleep, so please pardon the stupidity that's likely to come next...

What about storing the actual data in an ArrayList, but always using add() so that it appends to the end, which is pretty quick (ArrayList is slow at inserts, but not bad at appends), and then storing the indexes in a LinkedList?

-Gary-

[rsiddharth]

...Maybe just a LinkedList will do for one part and as soon as you want to traverse the list (using an Iterator), copying the entire thing to an ArrayList and instantiate an Iterator on that can speed up things a bit...
kind regards,
Jos

I think this is a good idea. I will try to implement what you said.That is , for additions/removals use a LinkedList as before and implement my own iterator in combination with the ArrayList for traversals.

Does get() use the iterator to get the element at the index ??.

What about storing the actual data in an ArrayList, but always using add() so that it appends to the end, which is pretty quick (ArrayList is slow at inserts, but not bad at appends),...
-Gary-

But the requisite is that you *only* perform traversals and get() operations with ArrayList.

and then storing the indexes in a LinkedList?

What does this exactly mean. I am not able to grasp the sentence.:confused:

Period

Thank you Jos and Gary for your ideas .

[rsiddharth]

To recap :

Create a FastTraversalLinkedList that internally uses a LinkedList for rapid insertions and removals and an ArrayList for rapid traversals and get() operations.

I have written a truly working version of FastTraversalLinkedList . I tested the class using the Testing Framework given in "Thinking in Java" book . Here are the results of the test

------------------ FastTraversalLinkedList ------------------
 size     add     get     set iteradd  insert  remove    sort
   10     727      74     548    2534    1841    2345   24523
  100     366      72     459    1328     628     822  155047
 1000     443     125     779    1130     434     664 3062043
10000     459      74     645    1086     433     560 3326477
------------------------- LinkedList -------------------------
 size     add     get     set iteradd  insert  remove    sort
   10     460     105     518    1270     440    2739   10604
  100     386     128     463    1322     342     645  129504
 1000     380     727    1970    1085     348     529 2737974
10000     426   14642   21111    1125     365     488 3239869
------------------------- ArrayList -------------------------
 size     add     get     set iteradd  insert  remove    sort
   10     469      72     411    1193    4195     612   16619
  100     417      94     479    1048    3769     562  135063
 1000     496     141     441    1354    4223     869 2070159
10000     373      78     453    5803   13834    6152 3262256

You may download the source of FastTraversalLinkedList.java and the binary of the Test Framwork from here :
~Code~ - Frepository

The name of the file is FTLL.jar . I have packaged the archive in such a way that the test can be run by :

$ java -jar FastTLL.jar

The source of the Testing Framework that I have used can be downloaded from :
Thinking in Java 4th Edition Source Code

( for you information )
Files that make the Testing Framework :
* TIJ4/containers/Test.java
* TIJ4/containers/TestParam.java
* TIJ4/containers/Tester.java
* TIJ4/containers/ListPerformance.java

Period.

Thank you all for your support. Please let me know if you find a bug in FastTraversalLinkedList . :)