Win a copy of Node.js Design Patterns: Design and implement production-grade Node.js applications using proven patterns and techniques this week in the Server-Side JavaScript and NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Difference btwn LinkedList and ArrayList?

 
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi,

i got the difference from sun's tutorial, which says, "If you need to support random access, without inserting or removing elements from any place other than the end, than ArrayList offers the optimal collection. If, however, you need to frequently add and remove elements from the middle of the list and only access the list elements sequentially then LinkedList offers the better implementation." The content i read from http://java.sun.com/developer/onlineTraining/collections/Collection.html#ArrayListLinkedListClasses

But by keeping API in mind, both these classes implements List interface where in which the methods like get/set() and realted to it are used to add or remove object at any place. then why is that they says that ArrayList does not support addition or deletion at any place rather than only at end.

better to breathe freely if the clarifications are with sample code. thanks.
 
Ranch Hand
Posts: 3271
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Check this out and see if it answers your question.
 
lowercase baba
Posts: 13003
66
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Even if both implement the ability to add/remove and element, that doesn't mean both can do it efficiently. the only way to GET an i-th element from a linked list is to start at the front, step forward through each one, counting which element you're on. If i want the 1,000,000th element, it's gonna take a while to get there. with an array list, i can jump straight to it.

HOWEVER, if i'm AT the 500,000th element, and i want to insert something after that one, but preserve the order of the rest, a linked list just creates a new node on the heap, change 2 references (the new node now refers to where the 500,000th used to refer, and the 500,000th now refers to the newly created).

to insert into an array list, you have to make a new, larger array, copy everything over and shifting the top half to a one-higher index, and putting hte new element into the arraylist.

So, it's not a question of what you can or can't do. it's a question of what you can or can't do EFFICIENTLY.
 
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


to insert into an array list, you have to make a new, larger array, copy everything over and shifting the top half to a one-higher index, and putting hte new element into the arraylist.



Hey Fred,
The K&B book on page 426 says

ArrayList: Think of this as a growable array


Makes me think that the array grows automatically whn u insert new elements at the end....Then why do you say that you have to make a new larger array and copy everything over....

[ August 12, 2004: Message edited by: Murtuza Akhtari ]
 
Corey McGlone
Ranch Hand
Posts: 3271
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Murtuza Akhtari:

Makes me think that the array grows automatically whn u insert new elements at the end....Then why do you say that you have to make a new larger array and copy everything over....


[ August 12, 2004: Message edited by: Murtuza Akhtari ]



This really has to do with how the data object is implemented, not how you use it. Certainly, LinkedList and rrayList both implement the List interface so they, therefore, offer the capability to get an item at a specific and retrieve an item at a specific index.

However, how it's actually done "under the covers" is very different. The way a LinkedList is implemented, it is very easy to insert an element at a specific point, but it's quite time-consuming to get to a particular element as you have to step over each element in the list. An ArrayList, on the other hand, has the opposite situation. It's easy to get to a specific element, but it's time-consuming to add an element to the beginning or middle of the list.

Take a look at the link I pointed out earlier. Sepcifically, look at the benchmark table that shows how long various operations take using different List implementations. Notice that the insert takes 281ms for an ArrayList and only 62ms for a LinkedList. Meanwhile, when it came to getting an item from the list, it took 3328ms for the LinkedList and only 406ms for the ArrayList.

As you can see from those numbers, the various List implementations are very different. They all implement the List interface so you use them all in an identical fashion but which one you should be using is really dependent upon the context in which you plan to use it.

Read that article. It's excellent.
 
Murtuza Akhtari
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Corey !!

That link helped !!
[ August 12, 2004: Message edited by: Murtuza Akhtari ]
 
fred rosenberger
lowercase baba
Posts: 13003
66
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

the array grows automatically whn u insert new elements at the end



I don't have to do all the work of allocating a new array, copying and inserting. but somebody does... and it's the JVM.

An arrayList is IS growable. but How does it grow? when it's created, your given a hunk of memory, probably just big enough for what you need (maybe a little bigger, if the JVM is smart enough (and it usually is)). your program runs, more memory is allocated for other things... and now you need to expand your array. but there probably isn't any memory available at the end of your array. You can most likely GET memory, but not contiguous to your array.

so, the JVM has to get a new larger hunk from somewhere else, copy everything over, update the references you have to your array (which is an interesting issue in and of itself), and THEN add your new data at the end of that.

To you, it looks like your array just grew in size. but there could have been a LOT going on behind the curtains...
[ August 13, 2004: Message edited by: fred rosenberger ]
 
Murtuza Akhtari
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So wht happens to the first array??

Is it a candidate for System.gc() ?
 
Corey McGlone
Ranch Hand
Posts: 3271
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Murtuza Akhtari:
So wht happens to the first array??

Is it a candidate for System.gc() ?



Most likely. If the add() method of your list needed to allocate a new array to hold all of the objects, the old array is probably just tossed away and can be picked up by garbage collection. Wasteful, huh?

That's just one of the reasons a LinkedList is superior to an ArrayList when you need to do a lot of adding and removing of elements.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic