Computer Science – 10.4 Introduction to Abstract Data Types (ADT) | e-Consult

An Abstract Data Type (ADT) is a mathematical model of a data structure that specifies the logical properties of the data structure, without specifying how it is implemented. It defines a set of operations that can be performed on the data, and the expected behavior of those operations. Crucially, an ADT separates the what (the abstract behavior) from the how (the concrete implementation).

A stack, queue, and linked list are examples of ADTs because they are defined by their logical properties and the operations that can be performed on them. For example:

• Stack: An ADT with operations like push (add an element to the top), pop (remove the top element), and peek (view the top element). The implementation could be an array or a linked list, but the stack ADT defines the behaviour – Last-In, First-Out (LIFO).
• Queue: An ADT with operations like enqueue (add an element to the rear), dequeue (remove the element from the front), and peek (view the front element). The implementation could be an array (circular queue) or a linked list, but the queue ADT defines the behaviour – First-In, First-Out (FIFO).
• Linked List: An ADT with operations like insert (add a new node), delete (remove a node), search (find a node), and traverse (visit nodes in sequence). The implementation uses nodes with data and pointers to the next node, but the linked list ADT defines the behaviour – a sequence of elements where each element points to the next.

The key distinction is that the ADT focuses on the interface (the operations) and the properties of the data, while the implementation details (e.g., using arrays or linked lists) are hidden. This allows for flexibility – the same ADT can be implemented using different underlying data structures.