Learn Data Structures and Types, ADT, List, Graph, Tree, Traversal
A data structure is a way of storing and organizing data for easy and faster retrieval and maintenance.
- Faster retrieval includes easy reading and also faster searches.
- Faster maintenance includes faster insertion, faster updates and deletion of data in a large data
A data structure can either be linear or non-linear. Basic operations on data structures include insertion, deletion, searching, find, and sorting
- Linear Data Structures
- Storing data in a sequential manner. Lists, Stacks and Queues are linear data structures
- Non-Linear Data Structures
- Storing data in a non-sequential fashion. It can be in hiercharchial order or any other non-linear style
Example: Trees, Graphs
Linear Data Structures
Data can be linearly arranged in different ways
- Stack: Stack follows a Last-In -First-Out approach (LIFO). LIFO means that when you retrieve or remove data, you always remove the data that you recently added. You can add and remove data at one end only. Stack is like a box in which you keep putting books one over the other. You can only pick up books one by one from the top. You cannot reach the bottom of the stack directly without removing the top items one by one
- Queue: you can add data at the end and remove data at the other end. In this case, you service the data you added first. In a queue,you always serve the customer who came first and stood in the queue.
- Priority Queue: A queue with each value having a priority.
- Double Ended Queue: You can add and remove data at the both ends in a double ended queue. Double ended queue is sometimes called as Dequeue or Deque which is misleading as it also refers to remove element from a queue and hence the terminology "Dequeue" should never be used.
- Singly Linked List: A list in which element has a link to the next element
- Double Linked list: A list in which element has a link to the next element and a link to the previous element except that first node in the list does not have a previous link and last node does not have a next link
- Circular Linked List: A single or double linked list in which the last node has a link to the first node
Tree
A tree can be structured in different ways. A Tree is a data structure with one root data. Root can have one or more children. Child node can have zero or more children
- Trie: A search tree in which each node has a prefix of its parent.
- Binary Tree: A tree in which each parent has maximum of two children
- Binary Search Tree: Sorted Binary Tree
Graph Shortest Path Algorithms
Graph
A graph is a data structure with nodes and edges with edges connecting the nodes. Graphs can be undirected or directed