What is the algorithm?

• 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.

A tree is a data structure similar to a linked list but instead of each node pointing simply to the next node in a linear fashion, each node points to a number of nodes. Tree is an example of a non-linear data structure. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form.
In trees ADT (Abstract Data Type), the order of the elements is not important. If we need ordering information, linear data structures like linked lists, stacks, queues, etc. can be used.

A queue is a data structure used for storing data (similar to Linked Lists and Stacks). In queue, the order in which data arrives is important. In general, a queue is a line of people or things waiting to be served in sequential order starting at the beginning of the line or sequence.
Definition: A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at other end (front). The first element to be inserted is the first one to be deleted. Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list.
Similar to Stacks, special names are given to the two changes that can be made to a queue. When an element is inserted in a queue, the concept is called EnQueue, and when an element is removed from the queue, the concept is called DeQueue.
DeQueueing an empty queue is called underflow and EnQueuing an element in a full queue is called overflow. Generally, we treat them as exceptions. As an example, consider the snapshot of the queue.