Page 1 of 2 12 LastLast
Results 1 to 20 of 23
  1. #1
    rsiddharth's Avatar
    rsiddharth is offline Member
    Join Date
    Feb 2010
    Location
    In Front of My Machine
    Posts
    13
    Rep Power
    0

    Question Inheriting two kinds of Lists into one Class

    I want to know if its possible to implement an ArrayList and a LinkedList into a single class ?. What I exactly want to do is this :

    * Perform addition and removals of elements from the List using a LinkedList.
    * Perform traversals and searching of elements in the List using an ArrayList .

    I know this is possible by composition . But it is likely that it could not be very efficient as I will have to maintain two separate Lists ( an ArrayList and a LinkedList ).Meaning if I add an element through the LinkedList , then I will have to update my ArrayList accordingly.So this destroys the Whole idea of writing a List implementation which Fast and Efficient . Is it possible to implement the class using extension .

    Thank you for your Help.
    Lover of Freedom and Simplicity .
    http://rsiddharth.wordpress.com/

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

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

    Arrow FastTraversalList

    Why can't you do same in a single ArrayList. I didn't see any requirements to use multiples.
    I want to implement FastList wherein every operating is geared up for speed . I have learned that LinkedList is good at insertion and deletion , ArrayList is good at fetching elements at random. Therefore I thought a class which is a hybrid of LinkedList and ArrayList will be "Fast" .
    Last edited by rsiddharth; 12-07-2010 at 02:52 AM. Reason: Minor Edit
    Lover of Freedom and Simplicity .
    http://rsiddharth.wordpress.com/

  4. #4
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

  5. #5
    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 Eranga View Post
    Of course never it happens. Because the combination build-up lots of issues.
    So , are you suggesting that we can extend both LinkedList and ArrayList to a new class only through composition ?.
    Lover of Freedom and Simplicity .
    http://rsiddharth.wordpress.com/

  6. #6
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    11,797
    Rep Power
    19

    Default

    You can't extend from two classes in Java anyway.
    Even if you could, since both LinkedList and ArrayList hold their own lists then how would you wire the two together?

    Besides, how those lists are stored is key to how the two Lists work. It's what makes the LinkedList fast at one set of tasks, and the ArrayList faster at others.

  7. #7
    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 Tolls View Post
    You can't extend from two classes in Java anyway.
    Even if you could, since both LinkedList and ArrayList hold their own lists then how would you wire the two together?

    Besides, how those lists are stored is key to how the two Lists work. It's what makes the LinkedList fast at one set of tasks, and the ArrayList faster at others.
    Very True.I will use composition in my FastList class which as a LinkedList and an ArrayList. I use the LinkedList to make structural modification to the List and accordingly update my ArrayList. I will use the ArrayList for random access. The downside of this kind of implementation is , as we know, redundancy and up keeping overhead.

    Anyways I will come back to this thread once I have written some code .

    I thank Eranga and Tolls for their support.
    Last edited by rsiddharth; 12-07-2010 at 05:51 PM. Reason: grammer
    Lover of Freedom and Simplicity .
    http://rsiddharth.wordpress.com/

  8. #8
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    Quote Originally Posted by rsiddharth View Post
    Very True.I will use composition in my FastList class which as a LinkedList and an ArrayList. I use the LinkedList to make structural modification to the List and accordingly update my ArrayList. I will use the ArrayList for random access. The downside of this kind of implementation is , as we know, redundancy and up keeping overhead.

    Anyways I will come back to this thread once I have written some code .

    I thank Eranga and Tolls for their support.
    If what you're going for is speed, how are you going to achieve it while storing your data in two different collections? Seems to me it will have to be at least as slow as both of them.

    -Gary-

  9. #9
    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 gcalvin View Post
    If what you're going for is speed, how are you going to achieve it while storing your data in two different collections? Seems to me it will have to be at least as slow as both of them.

    -Gary-
    I agree. But I have to try and do something about it.I will come up with answer shortly.
    Lover of Freedom and Simplicity .
    http://rsiddharth.wordpress.com/

  10. #10
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Quote Originally Posted by rsiddharth View Post
    So , are you suggesting that we can extend both LinkedList and ArrayList to a new class only through composition ?.
    What I'm worried is, as gcalvin mentioned, by combining those two entites how can we speedup, both are working on with its own model.

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

    Lightbulb Code

    I have written the code . It works ( compiles and runs ) . A test proves that the FastTraversalLinkedList is faster for set operation .

    Here is the code

    Java Code:
    /**
     * @author siddharth.
     */
    
    package containers;
    import static util.Print.*;
    import java.util.*;
    
    
    
    public class FastTraversalLinkedList<E> extends LinkedList<E>    {
        List<E> arryList;
        int arryListsize;
        public FastTraversalLinkedList() {
    	super();
    	arryList = new ArrayList<E>();
    	arryListsize=0;
        }
        public FastTraversalLinkedList(Collection<? extends E> c) {
    	super(c);
    	arryList= new ArrayList<E>();
    	arryListsize=0;
        }
        public E set(int index,E element) {
    	if(arryListsize!=this.size()) {
    	    arryList.clear();
    	    arryList.addAll(this);
    	    arryListsize=arryList.size();
    	}
    	E previous=arryList.set(index,element);
    	return previous;
        }
        public E get(int index) {
    	if(arryListsize!=this.size()) {
    	    arryList.clear();
    	    arryList.addAll(this);
    	    arryListsize=arryList.size();
    	}
    	return arryList.get(index);
        }
        public String toString() {
    	if(arryListsize!=this.size()) {
    	    arryList.clear();
    	    arryList.addAll(this);
    	    arryListsize=arryList.size();
    	}
    	StringBuilder sb = new StringBuilder();
    	sb.append("[");
    	for(E e:arryList) {
    	    sb.append(e);
    	    sb.append(", ");
    	}
    	sb.delete(sb.length()-2,sb.length());
    	sb.append("]");
    	return sb.toString();
        }
        public static void main(String[] args) {
    	// Adding and Set() operation in FastTraversalLinkedList.
    	print("FastTraversalLinkedList:");
    	FastTraversalLinkedList<Integer> fll = new FastTraversalLinkedList<Integer>();
    	for(int i=0;i<20;i++) {
    	    fll.add(i);
    	}
    	print("After adding: ");
    	print(fll);
    	long start1=System.nanoTime();
    	for(int i=19;i>=0;i--) {
    	    fll.set(19-i,i);
    	}
    	print("After set() operation:");
    	print(fll);
    	long duration1=(System.nanoTime()-start1)/20;
    	print("Duration for one set() operation: "+duration1);
    
    
    	// Adding and Set() operation in LinkedList
    	print("LinkedList:");
    	LinkedList<Integer> ll = new LinkedList<Integer>();
    	for(int i=0;i<20;i++) {
    	    ll.add(i);
    	}
    	print("After adding: ");
    	print(ll);
    	long start2=System.nanoTime();
    	for(int i=19;i>=0;i--) {
    	    fll.set(19-i,i);
    	}
    	print("After set() operation:");
    	print(fll);
    	long duration2=(System.nanoTime()-start2)/20;
    	print("Duration for one set() operation: "+duration2);
        }
    }
    The Output is here :

    Java Code:
    [B]FastTraversalLinkedList:[/B]
    After adding: 
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    After set() operation:
    [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    Duration for one set() operation: 10972
    [B]LinkedList:[/B]
    After adding: 
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    After set() operation:
    [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    Duration for one set() operation: 23425
    But this code is buggy! . Yes . Its very obvious but I will explain. Say if add elements 1 to 5 to the FastTraversalLinkedList ,then I use the set() operation to set the 3rd element in the FastTraversalLinkedList to be 10 . Now my modified FastTraversalLinkedList will have [1,2,10,4,5] ( It must be noted here that the ArrayList arryList will only reflect this but not the LinkedList ( its not updated ). If I add '6' to the end of my FastTraversalLinkedList and use the set() again to set the 1st element to be 20, then my list will become [20,2,3,4,5,6] !!. Observe that the element '10' has vanished from the List !.

    Period


    I am working on the code anyway . I will post a better version of the FastTraversalLinkedList: soon . If you have any ideas please let me know . Thank you for your help !.
    Lover of Freedom and Simplicity .
    http://rsiddharth.wordpress.com/

  12. #12
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,336
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by rsiddharth View Post
    I have written the code . It works ( compiles and runs ) . A test proves that the FastTraversalLinkedList is faster for set operation .

    Java Code:
        public E set(int index,E element) {
    	if(arryListsize!=this.size()) {
    	    arryList.clear();
    	    arryList.addAll(this);
    	    arryListsize=arryList.size();
    	}
    	E previous=arryList.set(index,element);
    	return previous;
        }
    How can your code be faster than the 'standard' Lists? Your set operation does more work than both of the other Lists ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  13. #13
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

  14. #14
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    11,797
    Rep Power
    19

    Default

    Quote Originally Posted by JosAH View Post
    How can your code be faster than the 'standard' Lists? Your set operation does more work than both of the other Lists ...

    kind regards,

    Jos
    Well, his set() method doesn't do anything with the LinkedList list as far as I can see. At least as a starter. I'm not going to delve any deeper than that since the whole concept makes no sense to me.

    ETA: Oh, and the second test also test the FastLinkedList class as well, and not LinkedList.
    So it's all a bit of a mess.

  15. #15
    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
    How can your code be faster than the 'standard' Lists? Your set operation does more work than both of the other Lists ...

    kind regards,

    Jos
    The Output says its faster. I have pasted the Output in my previous post. I must concede that the present code is buggy and I have explained the problem.
    Lover of Freedom and Simplicity .
    http://rsiddharth.wordpress.com/

  16. #16
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    11,797
    Rep Power
    19

    Default

    Your test is wrong then.

    In fact, as I say above, that code is timing the same FastLinkedList.

    Come on, think about it. How can this actually be faster if it was coded the way you suggest it should be (but isn't currently)?

  17. #17
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    11,797
    Rep Power
    19

    Default

    I've just run your code and got this:

    FastTraversalLinkedList:
    After adding:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    After set() operation:
    [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    Duration for one set() operation: 5222
    LinkedList:
    After adding:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    After set() operation:
    [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    Duration for one set() operation: 5011

    Which is understandable because you are timing fll both times.

    Changing the second loop of set()s to use ll I get this:

    FastTraversalLinkedList:
    After adding:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    After set() operation:
    [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    Duration for one set() operation: 7084
    LinkedList:
    After adding:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    After set() operation:
    [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    Duration for one set() operation: 5318

    ETA: But, of course, 20 times is far too few to actually be able to time this. Run this whole test a hundred or even a thousand times and see what comes out.
    Last edited by Tolls; 12-08-2010 at 05:21 PM.

  18. #18
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    11,797
    Rep Power
    19

    Default

    Just changed the code a bit to run that test 1000 times, and added in a call to super.set() in the set() method:
    Java Code:
    public class FastTraversalLinkedList<E> extends LinkedList<E> {
        List<E> arryList;
        int arryListsize;
    
        public FastTraversalLinkedList() {
            super();
            arryList = new ArrayList<E>();
            arryListsize = 0;
        }
    
        public FastTraversalLinkedList(Collection<? extends E> c) {
            super(c);
            arryList = new ArrayList<E>();
            arryListsize = 0;
        }
    
        public E set(int index, E element) {
            if (arryListsize != this.size()) {
                arryList.clear();
                arryList.addAll(this);
                arryListsize = arryList.size();
            }
            E previous = arryList.set(index, element);
            super.set(index, element);
            return previous;
        }
    
        public E get(int index) {
            if (arryListsize != this.size()) {
                arryList.clear();
                arryList.addAll(this);
                arryListsize = arryList.size();
            }
            return arryList.get(index);
        }
    
        public String toString() {
            if (arryListsize != this.size()) {
                arryList.clear();
                arryList.addAll(this);
                arryListsize = arryList.size();
            }
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            for (E e : arryList) {
                sb.append(e);
                sb.append(", ");
            }
            sb.delete(sb.length() - 2, sb.length());
            sb.append("]");
            return sb.toString();
        }
    
        public static void main(String[] args) {
            TestResult tr = new TestResult(0, 0);
            for (int i = 0; i < 1000; i++) {
                tr.add(test());
            }
            System.out.println("Final times = fll " + tr.fll + " ll " + tr.ll);
        }
    
        private static class TestResult {
            long fll = 0;
            long ll = 0;
    
            TestResult(long fll, long ll) {
                this.fll = fll;
                this.ll = ll;
            }
    
            void add(TestResult tr) {
                this.fll += tr.fll;
                this.ll += tr.ll;
            }
        }
    
        public static TestResult test() {
            // Adding and Set() operation in FastTraversalLinkedList.
            FastTraversalLinkedList<Integer> fll = new FastTraversalLinkedList<Integer>();
            for (int i = 0; i < 20; i++) {
                fll.add(i);
            }
            long start1 = System.nanoTime();
            for (int i = 19; i >= 0; i--) {
                fll.set(19 - i, i);
            }
            long duration1 = (System.nanoTime() - start1) / 20;
    
    
            // Adding and Set() operation in LinkedList
            LinkedList<Integer> ll = new LinkedList<Integer>();
            for (int i = 0; i < 20; i++) {
                ll.add(i);
            }
            long start2 = System.nanoTime();
            for (int i = 19; i >= 0; i--) {
                ll.set(19 - i, i);
            }
            long duration2 = (System.nanoTime() - start2) / 20;
            
            return new TestResult(duration1, duration2);
        }
    }
    This gives:
    Final times = fll 439233 ll 122215

    Which has got to be slightly more accurate.
    Indeed it is pretty consistently showing the fll to take at least 3 times longer.

  19. #19
    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 Tolls View Post
    Just changed the code a bit to run that test 1000 times, and added in a call to super.set() in the set() method:
    Java Code:
    public class FastTraversalLinkedList<E> extends LinkedList<E> {
        List<E> arryList;
        int arryListsize;
    
        public FastTraversalLinkedList() {
            super();
            arryList = new ArrayList<E>();
            arryListsize = 0;
        }
    
        public FastTraversalLinkedList(Collection<? extends E> c) {
            super(c);
            arryList = new ArrayList<E>();
            arryListsize = 0;
        }
    
       ...
    This gives:
    Final times = fll 439233 ll 122215

    Which has got to be slightly more accurate.
    Indeed it is pretty consistently showing the fll to take at least 3 times longer.
    I am real sorry for goofing up the test . Thanks Toll for rewriting it beautifully and making corrections in the set() method. It apparently futile to move forward with writing this kind of a List.

    Period.

    The idea of writing this kind of List ( a List which does additions/removals at the speed of a LinkedList and traversals/random fetching from List at the speed of an ArrayList) didn't crop up from my mind , but I found it as an Exercise given in Bruce Eckel's "Thinking in Java" .

    The Exercise says :
    Create a FastTraversalLinkedList that internally uses a LinkedList for rapid insertions and removals and an ArrayList for rapid traversals and get() operations.
    I was breaking my head with this exercise for a week or so . I didn't get any answers . I came here.
    Lover of Freedom and Simplicity .
    http://rsiddharth.wordpress.com/

  20. #20
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,336
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by rsiddharth View Post
    I was breaking my head with this exercise for a week or so . I didn't get any answers . I came here.
    There are no failed experiments; you've learned from the exercise. 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 but keep in mind that there are two different List implementations for good reasons. I think it's brave to start such a complex experiment like you did.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Page 1 of 2 12 LastLast

Similar Threads

  1. Array Lists and Club class
    By amekjian in forum New To Java
    Replies: 13
    Last Post: 11-03-2010, 12:42 AM
  2. Help with lists
    By datreta in forum New To Java
    Replies: 6
    Last Post: 10-29-2010, 11:33 AM
  3. How is this dog inheriting a bark?
    By fresh83 in forum New To Java
    Replies: 3
    Last Post: 07-05-2010, 01:33 AM
  4. 2 dimensional Lists
    By gapper in forum New To Java
    Replies: 4
    Last Post: 01-20-2008, 09: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, 12: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
  •