What is a Linked List and What are its types?

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

A data structure is an arrangement of data in a computer's memory or even disk storage. It has a different way of storing and organizing data in a computer so that it can used efficiently. Different kind of Data structure is used in different application. For example, B-tree is widely used in implementation of databases.

Data structures are a way of organizing and storing data in a computer's memory or storage space. There are many types of data structures, each with its own set of advantages and disadvantages depending on the specific application. Here are some common examples of data structures:

1. Arrays: Arrays are a collection of elements of the same data type. They are used to store a fixed-size sequential collection of elements.

2. Linked Lists: Linked lists are a data structure in which each element contains a reference to the next element in the list. They are used to store a collection of elements that can be added or removed dynamically.

3. Stacks: Stacks are a data structure in which elements are added and removed from the top. They are used to implement functions such as recursion and backtracking.

4. Queues: Queues are a data structure in which elements are added at one end and removed from the other. They are used in various applications such as scheduling and buffering.

5. Trees: Trees are a hierarchical data structure in which each node has one parent and zero or more children. They are used in many applications such as sorting, searching, and data compression.

6. Graphs: Graphs are a data structure in which nodes are connected by edges. They are used in many applications such as social networks, routing, and scheduling.

Overall, data structures play a crucial role in computer science and programming by providing efficient ways to store, access, and manipulate data.

There are basically two types of data structures
1 Linear data Structure
2 Non Linear data Structure

Linear data structure organizes their elements in a linear fashion, where data elements are attached one after another. They are organized in a way similar to how the computer's memory is organized.

1) To have the linear relationship between the elements represented by means of sequential memory locations. For Example- ARRAY

2) To have the linear relationship between the elements represented by means of pointers and links. For Example- LINKED-LIST

Non-linear data structure is a type of data structure in which the data elements are not arranged in a sequential manner. In other words, the elements are not stored in a linear or sequential manner and do not follow a specific order. Non-linear data structures are used when data elements have a hierarchical relationship and there is a need to represent the relationship between the elements.

Some examples of non-linear data structures are:

1. Trees: Trees are a hierarchical data structure where each node has a parent and zero or more children.

2. Graphs: Graphs are a collection of nodes and edges that connect them. Graphs can be used to represent complex systems such as social networks, transportation networks, and computer networks.

3. Heaps: Heaps are a type of binary tree used to implement priority queues.

Non-linear data structures are commonly used in various fields such as computer science, engineering, mathematics, and natural sciences. They allow for efficient representation of complex relationships between data elements, making them an essential tool in various applications.