Skip to main content
Engineering LibreTexts

11: Tradeoffs

  • Page ID
    46709
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

    ( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\id}{\mathrm{id}}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\kernel}{\mathrm{null}\,}\)

    \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\)

    \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\)

    \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    It is important to fully understand the problem you need to solve before choosing a data structure because each structure is optimized for a particular job. Hash tables, for example, favor fast lookup times over memory usage while arrays are compact and inflexible. Other structures, such as stacks, are optimized to enforce rigid rules on how data is added, removed and accessed throughout the program execution. A good understanding of data structures is fundamental because it gives us the tools for thinking about a program's behavior in a structured way.

    Sequences (aka lists):

    Array Dynamic Array Array Deque Singly Linked List Double Linked List
    Push (Front) - O(n) O(1) O(1) O(1)
    Pop (Front) - O(n) O(1) O(1) O(1)
    Push (Back) - O(1) O(1) O(n), maybe O(1)* O(1)
    Pop (Back) - O(1) O(1) O(n) O(1)
    Insert before (given iterator) - O(n) O(n) O(n) O(1)
    Delete (given iterator) O(n) O(n) O(n) O(1)
    Insert after (given iterator) O(n) O(n) O(1) O(1)
    Delete after (given iterator) - O(n) O(n) O(1) O(1)
    Get nth element (random access) O(1) O(1) O(1) O(n) O(n)
    Good for implementing stacks no yes (back is top) yes yes (front is top) yes
    Good for implementing queues no no yes maybe* yes
    C++ STL std::array std::vector std::deque std::forward_list std::list
    Java Collections java.util.Array java.util.ArrayList java.util.ArrayDeque - java.util.LinkedList
    * singly-linked lists can push to the back in O(1) with the modification that you keep a pointer to the last node
    

    Associative containers (sets, associative arrays):

    Sorted Array Sorted Linked List Self-balancing Binary Search Tree Hash Table
    Find key O(log n) O(n) O(log n) O(1) average O(n) worst
    Insert element O(n) O(n) O(log n) O(1) average O(n) worst
    Erase key O(n) O(n) O(log n) O(1) average O(n) worst
    Erase element (given iterator) O(n) O(1) O(1) O(1)
    Can traverse in sorted order? yes yes yes no
    Needs comparison function comparison function comparison function hash function
    C++ STL - - std::set

    std::map
    std::multiset
    std::multimap

    std::unordered_set

    std::unordered_map
    std::unordered_multiset
    std::unordered_multimap

    Java Collections - - java.util.TreeSet

    java.util.TreeMap

    java.util.HashSet

    java.util.HashMap

    Various Types of Trees

    Binary Search AVL Tree Binary Heap (min) Binomial Queue (min)
    Insert element O(log n) O(log n) O(log n) O(1) (on average)
    Erase element O(log n) O(log n) unavailable unavailable
    Delete min element O(log n) O(log n) O(log n) O(log n)
    Find min element O(log n) O(log n) O(1) O(log n) (can be O(1) if ptr to smallest)
    Increase key unavailable unavailable O(log n) O(log n)
    Decrease key unavailable unavailable O(log n) O(log n)
    Find O(log n) O(log n) unavailable unavailable
    Delete element O(log n) O(log n) unavailable unavailable
    Create O(1) O(1) O(1) O(1)
    find kth smallest O(log n) O(log n) O((k-1)*log n) O(k*log n)

    Hash table:

    Hash table (hash map)
    Set Value Ω(1), O(n)
    Get Value Ω(1), O(n)
    Remove Ω(1), O(n)

    This page titled 11: Tradeoffs is shared under a CC BY-SA license and was authored, remixed, and/or curated by Wikibooks - Data Structures (Wikipedia) .

    • Was this article helpful?