How, why or when would you use your own data structure instead of Collections Framework?

Question

While most of the top IT companies will ask you (during the interview) to solve a problem applying some data structure, is it good if you define your own class for that data structure?

Like if I know this problem is going to b solved by applying a LinkedList, should I make my own implementation of a LinkedList class or use the one provided by the Java Collections API? I have no prior knowledge of C or C++, since I started with Java in school, so I don't know the inner working of these classes.

Answer 1

In my experience, as far as interviews go, the exact (language specific) implementation doesn't actually matter and many will simply let you write it out in pseudo code. If they do require you to write it in a specific language the interviewer will usually be more than happy to help you out with the specific syntax, but be sure they realize you understand the underlying concepts.

As a general rule, never implement a custom data structure if an existing library does the same thing. This applies while working and in an interview (unless specifically asked to do otherwise of course). Re-creating your own data structure is almost always a terrible idea.

There may times where it tempting for some specific case which requires specialized handling of data. However, this should only be done if there is literally no other way of doing this. It is better to implement that separate functionality as a separate entity (or wrap the existing data structure) if possible . Take advantage of the previous developer who created the data structure and likely ran into a lot of the edge cases and bugs you will end up re-creating if you re-create the data structure.

In short: You should understand the data structure to the point that you are able to implement the data structure if someone asked you to do so, but in a real life environment you shouldn't actually re-create it.

Answer 2

You would roll your own data-structure when:

