Linked List vs Array List (Java)

Once upon a time I talked to a real strong technical guy, he said that data structures & algorithms are really important.

They are important, not only in interviews, but also if you are really coding something. In some companies you could always “glue” something together by applying this framework and that library, while in real coding after all this is your understanding in how a problem can be solved.

After a year or 2 focusing on trying all sorts of framework out & gluing, lets have some data structure revisited….

As a data structure revisited, would like to ask a question I faced:

Linked List vs Array List (Java)

First one need to understand abstract data type you studied in Intro to data structure could be way different from Language implementation, like Java. Or like javascript, there is no built in linkedlist, and even array is not an array but a hashmap.

in Java, this SO thread is perfect

Linked List:

  • allow sequential access -> will transverse from either front / back, which closer
  • get by Index is O(n)
  • add @front is O(1)
  • remove is O(n)
  • Iterator.remove is O(1)
  • Spent more memory for pointers=>higher for 64bit. refer to the chart
  • not synchronized

ArrayList:

  • allow index access
  • get is O(1)
  • add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
  • remove is O(n)
  • default size is 10
  • consume memory for capacity not actual storage
  • not synchronized

CopyOnWrite-ArrayList

  • get –> O(1)
  • add –> O(n)
  • contains –> O(n)
  • next –> O(1)
  • remove –> O(n)
  • iterator.remove –> O(n)

When to use Linked List

Some points against LinkedList in general

  • bad performance in getting middle elements
  • It uses lots of small memory objects, and therefore impacts performance across the process.
  • Lots of small object are bad for cache-locality.

Good Use cases:

  • When the size is unknown
  • with FIFO / LIFO property
  • Some deep dive in the Java API =>possible  as a stack, queue, or double-ended queue (deque).
    while there is also java.util.ArrayDeque for array to implement dequeue
  • Want a more stable behaviour? (To be verified)
    <=a already very large ArrayList expanding with GC may cause issue

 

SideNote:

  • There is also an interesting impl of GapList
  • Vector also implements the List interface and is almost identical to ArrayList.
  • It is also possible to implement Queue with known size using arrayList or ArrayBlockingQueue, with help of circular buffer
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s