A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
An Abstract Data Type (ADT) specifies what operations are supported and their expected behavior, but not how they are implemented. A List ADT defines access, insertion, deletion, and traversal without prescribing array or linked-list implementation.
Define a List interface with operations (get, insert, remove, size), then implement it twice—once with arrays and once with linked lists—and compare performance on a suite of use cases.
You already know how arrays work at a concrete level — indexed slots in contiguous memory where you can read or write any position in O(1) time. An Abstract Data Type takes a step back from that concrete machinery and asks: what operations does a user of this data structure actually need, and what promises should those operations make? The List ADT answers that question for ordered, sequential collections. It specifies operations like `get(index)`, `insert(index, element)`, `remove(index)`, and `size()`, along with their expected behavior — but it says nothing about whether the data lives in a contiguous block of memory or in scattered nodes connected by pointers.
This separation between interface (what you can do) and implementation (how it works underneath) is one of the most powerful ideas in computer science. Think of it like a vending machine: the interface is the buttons and the dispensing slot. You don't need to know whether the machine uses a conveyor belt, a robotic arm, or a spring-loaded shelf — you just press B4 and expect your item. The List ADT is the button panel; arrays and linked lists are two different internal mechanisms.
Why does this matter in practice? Because different implementations make different tradeoffs. An array-backed list gives you O(1) random access by index — jump straight to position 47 — but inserting at the front requires shifting every element over, costing O(n). A linked-list-backed list flips this: inserting at the front is O(1) since you just redirect a pointer, but reaching position 47 means walking through 47 nodes one at a time. The ADT lets you write code that depends only on the interface, so you can swap implementations later without rewriting your logic. If your program mostly reads by index, use an array-backed list. If it mostly inserts and removes from the ends, a linked-list backing may be faster.
The discipline of thinking in ADTs also prevents a subtle mistake: assuming that because two implementations support the same operations, they perform the same way. They don't. The same `insert(0, x)` call is O(1) in one implementation and O(n) in another. Choosing an implementation without understanding these differences is like choosing a vehicle without asking whether you need to haul cargo or race on a track. The ADT tells you what the vehicle can do; the implementation determines how well it does each thing.