re: thank u, next: an introduction to linked lists VIEW POST

TOP OF THREAD FULL DISCUSSION
re: That's a good introduction to linked lists. Still I believe that linked lists are one of the most overrated data structures and that in practice t...
 

One thing that people forget so often is that "linked list" as data structure doesn't have to mean the exact in-memory representation. When you use a LinkedList class, you don't care for its implementation details: it could actually be storing elements sequentially like a traditional array, but exposing only the methods so you see it like a linked list.

When talking about data structures, it's all about the public interface.

 

When you use a LinkedList class, you don't care for its implementation details

But linked list is the name of a specific implementation of a list. When a class is named LinkedList, I expect it to be implemented this way.

If you don't care about the implementation, it would be better to declare and use an interface named List that is implemented by classes named LinkedList or ArrayList.

Indeed, I should've used the term Abstract Data Type (ADT), not data structure.

Still, I don't think that LinkedList refers to the way it's implemented. For example, it's not uncommon for a tree to be implemented as two arrays: one to hold the index of the parent and the other to store the actual data. Such data structure could still expose all public methods as a tree, and you wouldn't have to know how it's implemented.

code of conduct - report abuse