4

I've been wondering for a while why an ArrayList does not have a stack-like interface (think push() and pop())

I frequently find myself using these constructs in Java:

  • list.get(list.size() - 1);
  • list.remove(list.size() -1);

While I rather do something like:

  • list.peek();
  • list.pop();

I know the legacy class Stack exists, which clashes with a potential interface called Stack, but that wouldn't stop them from making a stack-like interface with a different name.

A Deque also exists, but it can not be (efficiently) backed by an array-like collection for obvious reasons. One downside is that it's implementations are often linked-list-like and therefore don't support random access. There are situations where random-access in a stack is desired, like in Reverse Polish notation calculations or in emulators (implementing an actual call stack)

I also know that the ArrayDeque class exists, which is almost a copy of ArrayList (why?) and explicitly warns about inefficient deque-operations that operate on the first element or elements in the middle. It's also yet another class to learn, possibly with it's own quirks that differ from ArrayList. Why was this route chosen instead of adding the Deque interface to ArrayList? (Is it to prevent inexperienced programmers from making unobvious (performance-related) mistakes?)

Improve this question
8
  • 1
    what you look for is a Deque - a proper replacement for legacy Stack, with push and pop. This was quite thoroughly discussed at Stack Overflow over 10 years ago Commented Sep 27, 2024 at 11:10
  • 3
    @gnat: I think the OP is not looking for a Deque. They are looking for an ArrayList which they can use like a Stack in a certain context, and like an ArrayList in another context. Commented Sep 27, 2024 at 11:51
  • 1
    @DocBrown in JCF, Deque interface is exactly the thing they need for what you describe because one of its implementations has just that (ArrayDeque, it was also mentioned in that old SO discussion) Commented Sep 27, 2024 at 12:09
  • 1
    @gnat: the OPs question, as I understand it, was not "is there a different class in JCF which fits better to my needs", but "why did the JCF designers not add peek and pop to an ArrayList (since both are common and efficient operations)?". Of course, that's almost unanswerable for us and should probably be closed as "too opinionated". Commented Sep 27, 2024 at 12:17
  • 1
    Duplicate of In Java, why is there no instance method like bigDecimal.isGreaterThan(otherBigDecimal)? Commented Sep 27, 2024 at 12:51

4 Answers 4

Reset to default
5

We can only guess why the JCF looks today like it does, but one lesson learned in design is what Antoine de Saint-Exupery once said:

A designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away.

In my experience, this applies to software design as well. A component like an ArrayList does not become necessarily "better" by supporting as many different data type interfaces as possible (even if it could). The smaller the interface of a component is, the less do we we have to learn and remember how it looks like, and the less functions are there which we confuse for each other. (Of course, an interface should not be smaller than it needs to be to form a coherent abstraction.)

How "small" an interface of a container should be ideally is definitely a question of the designers experience, taste and what they have learned at school or university. The usual CS books about stacks, lists, vectors, queues and arrays treat them as distinct abstract data types, so following that tradition and implementing them as different classes seemed to be quite natural.

Hence, for some reason we do not know for sure, the JCF designers seemed to have thought peek and pop are negligible for ArrayList. But when you think peek and pop would be a great addition to your ArrayLists, feel free to implement your own component ExtArrayList which provides the whole ArrayList together with peek and pop.

