Java - différence d'implémentation LinkedList et ArrayList ? -Débordement de pile

Possible Duplicate:
When to use LinkedList<> over ArrayList<>?

I saw the API for the ArrayList and LinkedList and it seems to be same. Apart from their performance difference is there any difference in terms of adding, deleting and iterating the List.

List arrList = new ArrayList();

List linList = new LinkedList();

The List arrList or linList reference is actually implementing the corresponding class. What does this actually mean?

I am not 100% sure what you mean when you ask "What does this actually mean?", but here is a guess.

Consider code like this:

interface Interface
{
   void foo();
}

class Implementation
    implements Interface
{
    public void foo() { }
    public void bar() { }
}

public class Main
{
    public static void main(final String[] argv)
    {
        Interface a;
        Implementation b;

        a = new Implementation();
        b = a;

        a.foo();
        b.foo();
        a.bar(); <-  won't compile
        b.bar();
    }
}

Interface a; and Implementation b; both point at the same object, but only the reference to "b" has access to the "bar" method.

So, in your example, any methods that are in the List interface are accessible to both arrList and linList, but any methods that they provide in addition to the List interface wont be callable without a cast. You can (and should in most cases) treat ArrayList and LinkedList as a List.

For the specifics of inserting/adding/deleting from the different lists, you generally should not care. Both behave the same way from the point of view of the end result (eg. the same sequence of method calls with the same data will result in the same result, just the internal layout will be different).

As far as your first question goes: their performance and their memory usage the only differences that will matter to you (the third one, their actual implementation details, aren't your concern.) LinkedLists use more memory, and getting, say, the 22nd element by walking through the list from the head is very slow; but they're terrific as far as adding and removing elements in the middle of the list. ArrayLists use less memory, and getting the 22nd element is very fast -- but inserting or removing an element in the middle takes time proportional to the size of the list.

As far as your second question goes: the statement that the reference is "actually implementing the list" is just wrong, so I don't really know how to answer it. The reference variable refers to an object that implements the List interface; both of these two classes implement that interface, so a reference of type List can refer to objects of either class.

There's a good discussion of the pros and cons of these two List implementations in the Java tutorial. See the topic on List Implementations.

ArrayList is backed by an array which is resized when needed. LinkedList is made of of element nodes with references pointing to the previous and next node. There are numerous posts on this site discussing the differences, just search for them.

Possible Duplicate:
When to use LinkedList<> over ArrayList<>?

I saw the API for the ArrayList and LinkedList and it seems to be same. Apart from their performance difference is there any difference in terms of adding, deleting and iterating the List.

List arrList = new ArrayList();

List linList = new LinkedList();

The List arrList or linList reference is actually implementing the corresponding class. What does this actually mean?

I am not 100% sure what you mean when you ask "What does this actually mean?", but here is a guess.

Consider code like this:

interface Interface
{
   void foo();
}

class Implementation
    implements Interface
{
    public void foo() { }
    public void bar() { }
}

public class Main
{
    public static void main(final String[] argv)
    {
        Interface a;
        Implementation b;

        a = new Implementation();
        b = a;

        a.foo();
        b.foo();
        a.bar(); <-  won't compile
        b.bar();
    }
}

Interface a; and Implementation b; both point at the same object, but only the reference to "b" has access to the "bar" method.

So, in your example, any methods that are in the List interface are accessible to both arrList and linList, but any methods that they provide in addition to the List interface wont be callable without a cast. You can (and should in most cases) treat ArrayList and LinkedList as a List.

For the specifics of inserting/adding/deleting from the different lists, you generally should not care. Both behave the same way from the point of view of the end result (eg. the same sequence of method calls with the same data will result in the same result, just the internal layout will be different).

As far as your first question goes: their performance and their memory usage the only differences that will matter to you (the third one, their actual implementation details, aren't your concern.) LinkedLists use more memory, and getting, say, the 22nd element by walking through the list from the head is very slow; but they're terrific as far as adding and removing elements in the middle of the list. ArrayLists use less memory, and getting the 22nd element is very fast -- but inserting or removing an element in the middle takes time proportional to the size of the list.

As far as your second question goes: the statement that the reference is "actually implementing the list" is just wrong, so I don't really know how to answer it. The reference variable refers to an object that implements the List interface; both of these two classes implement that interface, so a reference of type List can refer to objects of either class.

There's a good discussion of the pros and cons of these two List implementations in the Java tutorial. See the topic on List Implementations.

ArrayList is backed by an array which is resized when needed. LinkedList is made of of element nodes with references pointing to the previous and next node. There are numerous posts on this site discussing the differences, just search for them.

Source