What are data structure operations?

Depending on the organization of the elements, data structures are classified into two types:

1. Linear data structures

Linear data structures are data structures in which elements are organized sequentially or linearly, meaning each element has a direct predecessor and successor, except for the first and last elements. Linear data structures facilitate simple and straightforward traversal of elements from one end to another.

Here are some common examples of linear data structures:

1. Arrays: A collection of elements stored in contiguous memory locations, accessible by their index. Elements in an array have a linear order, and you can traverse them in a linear manner.

2. Linked Lists: A linear collection of elements (nodes), where each node contains both data and a reference (pointer) to the next node. Traversing a linked list involves following the pointers from one node to the next.

3. Stacks: A Last-In-First-Out (LIFO) linear data structure, where elements are added and removed from the same end, called the top. The most recently added element is the first to be removed.

4. Queues: A First-In-First-Out (FIFO) linear data structure, where elements are added at the rear and removed from the front. The oldest element is the first to be removed.

5. Deques (Double-Ended Queues): A linear data structure that allows insertion and deletion at both ends, front and rear.

6. Vectors (Dynamic Arrays): Similar to arrays but with dynamic resizing capabilities, allowing them to grow or shrink as needed.

7. Strings: A sequence of characters arranged in a linear manner. Strings are a fundamental linear data structure in many programming languages.

Linear data structures are essential building blocks in computer science and programming. They are used in various algorithms and applications, ranging from simple data storage and retrieval to more complex data processing tasks. The choice of a specific linear data structure depends on the requirements of the problem you are trying to solve and the desired performance characteristics for the operations you need to perform.

2. Non Linear data structures

Non-linear data structures are data structures in which elements are organized in a way that does not follow a sequential order like linear structures. Elements in non-linear data structures can have multiple predecessors and successors, leading to more complex relationships between elements. These structures are particularly useful when data needs to be represented in a hierarchical or interconnected manner.

Here are some common examples of non-linear data structures:

1. Trees: Trees are hierarchical data structures consisting of nodes connected by edges. Each tree has a root node, and each node can have zero or more child nodes. Nodes with no children are called leaves. Trees can be binary trees, where each node has at most two children, or multiway trees with more than two children per node. Special types of trees include:

   • Binary Search Trees (BST): A binary tree where the left child is less than the parent, and the right child is greater.
   • AVL Trees: A self-balancing binary search tree to ensure efficient operations.
   • Red-Black Trees: Another type of balanced binary search tree with specific properties.
   • B-Trees: Multiway search trees used for efficient disk-based storage and retrieval.

2. Graphs: Graphs are collections of nodes (vertices) connected by edges (links). Unlike trees, graphs can have cycles (cycles are loops in the graph). Graphs can be directed (edges have a direction) or undirected (edges have no direction). Common types of graphs include:

   • Directed Graphs (Digraphs): Edges have a specific direction from one vertex to another.
   • Undirected Graphs: Edges have no specific direction and represent symmetric relationships.
   • Weighted Graphs: Edges have associated weights or costs, representing values like distances or time.

3. Heaps: Heaps are specialized binary trees used to efficiently find the maximum or minimum element in constant time. They can be max heaps or min heaps, where the root node holds the largest or smallest element, respectively.

4. Hash Tables: While hash tables store data in a linear array, they are considered non-linear because the relationship between keys and their corresponding hash locations is not sequential. Hash tables use a hash function to convert keys into array indices, allowing for efficient retrieval based on keys.

5. Trie: A tree-like data structure used for efficient storage and retrieval of a dynamic set of strings with a common prefix. Tries are commonly used for dictionary-like applications and autocomplete features.

Non-linear data structures are essential for representing complex relationships and organizing data efficiently in various applications, including database management systems, network routing algorithms, hierarchical file systems, and more. The choice of a specific non-linear data structure depends on the specific problem domain and the types of operations needed for the application.

• Insertion: Add a new data item in the given collection of data items.
• Deletion: Delete an existing data item from the given collection of data items.
• Traversal: Access each data item exactly once so that it can be processed.
• Searching: Find out the location of the data item if it exists in the given collection of data items.
• Sorting: Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.

• The size of the arrays is fixed, Linked Lists are Dynamic in size.
• Inserting and deleting a new element in an array of elements is expensive, Whereas both insertion and deletion can easily be done in Linked Lists.
• Random access is not allowed in Linked Listed.
• Extra memory space for a pointer is required with each element of the Linked list.
• Arrays have better cache locality that can make a pretty big difference in performance.

Here is a table comparing arrays and linked lists:

In summary, arrays and linked lists have different strengths and weaknesses, and their use depends on the specific needs of the application. Arrays are efficient for random access, while linked lists are efficient for dynamic memory allocation and efficient insertion and deletion operations.

The stack is a linear data structure which the order LIFO(Last In First Out) or FILO(First In Last Out) for accessing elements. Basic operations of the stack are: Push, Pop, Peek

Applications of Stack:

1. Infix to Postfix Conversion using Stack
2. Evaluation of Postfix Expression
3. Reverse a String using Stack
4. Implement two stacks in an array
5. Check for balanced parentheses in an expression

• Queue is used for BFS
• Stack is used for DFS. DFS can also be implemented using recursion (Note that recursion also uses function call stack).

We use two data structures to implement an LRU Cache.

1. Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).The most recently used pages will be near rear end and least recently pages will be near front end.
2. A Hash with page number as key and address of the corresponding queue node as value. See How to implement LRU caching scheme? What data structures should be used?

If inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do inorder traversal and while traversing keep track of previous key value. If current key value is greater, then continue, else return false.