1. You are learning to code, and need the experience (re)writing a "known" solution.
2. You have a very specialized use-case and have done enough research to determine that a pre-built solution is not available for you. (This is relatively rare because EVERYONE needs data structures, so finding a use-case that someone else hasn't already solved is hard)

Answer 3

I admittedly do this rather frequently, even for the most basic and generic containers, though my domain is rather intense in terms of data structure requirements.

The thing in my case is that while these generalized structures are extremely efficient at what they do in ways where I'd be a fool to try to match them fulfilling the same requirements, their generality usually offers plenty of room for a more efficient solution if you tailor that solution to the specific nuances and requirements of the problem at hand.

General vs. Tailored Solutions

For example, I would be a complete fool to try to beat or even match C++'s std::vector (similar to ArrayList in Java) in terms of its general purpose as a variable-length, random-access sequence which is designed to store anywhere from 0 to a gazillion elements. But I can beat it without breaking a sweat (as should anyone else) in use cases where the common case scenario involves frequently constructing a sequence that has no more than 32 elements, for example, with a straightforward implementation of a generic container that only has a couple of dozen lines of code using a small buffer optimization which avoids using the heap in those common cases.

Similar thing with a general-purpose memory allocator. It'd be very foolish in my opinion to try to beat malloc in C with my own implementation designed to satisfy variable-length allocation requests while juggling all kinds of different concerns, and I'd pit myself against the world's finest who devote so much time and attention to just this one problem if I tried. But if all I need is to allocate N element of the same type (same chunk size) in a single thread, then the problem is exponentially simpler to solve, and I can easily beat malloc if I design a solution just to solve this one very specific type of need.

So I've often found a lot of use for slightly more nuanced, but still somewhat general (enough to find a bit of reuse) solutions like these which are more tailored to the specific problem at hand. And it's not like you can implement a competitive, production-quality path tracer or realtime physics engine using std::hash_map in place of a spatial index, e.g, let alone using a third party implementation, so my domain inevitably calls for rolling your own data structures at times since that's what gives your software the competitive advantage (or lack thereof if we fail) and unique performance characteristics*.

In these areas it's not always about "better" or "worse"; different solutions offer different performance strengths and weaknesses, and some of what makes your solution competitive and stand out isn't always about being outright better at everything but being better at some. For example, some of our competitors have very efficient GPU implementations of standard path tracing (as opposed to BDPT or other techniques) which allows them to process a ridiculous number of rays/sec on beefy GPUs. However, they suffer at times with tricky lighting scenarios and can still take hours to converge to a noise-free image in those cases. Ours is more of a hybrid system and data structure and lacks that brute force power, but can converge on those tricky lighting setups a lot faster which tends to make us popular for architectural visualization, while theirs converges a lot faster than ours with more straightforward lighting.

A Practical Example

Just as a practical example I found many on SO struggling to implement their spatial indexes (quadtrees, octrees, BVHs, grids, spatial hashes, etc) efficiently, and one of the biggest gotchas I always see is the temptation to store a generic container from their standard library with each node. That just ends up becoming too explosive in memory to reach for such a generalized solution in areas like a single node/cell of such a structure.

Their structures often had difficulty pulling off even 30 FPS with just a few thousand agents. Whereas I ended up handling half a million on a single thread at over 100 FPS (over 50 million insertions+removals+search queries into the structure per second with about a third of the time spent drawing the frame, not doing collision queries) with a single-thread solution I whipped up in 2 hours that I deliberately tried not to optimize much (the code was intended to teach other people and be as simple and as straightforward as possible):

And this is not intended as a boast and while I have some experience doing these types of things (along with a very fancy and expensive profiler), the first and biggest key (but a substantial one that anybody seeking similar results can apply) to achieving such a solution is to move away from the idea of storing generalized containers in every single node. We have to sometimes move away from such a generalized mindset to solving the problem and, instead of just reaching into the standard toolbox in some demanding cases like these, start really thinking about how to arrange the data in memory and access it efficiently in ways you can't if you can't represent this data at a finer level of nuance any further than what standard containers provide. And exercising this mindset might still allow some use of a generalized container at the tree level but not at the level of a single node in a spatial index.

Staying Productive

One of the things I learned the hard way is not to generalize these more tailored and nuanced solutions too much (otherwise the amount of hand-rolled code we'd have to write and test can multiply a great deal in exchange for very little). I used to try to generalize them to the extent of offering identical interfaces to the standard library to try to maximize their reusability and familiarity, and while I still try to do that when it doesn't require going out of my way at all, I no longer do that when it does. That just ended up requiring so much time upfront to try to generalize a solution whose performance advantages over what's more generalized came from not being so generalized, only to find all the bells and whistles to meet such standard compliance were hardly, if ever, used. So it was like trying to balance two conflicting requirements at once and also a huge time sink. So these days I don't bother trying to generalize these "tailored" solutions too much; I'll make them conform to standard and familiar interfaces when that's almost effortless. Otherwise I won't and accept that these solutions are somewhat narrower in their applicability.

With that aside, I still lean on the generalized containers built into the language whenever possible (there's a massive benefit to doing that which multiplies for teams since the team members are already familiar with those standard containers), and often implement my first draft implementations using them for new and unfamiliar problems I encounter (though I've built up a bit of a library of solutions for very familiar ones). Only if I start seeing hotspots there in hindsight in profiling sessions and, balancing that out with the need to ship, do I consider reaching for anything else.

Answer 4

You roll your own data structures when the existing ones (provided by the JDK or other libraries) are no good at solving your "particular" problem.

Java is a generic language and as such you will find implementations of the data structures that are suitable for, let's say, 99% or the use cases.

But sometimes you have a "particular" application or use case where you fall into the other 1%. That might be for example some high throughput low latency applications with 64GB, 128GB, 256GB, etc, heap sizes. These involve storing a lot of data in memory, sometimes int and long that are IDs representing different entity relations. If, for example, you need a Map of int or long, you are out of luck. You need to box these to Integer or Long to use the Map in Java. Kevin Cline mentioned this in his answer.

If you have a Map of a few million items stored in memory, every bit counts. Saving a few bits here and there multiplied by a few million entities can save you some good amount of memory. That way instead of using 64GB of heap space you use, say, 48GB. That makes it easier to scale because you need servers with fewer resources (thus cheaper) and if you have enough memory but keep it in check you also get less visits from the nice Garbage Collector who might just decide to "stop the world" for a few seconds in that nice little application of yours. For example, TROVE is an example where data structures were implemented to allow storing primitives in an fast efficient way.

For learning the internals and for answering interview question you should be able to implement various data structures, but as the other answers point out, unless your problem is "particular", you will find solutions that already exist and work for most of the cases.

Answer 5

The Collections Framework structures can only store collections of references to objects. This makes them extremely inefficient in space and time for storing large structures of numeric data since each datum must be "Boxed" into an object.