0

I want to create a list of bytes. (In Java) The size is known. After every iteration, I'd like to remove the first element. And at any point in time, I will only be accessing the first element.

I thought about using a queue but that will not work in my use case as I need to keep the item in the list for multiple iterations.

What will be best suited keeping the performance in mind.

Array list of LinkedList? (Order is important) Since size is not changing, how about using array and accessing i-th element? Without removing the first everytime?

Femn Dharamshi
  • 527
  • 1
  • 9
  • 25
  • Are you ever adding more bytes? Where? – Louis Wasserman Nov 10 '21 at 17:48
  • And just saying: does "first" mean ... the end you aren't "appending"? And how do you "remove" an element from a list when its size is "not changing"? Sometimes a bit of (pseudo) code is much better to describe requirements than vague explanations, you know? – GhostCat Nov 10 '21 at 19:14

2 Answers2

2

For removal of first element an arrayList will be slower as it uses arrays to store data while a linkedList would be much faster O(1)

Refer blogs like; https://www.baeldung.com/java-remove-first-element-from-list#:~:text=ArrayList's%20remove()%20method,elements%20need%20to%20be%20shifted.

For removal of 1st element order does not matter anyway. So keeping performance in mind, LinkedList is the way to go for you.

For accessing a random i'th element however, an ArrayList is much faster O(1) than LinkedList O(n)

Refer the answer to question for more details to this or any further questions regarding LinkedList vs ArrayList: When to use LinkedList over ArrayList in Java?

Shivam Puri
  • 1,578
  • 12
  • 25
  • Okay great answer. I've heard the LinkedList takes a lot of overhead memory to store things. Will this be affecting the performance? – Femn Dharamshi Nov 10 '21 at 18:12
  • Space complexity and time/performance complexity are 2 different topics. Your question was about time complexity and performance and was answered accordingly I hope!! :) – Shivam Puri Nov 10 '21 at 18:34
0

I am not sure if you want to implement this by yourself. If that's not the case, check Java Byte Class which is a byte primitive wrapper.

Regarding accessing the first element, there are multiples approaches, some of them are:

  1. Just simply iterating over the list with an index and then moving it to the last element and starting over again when the last element is reached.

  2. Poping the elements and adding them into another queue. When the last element is deleted you just simply change the queues and start over.

Martin Capparelli
  • 21
  • 2