0

Does a 2d array make sense as a data structure instead of a linked list? Does it offer any performance benefits? Would it work to implement a hash table that way?

Also it seems like the top results typically use very little memory. How is this accomplished?

1 Answer 1

1

Generally speaking, an array, whether 2d or something else, doesn't make sense for this type of application. An array is useful for handling data of a known size, or maybe, if a maximum size is known.

The issue here is that the data will grow in directions that are difficult to predict. In the case of a set of linked lists, it is difficult to determine the length of the linked lists, so it would be similar to determine the size of the array needed to hold the same data. In the case of a trie, it's even more complex to determine how to apply arrays to the scenario.

The problem is that arrays cannot be increased in size once created in C. You would have to implement a way to create a new array and copy the data each time more space is needed.

Or, a massive amount of memory could be allocated to the array at the start, but this tends to leave a large amount of memory unused but allocated. This may be incredibly inefficient.

With memory that is allocated on demand, only the memory needed is allocated and the problems with increasing the size of an array or allocating more array space goes away.

As you may be thinking by now, it all depends on your priorities. If speed is the only consideration and there's massive memory available to sacrifice, then an array solution might be the best choice. If memory efficiency is the most important goal, then allocating on the fly using malloc/calloc calls is probably the best solution.

It all depends on the performance priorities of the program.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

2
  • The second part of his question remained unanswered. How do the top results in the challenge use so little memory? Anyone have any ideas how to replicate that. I have tried both approaches and both use up quite a bit more memory, especially the trie.
    – booklvr
    Mar 14, 2019 at 7:04
  • Oh, that would be giving away the secrets!!!! :-D
    – Cliff B
    Mar 14, 2019 at 7:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .