[Data Structure] Understanding ADT(Abstract Data Types)

What Are Data Structures?

A data structure is a way of organizing and storing data so we can work with it efficiently. Different types of data require different organizational strategies—think of how a dictionary organizes words alphabetically for quick lookup, or how a map uses geometric layouts to represent locations and routes.

When we study data structures, we typically approach them from two angles:

1. Abstract Data Types (ADTs): The mathematical and logical perspective
2. Implementation: How we actually build them in code

Abstract Data Types (ADTs)

An ADT defines what operations a data structure can perform without specifying how those operations work under the hood. It’s like knowing you can turn a TV on and off, change channels, and adjust volume—without needing to understand the internal circuitry.

ADT vs. Data Structure

Let’s clarify the distinction with an example:

List ADT (the “what”):

• Store elements in sequential order
• Insert elements at any position
• Remove elements from any position
• Access and modify elements by position
• Track the number of stored elements

This is abstract—we’re describing capabilities, not implementations.

List Implementation (the “how”):

• Array-based list
• Linked list
• Dynamic array
• And more…

These are concrete implementations of the same ADT concept.

Note: In C, there’s no built-in stack implementation. You have to build one yourself using arrays or linked lists—that’s the implementation part.

Practical Example: Implementing a List with Arrays

Let’s see what happens when we implement the List ADT using an array:

Initial state:
[2][4][3][7][ ][ ][ ]  end=3

Insert 5 at position 2:
[2][4][ ][3][7][ ][ ]  ← shift elements right
[2][4][5][3][7][ ][ ]  ← insert 5, end=4

Time Complexity Analysis

• Insertion: $O(N)$ in the worst case (when inserting at the beginning)
  • We have to shift all subsequent elements
• Access/Modification: $O(1)$
  • Direct indexing makes this fast
• Handling Full Arrays:
  • Create a new, larger array (typically double the size)
  • Copy all elements to the new array
  • This is expensive and wastes memory if we overestimate capacity

The Problem

Array-based lists have limitations:

• Costly insertions and deletions
• Inefficient memory usage
• Fixed maximum capacity (or expensive resizing)

This is where linked lists come in, offering a different set of trade-offs that we’ll explore in future posts.

Why This Matters

When solving problems, your first question should be: Which ADT fits this problem? Only after choosing the right abstraction should you worry about implementation details. This separation of concerns makes code more flexible and easier to reason about.

Think of ADTs as contracts—they guarantee certain operations will be available, regardless of how they’re implemented behind the scenes.