DEV Community

Discussion on: Six Data Structures To Help You Ace Your Technical Interview

canderson93 profile image
Carl Anderson

A lot of the criticisms of linked lists vs ArrayList are language-specific...

In languages like C and Java, arrays (and the underlying arrays in ArrayLists) have to be created with a fixed size. This memory is allocated in a block. If you need to insert more items than your array has, you have to request a larger block of memory and copy things across. You also have the problem where the array is taking up memory even if it's not actually being used, although with modern tech this is largely irrelevant.

The linked list addresses this problem by allowing you to create a list by storing the items in disparate pieces of memory, and storing references. The memory allocation per item is higher, since you also have to store references, but the list can happily grow to any size and has a constant insertion/deletion cost.

The big tradeoff of Linked Lists is that you lose the ability to randomly access the list. If you want the nth element, you have to traverse the entire chain until you get there. This is actually a perfectly good tradeoff for setups where you need to constantly access the first element of the list, like a queue or stack.

Like all data structures, whether it's correct for you depends heavily on your situation. In languages like JavaScript that have dynamic arrays anyway, it's probably not worth thinking about.

Thread Thread
aminmansuri profile image
hidden_dude • Edited on

But you're forgetting the cache tradeoff.. the cache tradeoff of linked lists vs dynamic arrays (aka. ArrayLists) is considerable.

It can make a very large performance difference if every time you access a new item in the list you have to suffer a cache miss.

Also I don't think these "criticisms" (I prefer comparison) are language specific. Underlying it all is the concept of a fixed block of memory you allocate for an array or for a node. How you do those allocations and what their dispositions in RAM are is very relevant when figuring out the practical performance behaviors.

It may be that Python or Javascript hides this from you by implementing the dynamic array outright, however, its the very selection of the data structures used in these languages that will dictate their performance characteristics.

I'm using Java as an example. But the underlying notions of how you create lists are the same.