Data Structure
What is Data Structure
A data structure is a specialized format for organizing and storing data. General data structure types include the array, the file, the record, the table, the tree, and so on. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways. In computer programming, a data structure may be selected or designed to store data for the purpose of working on it with various algorithms.
Basic types of data structure
Then we also have some complex Data Structures, which are used to store large and connected data. Some example of Abstract Data Structure are :
1. Linked List
2. Tree
3. Graph
4. Stack
5. Queue
1. Linked List
In computer science, a linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration.
2. Tree
In computer science, a tree is a widely used Abstract Data Type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and sub trees of children with a parent node, represented as a set of linked nodes.
3. Graph
A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph.A tree that is not empty consists of a root node and potentially many levels of additional nodes that form a hierarchy.
4. Stack
A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack.
OR
In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.
5. Queue
A queue or FIFO (first in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: enqueue, the process of adding an element to the collection.(The element is added from the rear side) and dequeue, the process of removing the first element that was added. (The element is removed from the front side). It can be implemented by using both array and linked list.
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a triple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set.Some authors allow the binary tree to be the empty set as well.
​
Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search, when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right sub trees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.
An AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child sub trees of any node differ by at most one; if at any time they differ by more than one, re-balancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be re balanced by one or more tree rotations.
What is Recursion ?
Recursion is define as:-
​
1. Directly recursive: method that calls itself.
2.Indirectly recursive method that calls another method and eventually results in the original method call.
3. Tail recursive method recursive method in which the last statement executed is the recursive call.
4. Infinite recursion: case where every recursive call results in another recursive call.
What is STACK??
Its One side open and another side closed. Its worked as LIFO(Last In First Out).
​In programming, a stack is a data area or buffer used for storing requests that need to be handled. The IBM Dictionary of Computing says that a stack is always a push-down list, meaning that as new requests come in, they push down the old ones. Another way of looking at a push-down list - or stack - is that the program always takes its next item to handle from the top of the stack. (This is unlike other arrangements such as "FIFO" or "first-in first-out.")
What is Queue??
Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR(also called tail), and the deletion of existing element takes place from the other end called as FRONT(also called head). This makes queue as FIFO(First in First Out) data structure, which means that element inserted first will also be removed first.
The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.
