Types of Data Structures
Learn about the different types of data structures including primitive and composite, linear and nonlinear, hash-based, static, and dynamic structures. Understand how these structures organize data and impact program efficiency to build a strong foundation for applying them in Go programming.
We'll cover the following...
Primitive vs. composite structures
All data structures in computer science belong to one of two families. Primitive structures are the basic types built directly into the programming language: integers, floats, runes or bytes for characters, and booleans. Composite structures are built on top of those primitives to organize multiple values into something with shape and access rules.
This course focuses entirely on composite structures. These are the ones you design, choose between, implement, and reason about as an engineer.
Linear vs. nonlinear
Composite structures are further divided by how their elements relate to each other.
Linear: Elements arranged in a sequence
In a linear structure, each element has at most one predecessor and one successor. You can traverse the whole structure in a single pass from start to finish. These map naturally to sequential memory.
Nonlinear: Elements arranged hierarchically or as a network
In a nonlinear structure, elements can have multiple predecessors or successors. You cannot traverse the whole thing in one sequential pass. These structures model real-world relationships like hierarchies, priorities, and networks.
Hash-based: Key-value access via hash functions
Hash-based structures use a hash function to map keys to storage locations, providing near-constant-time access on average, regardless of how many elements are stored.
How they compare at a glance
Here’s a high-level comparison across the major structures. Do not worry about memorizing it now. Treat this as a reference you will return to as each structure gets its own chapter.
Structure | Access | Insert | Delete | Search | Best For |
Array | O(1) | O(n) | O(n) | O(n) | Index-based access |
Linked List | O(n) | O(1) | O(n) | O(n) | Frequent insert and delete |
Stack | O(1)* | O(1) | O(1) | O(n) | LIFO processing |
Queue | O(1)* | O(1) | O(1) | O(n) | FIFO scheduling |
Hash Table | O(1)† | O(1)† | O(1)† | O(1)† | Fast key-value lookup |
BST | O(log n) | O(log n) | O(log n) | O(log n) | Sorted data, range queries |
Heap | O(1)* | O(log n) | O(log n) | O(n) | Priority queues |
Graph | varies | O(1) | O(V+E) | O(V+E) | Relationships, paths |
Note:
*Top or front element only.†Average case; worst case O(n) due to hash collisions.
Static vs. dynamic structures
Structures are also split by whether their size is fixed at creation or can grow and shrink at runtime.
Static structures like fixed-size Go arrays have their size set at creation. They are memory-efficient but require you to know the maximum size upfront.
Dynamic structures like linked lists and Go slices grow and shrink as needed. They offer flexibility, at the cost of slightly more memory overhead per element.
Go's built-in slice is a dynamic view over an underlying array. It behaves like a flexible array and can automatically increase its capacity when appended to beyond its current limit. This abstraction hides the underlying resizing strategy and associated trade-offs.