ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Data structures logical and physical

?Download as PPTX, PDF?
?
Sandeep Kunkunuru
Sandeep Kunkunuru

This document discusses logical and physical data structures. Logical data structures are defined by their APIs and semantics rather than a specific implementation. Common logical structures include stacks, queues, priority queues, bags, and symbol tables. Physical structures are based on machine organization and include arrays and graphs as the most generic types. Graphs can then be specialized further as linked lists, trees like binary search trees, and different types of graphs.

1 of 7
Logical and Physical Data Structures - A way of understanding data structures - References: 1. Algorithms - Princeton - Coursera 2. Algorithms Booksite
Logical Data structures - definition A logical data structure is defined by its API and the semantics of each of the APIs. It does not either imply the physical implementation of the data structure nor necessitate a specific implementation. While several implementations exist for each logical data structure some are optimal vis-a-vis others.
Logical Some of the logical data structures include ¡ñ Stacks ¡ñ Queues o Priority Queues ¡ñ Bags ¡ñ Symbol Tables
Logical - Illustrative API - Symbol Table
Physical - Generic Physical data structures are constructed based on the organization of the computing machine. The memory structures both scale and hierarchy, instruction set both operations and registers drive the physical design of a data structure. There are two physical implementations of data structures at the most generic abstraction level for a computing machine (a deterministic turing machine as opposed to a quantum). ¡ñ Arrays ¡ñ Graphs
Physical - Specialized The two generic physical data structures can be further specialized as follows ¡ñ Array o unordered array o ordered array ¡ñ Graph o Linked Lists o Trees ? Binary Trees ¡ñ Binary Search Trees o Self Balancing Binary Search Trees ? Left Leaning Red Black Tree ? ¡­. o Acyclic Graphs ? Directed Acyclic Graphs ? ¡­. o Cyclic Graphs ? ... o And all other variants ? 2-3 Trees ? B-Trees ? Tries
Physical - Illustrative Implementations - Symbol Table

More Related Content

Data structures logical and physical

  • 1. Logical and Physical Data Structures - A way of understanding data structures - References: 1. Algorithms - Princeton - Coursera 2. Algorithms Booksite
  • 2. Logical Data structures - definition A logical data structure is defined by its API and the semantics of each of the APIs. It does not either imply the physical implementation of the data structure nor necessitate a specific implementation. While several implementations exist for each logical data structure some are optimal vis-a-vis others.
  • 3. Logical Some of the logical data structures include ¡ñ Stacks ¡ñ Queues o Priority Queues ¡ñ Bags ¡ñ Symbol Tables
  • 4. Logical - Illustrative API - Symbol Table
  • 5. Physical - Generic Physical data structures are constructed based on the organization of the computing machine. The memory structures both scale and hierarchy, instruction set both operations and registers drive the physical design of a data structure. There are two physical implementations of data structures at the most generic abstraction level for a computing machine (a deterministic turing machine as opposed to a quantum). ¡ñ Arrays ¡ñ Graphs
  • 6. Physical - Specialized The two generic physical data structures can be further specialized as follows ¡ñ Array o unordered array o ordered array ¡ñ Graph o Linked Lists o Trees ? Binary Trees ¡ñ Binary Search Trees o Self Balancing Binary Search Trees ? Left Leaning Red Black Tree ? ¡­. o Acyclic Graphs ? Directed Acyclic Graphs ? ¡­. o Cyclic Graphs ? ... o And all other variants ? 2-3 Trees ? B-Trees ? Tries