Data Structure Classification🧑‍🔧

Data structures are fundamental building blocks of any program. Understanding and applying them properly is important to understand how data structures can be classified. There are two main ways to categorize data structures - logical structure and physical structure.

Logical Structure ✅

Logical structure refers to how data elements relate to each other logically. This relationship can be linear or non-linear:

• Linear structures arrange data sequentially, like arrays and linked lists. Elements have a direct "before and after" relationship.
• Non-linear structures don't arrange data linearly. Trees represent hierarchical relationships, while graphs represent complex networks between elements.

Common linear structures include arrays, linked lists, stacks, hash tables, and queues. Non-linear structures include trees, heaps, hash tables, and graphs.

Physical Structure ✅

Physical structure refers to how data is stored in computer memory. There are two types:

• Contiguous Memory Allocation stores related data at contiguous memory locations, like arrays. This allows for efficient random access.

• Non-Contiguous Memory Allocation stores data anywhere in memory using pointers, like linked lists. This is more flexible for dynamic data.

Image source

All data structures are ultimately built upon arrays and/or linked lists at the physical level. For example, trees can be implemented via arrays or linked lists.

Implementation

All data structures are implemented based on arrays, linked lists, or a combination of the two

Common data structures tend to be implemented based on their logical properties and the application's specific needs. For example, stacks and queues can be implemented using arrays or linked lists and a hash table implementation may include both arrays and linked lists.

• Based on arrays: stack, queue, hash table, tree, heap, graph, matrix, tensor (dimension >= 3 arrays) etc.
• Based on linked lists: stack, queue, hash table, tree, heap, graph, etc.

In summary, understanding how data structures can be categorized logically and physically provides important context for selecting the right structure for different problems and implementations. While common data structures tend to map to certain classifications, the ultimate choice depends on balancing the relevant tradeoffs 👓.