---

Data structure: concept vs. implementation

---

• What is a data structure
  • Data structure concept:

    Data structure = an information storage structure that provides a specific set of data access/manipulation operations on the data stored.

    ---

  • Example:

    Stack Information is stored in such a way that access to the information follows a Last In, First Out ordering Provides 2 (or 3) specific data access operations on the data stored: push(): insert a data item into the stack pop(): remove a data item from the stack peek(): examine the data item at the top of the stack

  ---

  ---

  ---

  ---

• Data structure: concept vs. implementation
  • Data structure concept:

    The data structure concept specifies (defines) the behavior of a data structure (The behavior of a data structure is often encapsulated or defined by the set of operations on the data structure)

    ---

  • Data structure implementation:

    The data structure implementation is the realization of the functionalities of the data structure in some programming language

    Fact about implementation of data structures:

    There are multiple ways to implement a (same) data structure Each different implementation will usually have its strengths and often its weaknesses.

    ---

    ---

  • Example:

    The stack data structure can be implemented using: An array          or          An linked list