Question

1. Considering singly linked list, be able to determine if inserting nodes at the end of a LinkedList is less time-efficient than inserting them at the front of the list.

2. Be able to differentiate between the data structures Stack, Queue, and Linked List.

3. Determine between the acronyms LIFO and FIFO, and be able to give one real life example where each is applicable

Answer 1

1. In a normal program, the process of adding nodes to the end of a linked list is less time efficient when compared to adding them at the front. The time complexity for insertion at the end of linked list is O(n) (unless a dedicated pointer is used for tail in which case it will be O(1)) unlike insertion at front where time complexity is O(1).

2. Stacks are data structures will allow both insertion and deletion from only one end, referred to as "Top". They follow the policy of LIFO or Last In First Out.

Queues are data structures which allow insertion from one end and deletion from another. They follow the principle of FIFO or First In First Out.

Linked list is a data structure that is employed to implement Stacks and Queues according to the need of a program. The convenience of linked lists is that they allow easy operation even when we are not aware of the size of the data we need to store.

3. LIFO or Last In First Out says that the last inserted element exits the system first. For this we can consider the example of a stack of CDs or plates where the one at the top was the one inserted last and will also be the one to be taken out first.

FIFO or First In First Out says that the first inserted element exits the system first. For this you can envision a queue at a ticket booth. The people who got in the line first exit the line first too.