• 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

 
Ranch Hand
Posts: 203
Eclipse IDE Oracle Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Guys,
Can you tell me on which the better searching can be done , it is the array list or linked list ...? and suppose I have to insert an item which is better option arraylist or linked list..? I know this question is being put up many times but I want an detail one result which can justfied the explnation..?
 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
First explain to us, in your own words, in what way the operation between these two types differs.
 
Saral Saxena
Ranch Hand
Posts: 203
Eclipse IDE Oracle Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:First explain to us, in your own words, in what way the operation between these two types differs.



What I have discovered that In a LinkedList, each element is linked to its previous and next element making it easier to delete or insert in the middle of the list. A ArrayList is more as its name subjects used as an array.Performance is similar, though LinkedList is optimized when inserting elements before the end of the list, where ArrayList is optimized when adding elements at the end. But can you guys give me a justfied anwer which will prove my point..!!
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You have the basic idea right: in a linked list, the list consist of nodes, each of which holds an element of the list and a reference to the next node (and also the previous node, if it is a doubly-linked list); in an array list, the list holds its elements in an array (contiguously in memory).

Because of these different ways that the elements are stored, operations that you can do on the list have different performance characteristics.

For example, if you want to get element number X in a linked list, you have to start at the beginning of the linked list, and walk over the nodes until you get to element X. In an ArrayList, you can immediately find element number X - you don't need to walk over elements 0, 1, 2, ... because in an ArrayList you know that element X is at position X * N (where N is the size of an element in the array). So, for finding an element by index, an ArrayList is much more efficient than a LinkedList.

On the other hand, if you want to insert a new element at position X in a LinkedList, all you have to do is make element X - 1 point to the new element as its next element, and make the new element point to the old element X as its next element. In an ArrayList, you would have to shift all elements in the array by 1 position (which means moving a large amount of data, if the list is large) to make room for the new element at position X. So, for inserting an element somewhere in the middle of the list, a LinkedList is much more efficient than an ArrayList.

It's important to understand these differences when choosing whether to use a LinkedList or an ArrayList. Which one will be more efficient for your particular application depends on what operations your application needs to do with the list. So, find out what your application needs to do with the list, and then study whether those operations are more efficient on a LinkedList or on an ArrayList.

It would be an interesting exercise to make two versions of your program: one with a LinkedList and one with an ArrayList, and compare their performance.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jesper de Jong wrote:...if you want to get element number X in a linked list, you have to start at the beginning of the linked list, and walk over the nodes until you get to element X. In an ArrayList, you can immediately find element number X - you don't need to walk over elements 0, 1, 2, ... because in an ArrayList you know that element X is at position X * N (where N is the size of an element in the array). So, for finding an element by index, an ArrayList is much more efficient than a LinkedList....


@Saral: Further to what Jesper said: there is an interface that a surprising number of even quite experienced Java programmers forget about called RandomAccess.
It is a "marker" interface (ie, it has no methods - like java.lang.Cloneable) that is supposed to indicate whether a List has good "random" (ie, direct) access to elements via their index.

You will notice that ArrayList implements it, and LinkedList doesn't, which is an indicator of precisely what Jesper was talking about; and you should remember to add it (or not) for any List class that you create too.

Winston
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic