Datastructure ADT

Reason for listing them down is for every methods in ADT as it difference from structure to structure and we have check runtime performance.

The way performance is calculated is based on inputs or sometime based on internal properties like height, depth, degree etc.,  But all the performance dependent on the Representation or implementation details (like graph / tree using vector, array, list etc.,)

Data Structures like Stack, Queues, Linked Lists, Tree, Graph are called as Abstract Data Types with few behaviors or operations or methods.

They are very special because, one has to know them before implementing any algorithm with them in advanced algorihtms where we don't make use of exact data structures provided out of box from programming languages but we will design them for our custom purposes with tweaks.

1. Stack  - push, pop (INSERT and REMOVE, no traversal)

REPRESENTATION - ARRAY (BEST), LINKED LIST

2. Queue - enqueue, dequeue  (INSERT and REMOVE, no traversal)

REPRESENTATION - ARRAY (BEST), LINKED LIST

3. Linked list - first, last, before, after (Traversal is like a person climbing a rope)

        Insert for Singly linked list alone is a special case, it take much time when compared to doubly linked list. (It is not a chain where we could de-link and link anywhere, every time one has to traverse from first)

4. vector - rank based. rank 

    sequence - mixed of vector and list.

REPRESENTATION - ARRAY(BEST), LINKED LIST

5. Tree - parent, children, root (like first), leaf (like last), internal, external. 

degree - count of children.

REPRESENTATION - VECTOR AND LIST

Traversal is with iterator - hasNext, next at each level.

Sub Structures

Spanning tree

Special Traversal

PreOrder, InOrder, PostOrder

Specialized Structures with special properties

Binary Tree - leftchild, rightchild

Heap - binary tree with Total order reflection

6. Graphs (vertices and edges) -  (there is no first, next, last, nor parent, children)

incident (incoming/outgoing) edges, adjacent(nearby) vertices, parellel edges.

REPRESENTATION - 

LIST, MATRIX.

EDGE LIST, ADJACENCY LIST and ADJACENCY MATRIX

Paths, Cycles - Simple and complex.

Sub Structures

Sub graph

Spanning Tree, Forest

Connect Graph

Special Traversals

BFS,

DFS

Shortest Path

Specialized Structures with special properties

UNDIRECTED graph

DIRECTED graph

Weighted Graph 

Non Weighted Graph

degree - count of incoming/outgoing edges.