CODEWITHSUNDEEP
java
BlahBlah
BlahBlah

Reputation: 275

which is better for implementing median of medians algorithm - ArrayList or Linkedlist?

I am trying to implement the median of medians algorithm in Java. I was wondering which of these two list implementations would cost less in terms of list traversal and comparison? Thanks!

Upvotes: 0

Views: 229

Answers (1)

dcernahoschi
dcernahoschi

Reputation: 15250

An ArrayList should be slightly more efficient because the algorithm needs some random access to the data structure that takes O(1) for the ArrayList and O(n) for the LinkedList.

LinkedList is more efficient for remove operations (O(1) for LinkedList and O(n) for ArrayList), but this should not be the case in your algorithm.

Upvotes: 1

Related Questions