Back to Study Material Data Structures and Algorithms

Types of Data Structures

Data structures can be classified along several axes: physical versus logical organization, linear versus non-linear layout, static versus dynamic sizing, ...

Types of Data Structures

Classifying Data Structures by Shape and Behavior

Data structures can be classified along several axes: physical versus logical organization, linear versus non-linear layout, static versus dynamic sizing, and homogeneous versus heterogeneous content. Understanding these axes helps you choose the right tool for any given problem.

Physical organization refers to how data sits in memory. Contiguous structures, such as arrays, store all elements in adjacent memory locations. This layout benefits from cache locality: when the CPU loads one element, neighboring elements are pulled into the cache simultaneously, making sequential access very fast. Linked structures, such as linked lists and trees, scatter nodes across memory connected by pointers. Each pointer dereference may cause a cache miss, which can slow traversal significantly on large datasets.

Linear data structures arrange elements in a sequential order where each item has a unique predecessor and successor (except the first and last). Arrays, linked lists, stacks, and queues are all linear. You can traverse all elements by following a single path from beginning to end.

Non-linear data structures allow one element to connect to many others. Trees have a hierarchical parent-child relationship, while graphs allow arbitrary connections including cycles. Non-linear structures model more complex relationships but require more sophisticated traversal strategies like depth-first search and breadth-first search.

Static data structures have a fixed size determined at creation time. A classic array in C is static: once declared with a size, that size cannot change without allocating new memory and copying elements. Dynamic data structures grow and shrink as needed. Dynamic arrays, such as Java's ArrayList or Python's list, automatically resize by allocating a larger block and copying elements when capacity is exceeded, typically doubling in size each time to amortize the cost to O(1) per append on average.

Homogeneous structures hold elements of the same type, such as an integer array. Heterogeneous structures hold mixed types; tuples and structs are examples. Most classical data structures are homogeneous, though many languages support generic or dynamic typing that relaxes this constraint.

Worked example: a stack implemented as a fixed-size array is static, fast, and cache-friendly but will overflow if too many elements are pushed. A stack implemented as a linked list is dynamic and never overflows but has slightly higher memory overhead per element due to pointer storage.

Interview tip: when asked to implement a data structure, clarify whether the size is bounded. If unbounded, prefer a dynamic implementation and discuss the resizing strategy.