Skip to main content
ICT
Lesson AB27 - Java Lists and Iterators
  
Main   Previous Next
 

E. LinkedList vs ArrayList page 7 of 10

An important aspect of good programming is to choose the best data structure to solve a particular problem. Here are some advantages and disadvantages of using one versus the other — LinkedList vs ArrayList:

Operation LinkedList ArrayList
Searching Best performance is O(N) because the list must be searched sequentially even if it is ordered. Best performance is O(log N) if the list is ordered because a binary search can be used.
Insertion/deletion Performance is O(1) no matter how big the list is. At most, two elements are affected (see Lesson AB30). Performance is O(N) because many elements of the list may have to be moved.
Accessing by index Performance is O(N). Performance is O(1).

When designing a program to build a telephone directory, for example, ArrayList might be a better choice than LinkedList. The directory would not change often, so insertion/deletion would not be a major concern. However, fast searching would be important.

On the other hand, LinkedList might be better for a print spooler program. Print jobs will frequently be inserted (when a new print request is received) and deleted (when the print job is sent to the physical printer). The list could even be prioritized so that small print jobs would be inserted near the front of the list. However, searching through the list for a particular print job would not be a common occurrence.

 
Main   Previous Next
Contact
 © ICT 2006, All Rights Reserved.