CODEWITHSUNDEEP
javaarrayslistarraylistdata-structures
Minimax
Minimax

Reputation: 131

Best way to go about removing middle element from list or arraylist in java?

I need sequentially remove the middle element from sorted data. What would be the best way to do that? Since LinkedList operation takes n/2 time to remove the element, an arraylist would be faster. But an arraylist on the other hand then takes time to shift all the elements to the left, which isn't efficient either. Would other datastructures be of use maybe?

Upvotes: 0

Views: 1251

Answers (2)

Shanu Gupta
Shanu Gupta

Reputation: 3807

Removing the middle element is composed of two parts:

  1. Finding the middle element
  2. Deleting that element

ArrayList is O(1) at random access, so 1st step is fast for Array. While LinkedList is O(1) at deletion (given node), so 2nd step is easy for List.

What you want is best of both worlds.

IMO this is easily achievable if you write a custom (or extend existing) LinkedList. You'll need to have extra middle reference variable which will :

  • move to next upon insertion if the size becomes odd.
  • move to prev upon deletion if the size becomes odd.

You can also do even in both cases but they must be same (either even or odd).

Upvotes: 2

meriton
meriton

Reputation: 70564

Might a TreeSet fit the bill? If offers removal in O(log n) by key.

Upvotes: 0

Related Questions