Improve this answer
5
  • 1
    Any interface should be as small as possible. Designer experience. Commented Sep 27, 2024 at 12:57
  • Interesting. This starts to look like not only the old Vector/StringBuffer/etc are designed sub-optimally, but ArrayList is also designed sub-optimally. I can imagine a compatibility-breaking 'improvement' where ArrayList is stripped to the bare essentials, and it can be 'transformed' by wrappers that implement the desired interface: Queue q = list.asQueue(); just like they can be 'transformed' to iterators. I think this answer comes closest to the real reason. Commented Sep 27, 2024 at 14:19
  • @MarkJeronimus asQueue() does not shrink the LinkedList interface, because a logical interface of a class includes interfaces of all of its return values. You have to use explicit wrappers: new QueueAdapter(list) Commented Sep 27, 2024 at 15:25
  • The way I described asQueue(), it will return a new object of type Queue (not necessarily QueueAdapter as it can be an anonymous class`), wrapping the collection. Commented Sep 30, 2024 at 8:46
  • @MarkJeronimus it does not matter. As long as there is a Queue in an interface, that interface include its complexity. Do not do that. Commented Oct 1, 2024 at 6:18
5

Have you seen this?

enter image description here

Stack Overflow - Rule of thumb for choosing an implementation of a Java Collection?

So tell me, how did you land on ArrayList if you wanted to treat it like a LIFO or a queue?

I know ArrayList is popular. If you got stuck with it somehow and don't really have a choice of implementation don't feel bad about wrapping it up in something that lets its client treat it like a stack. It might not be the most performant choice but good enough is good enough.

But don't act like every possible interface that could have been backed by ArrayList should be native to ArrayList. That list of interfaces has no end. They focused on what they made it for and hoped the kitchen sink could be added later.

Also how would anyone know which end list.pop() would pop from? What makes stack so special? Sorry but if I can see the ArrayList behind the stack then your abstraction is leaking.

Improve this answer
1
  • That's a thick thumb 🤷‍♂️. ArrayList does not differ from Deque for the stack operations. And it has defined end for those (only one has amortized complexity to work on). Commented Sep 30, 2024 at 5:42
1

API is easy to extend, but is very hard to shrink (shrinking breaks backward compatibility and requires a labor intensive deprecation protocol). Therefore adding any methods (and implementing new interfaces) to an API requires careful consideration and should be done as late as reasonable.

As Java is praised for backward compatibility, it can't easily afford to add new APIs. And when it is actually considered, redundant methods like push(o) instead of addLast(o) have lowest priority. Implementing something that was not possible to do before is more important than a convenience function.

Improve this answer
-2

Why doesn't Java implement things that way? One likely reason given early Java's almost-pedantic approach to object-oriented implementations is that lists and stacks are distinct and different data types, with different usages.

A list is a

collection of items that are finite in number and in a particular order. An instance of a list is a computer representation of the mathematical concept of a tuple or finite sequence.

Whereas a stack

is an abstract data type that serves as a collection of elements with two main operations:

  • Push, which adds an element to the collection, and
  • Pop, which removes the most recently added element.

Lists and stacks are different tools that are used to do different things. An "ordered collection" is not "a collection of elements with two operations". Lists are state-based, effectively static sets, and stacks are event-driven dynamic "holding tanks" that return the last object inserted.

One's a screwdriver, one's a hammer. Sure, you can grab a hammer and use it to drive in a wood screw. It might even work. But it's not an efficient use of the tool, and abuses the screw to the point it might fail. And good luck using a screwdriver to drive in a nail.

Likewise with lists and stacks. You can force a list to be a stack by adding to the end as a "push" operation, and removing the last element as a "pop" operation, but it's very likely to be a lot less efficient than a purpose-build stack implementation. And performance can be a critical requirement in the use of any tool. Whereas stacks have no concept of order outside of "this is the last one in", so they can't be forced into any type of "a particular order".

Improve this answer
7
  • I think that in the context of OP question (about JCF) there is no need to force list be a stack because they need to simply use Deque class Commented Sep 27, 2024 at 11:11
  • @gnat We're in agreement, then. ;-) OP asked "Why is ArrayList not a Stack", and that's what I tried to answer without a glib "Because a cat is not a horse" answer. IMO the fact there's an alternative implementation isn't fundamental to the "Why?", it's additional evidence that different tools have different uses, which is why I didn't mention Deque. Commented Sep 27, 2024 at 11:29
  • 2
    The screwdriver/hammer is an unsuitable comparison. An ArrayList is more like a swiss army knife, which contains a screwdriver function, and the OP asks why the integrated screwdriver ("Stack") functionality is a little bit awkward to use, though there could be an easy fix. Moreover, peek and pop operations on an ArrayList are exactly not very likely to be a lot less efficient than for a on-purpose Stack. Commented Sep 27, 2024 at 11:56
  • Like I said in the OP, there are cases where the overlap between list and stack is preferred for clean code. The examples I gave both need to peek 'deeper' into the stack without popping everything. Furthermore, any Stack (except PriorityStacks) has a fixed order: the iteration order. Commented Sep 27, 2024 at 12:08
  • @DocBrown The question is "Why doesn't Java implement it this way?" Saying "They could have done it" or "This one Java implementation isn't likely to be less efficient" aren't answers as to why it wasn't done. The fact that lists and stacks are distinct abstract data structures is an answer. I've added that explicitly. Commented Sep 27, 2024 at 12:35

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.