Page 2 of 2 FirstFirst 12
Results 21 to 23 of 23
  1. #21
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    952
    Rep Power
    5

    Default

    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-

  2. #22
    rsiddharth's Avatar
    rsiddharth is offline Member
    Join Date
    Feb 2010
    Location
    In Front of My Machine
    Posts
    13
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    ...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 ??.

    Quote Originally Posted by gcalvin View Post
    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.

    Quote Originally Posted by gcalvin View Post
    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 .
    Lover of Freedom and Simplicity .
    http://rsiddharth.wordpress.com/

  3. #23
    rsiddharth's Avatar
    rsiddharth is offline Member
    Join Date
    Feb 2010
    Location
    In Front of My Machine
    Posts
    13
    Rep Power
    0

    Lightbulb FastTraversalLinkedList

    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

    Java Code:
    ------------------ 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 Code:
    $ 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 . :)
    Lover of Freedom and Simplicity .
    http://rsiddharth.wordpress.com/

Page 2 of 2 FirstFirst 12

Similar Threads

  1. Array Lists and Club class
    By amekjian in forum New To Java
    Replies: 13
    Last Post: 11-03-2010, 01:42 AM
  2. Help with lists
    By datreta in forum New To Java
    Replies: 6
    Last Post: 10-29-2010, 12:33 PM
  3. How is this dog inheriting a bark?
    By fresh83 in forum New To Java
    Replies: 3
    Last Post: 07-05-2010, 02:33 AM
  4. 2 dimensional Lists
    By gapper in forum New To Java
    Replies: 4
    Last Post: 01-20-2008, 10:01 AM
  5. What kinds of classes needs to be final.
    By roots in forum New To Java
    Replies: 3
    Last Post: 01-03-2008, 01:54 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •