Data Structures Fundamentals
Data structures are specialized formats for organizing and accessing data efficiently. Arrays, linked lists, trees, hash tables, graphs, and heaps each trade off between operation speeds, memory use, and complexity, and choosing the right one determines an algorithm's performance.
itComputer fundamentals | OpenSkills.info
Intro
Data Structures Fundamentals
A data structure organizes information so a program can use it efficiently. The structure does not solve a problem by itself. It gives an algorithm a way to store, find, add, remove, and traverse data.
This course gives you a practical map of the main structures. You will learn the difference between an interface and an implementation. You will also learn to choose a structure from the operations your workload needs.
Start with the interface
An abstract data type, or ADT, specifies values and operations without fixing an implementation. A stack ADT promises operations such as push and pop. It does not require an array or a linked list.
That separation matters. The interface states what your code needs. The data structure states how those operations work in memory. Two implementations can provide the same interface with different time and space costs.
Use this sequence when you choose a structure:
- Name the data and the operations.
- Identify which operations dominate the workload.
- Decide whether order, duplicate values, or key lookup matters.
- Compare time, memory, and implementation costs.
- Check the worst case and any assumptions behind an average-case claim.
Continue the course
This section is part of the paid course.
See pricing to subscribe, or log in if you already have access.
Where this skill leads
Relevant careers
See how this topic contributes to broader role-level skill maps.
Sources
- https://xlinux.nist.gov/dads/terms.html
Supports
- NIST DADS defines algorithms, data structures, abstract data types, operations, and complexity terms
- Its indexes and cross-references connect related concepts
- https://xlinux.nist.gov/dads/HTML/dataStructure.html
Supports
- A data structure organizes information to support algorithm efficiency or conceptual unity
- Data structures have associated operations such as search, insertion, and balancing
- https://xlinux.nist.gov/dads/HTML/abstractDataType.html
Supports
- An abstract data type specifies values and operations independently of an implementation
- Stacks, queues, dictionaries, sets, and priority queues are abstract data types
- https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/79a07dc1cb47d76dae2ffedc701e3d2b_MIT6_006S20_lec2.pdf
Supports
- An interface specifies supported operations while a data structure represents how to support them
- Sequence and set interfaces have distinct operation families
- Dynamic-array append is amortized constant time and growth can require copying items
- Static arrays provide constant-time indexed access while insertion and deletion can be linear
- Linked lists provide constant-time changes at known ends while indexed access is linear
- https://xlinux.nist.gov/dads/HTML/array.html
Supports
- Array items are directly accessible through integer indexes
- Middle insertion can take linear time
- https://xlinux.nist.gov/dads/HTML/linkedList.html
Supports
- A linked list stores each item with a link to the next item
- Ordinary linked-list search is linear
- Linked lists can implement stacks and queues
- https://xlinux.nist.gov/dads/HTML/stack.html
Supports
- A stack removes the most recently added item first
- Push, pop, top, and empty checks are core stack operations
- https://xlinux.nist.gov/dads/HTML/queue.html
Supports
- A queue removes the earliest added item first
- Enqueue adds at the tail and dequeue removes from the head
- https://xlinux.nist.gov/dads/HTML/dictionary.html
Supports
- A dictionary maps keys to values through insert, find, and delete operations
- Hash tables and search trees are dictionary implementations
- https://xlinux.nist.gov/dads/HTML/hashtab.html
Supports
- A hash table maps dictionary keys to array positions with a hash function
- Collisions occur when keys map to the same position
- Chaining and open addressing are collision-resolution families
- https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/ce9e94705b914598ce78a00a70a1f734_MIT6_006S20_lec4.pdf
Supports
- Hashing maps keys into a smaller table and therefore permits collisions
- Chaining stores colliding items in another structure
- Hash tables can provide expected amortized constant-time dynamic set operations under stated assumptions
- Sorted arrays and ordered structures support order operations that hash tables do not make efficient
- https://xlinux.nist.gov/dads/HTML/tree.html
Supports
- A tree is accessed from a root and contains internal nodes, children, leaves, and subtrees
- Trees can represent rooted hierarchical relationships
- https://xlinux.nist.gov/dads/HTML/binarySearchTree.html
Supports
- A binary search tree keeps smaller keys in left subtrees and larger keys in right subtrees
- AVL trees are balanced binary-search-tree variants
- https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes/
Supports
- Binary-search-tree operations depend on height
- A tree can degenerate to linear height
- AVL balancing keeps height logarithmic and supports logarithmic key operations
- The course sequence includes heaps, graph traversal, and shortest paths after trees
- https://xlinux.nist.gov/dads/HTML/heap.html
Supports
- A heap is a complete tree with a parent-child key-order property
- Heaps are used to implement priority queues
- Heap memory and general allocation memory are different meanings of the word heap
- https://xlinux.nist.gov/dads/HTML/binaryheap.html
Supports
- A binary heap can be implemented in an array with computed parent and child indexes
- Binary-heap insertion is logarithmic
- https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/40d4851e550507ca14dc778b9b2266cc_MIT6_006S20_lec8.pdf
Supports
- A complete binary tree can use an implicit array representation
- A priority queue can inspect its extreme item in constant time and insert or remove it in logarithmic time
- Arbitrary search in a binary heap can be linear
- https://xlinux.nist.gov/dads/HTML/adjacencyListRep.html
Supports
- An adjacency list stores an array of neighbor lists
- Adjacency lists are compact for sparse graphs
- https://xlinux.nist.gov/dads/HTML/adjacencyMatrixRep.html
Supports
- An adjacency matrix represents graph edges in a matrix indexed by vertex pairs
- A matrix supports direct access to the entry for a vertex pair
- https://opendsa.cs.vt.edu/OpenDSA/Books/Catalog/html/index.html
Supports
- OpenDSA provides instructional material on lists, stacks, queues, hashing, trees, heaps, graphs, and algorithm analysis
- Its materials include explanations, visualizations, and exercises
- https://opendsa.cs.vt.edu/ODSA/Books/CS3/html/genindex.html
Supports
- The index links definitions and instructional sections for core and advanced data-structure topics
- https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
Supports
- MIT 6.006 covers common algorithms, data structures, performance measures, and analysis
- The course provides lecture notes, videos, problems, quizzes, and solutions
- https://algs4.cs.princeton.edu/home/
Supports
- The booksite covers fundamentals, searching, graphs, strings, and applications
- It provides implementations, excerpts, exercises, visualizations, and programming assignments