Introduction
In this article, let’s have a look at physical vs logical data structures.
Physical DataStructures
Physical data structures are the actual implementations of data structures in memory. They determine the performance and efficiency of algorithms that use the data structure, by determining how the data is stored and accessed in memory.
For example, a linked list is a logical data structure that consists of a sequence of nodes, each of which contains an element and a reference (or “pointer”) to the next node in the sequence. A physical implementation of a linked list might use an array to store the elements, with each element’s index in the array serving as a pointer to the next element. This implementation has a time complexity of O(n) for most operations because the time required to access an element in the linked list depends linearly on the position of the element in the list.
On the other hand, a physical implementation of a linked list using a doubly-linked structure, where each node has references to both the next and previous nodes in the list, can have a time complexity of O(1) for some operations, such as inserting or deleting elements from the list. This is because the time required to perform these operations does not depend on the size of the list, but only on the time required to update the references in the nodes.
In general, physical data structures are an important consideration in algorithm design, because they determine the performance and efficiency of the algorithm. By choosing the right physical data structure for a given problem, we can ensure that our algorithms will run quickly and efficiently, even on large inputs.
Logical DataStructures
Logical data structures are the abstract concepts of data structures, independent of any particular implementation. They provide a common language and framework for understanding and analyzing algorithms, by describing the organization and relationships of the data used by the algorithm.
The following is a list of logical data structures.
- Stack
- Queue
- Tree
- Graph
- Hash Table
We have seen about the above data structures and their ADTs in the previous articles.
- stack data structure: stack data structure follows the LIFO principle, which means the element which is inserted last will be removed first.
- Queue data structure: queue data structure follows the FIFO principle, which means the element which is inserted first will be removed last.
- Tree data structure: the tree data structure consists of nodes at different levels which are linked together. Tree data structure forms a hierarchical relationship. every two nodes in a tree are related in a parent-child manner. Binary trees, binary search trees, AVL trees, red-black trees etc are different kinds of trees formed according to their structure and efficiency.
- Graph data structure: graph data structure consists of vertices and edges. Vertices in the graphs are used to store the data and edges are used to represent the relationship between the vertices.
