Match the LIST-I with LIST-II.

	List – I (Data structure)		List – II (Characteristics)
A.	Stack	I.	First-In-First-Out (FIFO) order
B.	Queue	II.	Last-In-First-Out (LIFO) order
C.	Linked list	III.	Nodes with two children ordered
D.	Binary search tree	IV.	Dynamic size, nodes linked sequentially

Choose the correct answer from the options given below:

Correct option is B

A stack follows the Last-In-First-Out (LIFO) principle, meaning the most recently inserted element is removed first.
A queue follows the First-In-First-Out (FIFO) principle, where the element inserted earliest is removed first.
A linked list consists of dynamically allocated nodes connected sequentially through links or pointers, allowing its size to grow or shrink during execution.
A binary search tree (BST) is a tree structure in which each node has at most two children, with smaller keys generally placed in the left subtree and larger keys in the right subtree.
Information Booster
1. Stack – LIFO
· Insertion is called push, while deletion is called pop.
· Both operations are normally performed at the top of the stack.
· Example: Undo operations, function-call stack, expression evaluation.
· A stack can be implemented using an array or linked list.
· The basic push and pop operations generally take O(1) time.
2. Queue – FIFO
· Insertion is called enqueue, and deletion is called dequeue.
· Elements are inserted at the rear and removed from the front.
· Examples include CPU scheduling, printer queues and buffering.
· Common variants include circular queue, priority queue and deque.
· In a properly implemented queue, enqueue and dequeue can generally be performed in O(1) time.
3. Linked List – Dynamically Linked Nodes
· A linked list is composed of nodes, where each node stores data and a link/reference to another node.
· In a singly linked list, each node normally points to the next node.
· Unlike an array, its elements need not occupy contiguous memory locations.
· Insertion and deletion can be efficient when the relevant node position/reference is already available.
· Major types include singly linked, doubly linked, and circular linked lists.
4. Binary Search Tree – Ordered Binary Structure
· A BST is a binary tree in which each node has at most two children.
· For the standard BST property, keys in the left subtree are smaller than the node's key, while keys in the right subtree are larger.
· An in-order traversal of a BST produces the keys in sorted order.
· Searching, insertion, and deletion have O(log n) average complexity in a reasonably balanced BST.
· In the worst case, a highly skewed BST can have O(n) time complexity for these operations.
Additional Knowledge
· Important distinction: A binary tree only restricts each node to at most two children; a binary search tree additionally imposes an ordering relationship among the keys.
· Complexity trap: The often-quoted O(log n) BST operations assume a balanced or reasonably shaped tree. A skewed BST may degrade to O(n).