• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

ArrayList vs. LinkedList

 
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

Why and how is the linkedList good for fast insertion and deletion while the arraylist good for fast iteration and retrieval?

Also, why and how is the LinkedHashMap fast for iteration and slow for insertion and deletion ?


Regards,
Puja
 
Ranch Hand
Posts: 281
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Search these forums you will get a lot of answers...

to start with -> check here and here

 
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
ArrayList's are stored in contiguous memory, which means random access can be done using "pointer arithmetic" therefore has constant time and is very fast. Insertion or Deletion from anywhere but the end, however, requires that the remaining data elements have to be moved and a possible resizing memory allocation may have to occur. Adds/Removes from anywhere but the end are expensive.

LinkedLists are not stored in contiguous memory and just keep a reference to the next an previous nodes. This means that middle inserts/deletes are fast (just reassign the node references), but you can only do linear lookups because you have to traverse (non-contiguous means you can't use math to find the nth element).

LinkedHashMap contains additional data to ensure iteration order. Because that data must be managed, slower inserts/deletes. Because it is managed, faster interation (O(1)).



 
Greenhorn
Posts: 24
Android Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Puja,

The fact why LinkedList is good for fast insertion/deletion and ArrayList is good for fast iteration/retrieval lies in the way they are implemented.

ArrayList
The ArrayList saves elements in a normal array. This means it can access elements by array[index_number]. When deleting elements, the ArrayList moves all elements after the current index, one index to the left. With many elements this takes some time. The same goes for inserting elements at a specific index: all elements >= than the index get moved one to the right.

To handle increasing number of elements, the backing array sometimes needs to grow. When this is necessary all elements in the current array get moved to a bigger array. This happens, if necessary, when you add elements. This takes some extra time.

LinkedList
A LinkedList on the other hand saves its element in an entirely different way. Each element in an LinkedList, keeps a reference to the element before and after it in the List. So you get sort of a chain. Like:
Element 1 <--> Element 2 <--> Element 3 <--> Element 4

Now, when you remove an element, say Element 2, Element 1 will refer to Element 3 as its next element, and Element 3 will refer to Element 1 as its element before. This results in:
Element 1 <--> Element 3 <--> Element 4

So when deleting an element, this results in only two operations:
  • Change Element 1's next reference to Element 3
  • Change Element 3's next reference to Element 1

  • This makes deletion very fast in LinkedList. You don't have to move all elements beyond it like with an ArrayList. The same goes for inserting elements at a specific index:
  • Let the element before refer to the inserted element as its next element
  • Let the element after refer to the inserted element as its previous element

  • Faster again. However, when traversing and retrieving specific elements, you have to go through the elements one by one. So when you want to get element 4, the following happens:
  • Get first element's next element
  • Get second element's next element
  • Get third element's next element and return it

  • (This is just an illustration. In reality the List will traverse backwards when (size of list / 2) <= index. Starting with the last element.)

    In this case ArrayList would be faster, as it can access the element directly in the array.
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    reply
      Bookmark Topic Watch Topic
    • New Topic