Data Structures - Introduction
- Abstract data types
- Linear Data Structures
- Linked List Introduction
- Single Linked List
- Stacks using Array
- Stacks using linkedlist
- Queues using array
- Queues using linkedlist
- Stack Applications
- Infix to Postfic Converstion
- Postfix Evaluation
- Dictionaries
- Introduction to Dictionaries
- Linear list representation
- Skip list representation
- Hash Table
- Introduction Hash Table
- Hash functions
- Collision Resolution
- Separate chaining
- Open addressing
- Rehashing
- Extendible hashing
- Trees
- Introduction to Tree
- Binary trees Representation
- Binary tree traversals
- Binary Search Tree
- AVL Tree
- Red Black Tree
- Splay Tree
- B Tree
- B+ Tree
- Comparison of Trees
- Graphs
- Introduction to Graph
- Graph Representation
- Breadth-First Search
- Depth-First Search
- Sorting
- Quick Sort
- Merge Sort
- Heap Sort
- Pattern Matching
- Introduction to pattern Matching
- Brute force Pattern Matching
- Boyer–Moore Pattern Matching
- KMP Pattern Matching
- Tries
- Introduction to Tries
- Standard Trie
- Compressed tries
- Suffix Trie
Abstract data types
Abstract Data Types (ADTs) are a foundational concept in computer science and software engineering, serving as a blueprint for creating more complex data structures. They define the nature and behavior of a data structure but not its implementation. In other words, ADTs provide a way to describe what a data structure does but not how it does it.
Components of Abstract Data Types
- Data: The values that will be stored by the data structure.
- Operations: The set of functions or methods that can be applied to the data.
Formal Definition of Abstract Data Types
In more formal terms, an ADT is often defined using mathematical notation to specify its properties and operations. For example:
List ADT can be defined as a tuple L=(D,O)
D is a finite ordered set of elements.
O is a set of operations like insert(i,x), delete(i), find(x), etc.
Characteristics of ADTs
- Encapsulation: ADTs encapsulate data and the operations that manipulate that data, exposing only the essential features to the outside world.
- Abstraction: ADTs provide a high level of abstraction, allowing the programmer to focus on what operations are needed rather than how to implement them.
- Information Hiding: The actual internal workings of an ADT are hidden from the user. Users interact with the ADT through a well-defined interface.
- Reusability: An ADT can be implemented in multiple ways, which makes it reusable. You can switch from one implementation to another without affecting the rest of the code.
- Integrity: ADTs ensure that the operations performed are valid, thereby maintaining the integrity of the data.
Common Abstract Data Types
- List ADT: Defines operations for a sequential collection of elements.
- Operations: insert, delete, find, size, etc.
- Stack ADT: Last-In, First-Out (LIFO) behavior.
- Operations: push, pop, peek, isEmpty, etc.
- Queue ADT: First-In, First-Out (FIFO) behavior.
- Operations: enqueue, dequeue, front, isEmpty, etc.
- Tree ADT: Hierarchical data structure.
- Operations: insert, delete, find, traverse, etc.
- Graph ADT: A set of nodes and edges.
- Operations: addVertex, addEdge, removeVertex, removeEdge, findAdjacentNodes, etc.
Next Topic :Linked List Introduction