CODEWITHSUNDEEP
data-structures
GRANZER
GRANZER

Reputation: 385

What is the difference between Abstract Data Type and Logical Data Structure?

I am having a hard time differentiating between the Abstract Data Type (ADT) and Logical Data Structure (LDS). The only difference I can think of is that ADTs have defined operations, where as LDS are more about how the data is stored. But a Stack can be an ADT as we know what kind of operations must be denied to call something a 'stack' and also it can be called an LDT as we know how the data is should be 'structured' to call it a 'stack'. Both ADT and LDS are 'abstract' in that we don't talk about how they are implemented. So is it correct that ADT and LDS are different names for the same thing, but depending on where we come from we can call it ADT or LDS?

Upvotes: 1

Views: 547

Answers (1)

Ashwin Ganesan
Ashwin Ganesan

Reputation: 331

An abstract data type (ADT) is a mathematical model along with some operations that are performed on that model. For example, the stack ADT consists of a sequence of integers (say) along with the operations push, pop, isempty, makeemptystack and top. An ADT is similar to an interface in Java, and are the specs. Data structures are about how these specs are implemented. For example, the stack ADT operations can be implemented using an array data structure, or using a linked list data structure. A queue ADT can be implemented using a circular array data structure in such a manner that all the ADT operations can be done in O(1) time.

In a real-world problem, you would encounter only a subset of the possible operations, which form your ADT, and you need to find a data structure that would implement exactly this subset of operations efficiently. For example, in some applications, you want to maintain a set of integers, and the only operations you would do on this set are to find the value of the smallest element in the set, delete the smallest element in the set, and insert a new element into the set. (Applications include Dijkstra's shortest path algorithm, Prim's minimum spanning tree algorithm, and Huffman coding.) A set, with these three operations MIN, EXTRACTMIN and INSERT, define the min-priority queue ADT. A data structure that can implement all these three operations effficiently - in O(log n) time - is a minheap. Other data structures - such as linked lists, unsorted arrays, sorted arrays - would take O(n) time for one or more of these operations, and hence are less efficient for this particular ADT.

Upvotes: 1

Related Questions