A Data-Structure is data organization, management and storage format that enables 'efficient' access of data and modification.
Data structure implements the physical form of the data type, where as data type (ADT) is logical form how to implement the data types.
ADT is implementation independent. For example, it only describes what a data type List consists (data) and what are the operations it can perform, but it has no information about how the List is actually implemented.
Whereas data structure is implementation dependent, as in the same example, it is about how the List implemented ie., using array or linked list. Ultimately, data structure is how we implement the data in an abstract data type.
Next we will learn following Data structures and implement their operations in python.
Data Structures |
Operations |
|---|---|
| Stack | As an Abstract Data Type - Implementing the Stack and Infix, Postfix and Prefix: Definitions, Evaluationand Conversions. |
| Queues and Lists | The Queue as Abstract Data Type – Sequential Representation _Types of Queues – Operations. |
| Linked List | Operations – Implementation of Stacks, Queues and priority Queues. |
| Circular Lists | Insertion, Deletion and Concatenation Operations ,Stacks and Queues as Circular Lists, Doubly Linked List. |
| Trees | Binary Trees Operations and Applications |
| Binary Tree Representation | Node Representation – Implicit array Representation – Choice of Representation – Binary Tree Traversal – Threaded Binary Trees and their Traversal – Trees and their Applications. |
| Sorting | General Background: Efficiency – The big 0 Notation – Efficiency of Sorting. Bubble Sort and Quick Sort and their Efficiency – Selection Sorting – Binary Tree Sort – Heap Sort – Insertion Sorts – Shell Sort – Address calculation Sort – Merge and Radix Sorts. |
| Searching | Basic Searching Techniques: Dictionary as an Abstract Data Type – Algorithmic Notation – Sequential Searching and its Efficiency – Binary Search – Interpolation Search. |
| Tree Searching | Insertion into a Binary Search Tree – Deleting from a Binary Search Tree – Efficiency of Binary Search Tree operation |
| Graphs and Their Application | Application of Graphs – Representation of Graphs in C – Transitive closure – Warshall’s Algorithm – Shortest Path Algorithm. |
| Linked Representation of Graphs | Dijikstra’s Algorithm – Organizing the set of Graph Nodes – Application to Scheduling and its implication. |
| Graph Traversal and Spanning Forests | Undirected Graph and their Traversals, Applications and Efficiency – Minimal Spanning Trees – Prim’s and Kruskal’s Algorithms. |