Bihar STET Computer Science – Data Structures & Algorithms Set 2

In a singly linked list, elements are not stored contiguously and there is no direct indexing; searching requires traversing up to n nodes sequentially. Even if the target is absent, every node may need to be examined before the search can conclude. The best case is O(1) when the head node matches, but the worst case is O(n).

Dynamic memory allocation functions like malloc() or new allocate memory at runtime from the Heap segment. In C, malloc()/calloc() return heap memory that remains allocated until free() is called. In C++, new allocates dynamically and delete releases the allocation; the pointer variable itself may be local while the node is on the heap.

The first three options are rely on the LAST-IN-FIRST-OUT(LIFO) nature of stack. The queue data structure is used for synchronization between the processes. Stacks are used for function calls, recursion, expression evaluation, undo and backtracking. Asynchronous producer-consumer transfer is more naturally coordinated with a queue or a message buffer because items are consumed in arrival order.

A Stack operates on the LIFO principle where the last element inserted is the first one to be removed. The two fundamental operations are push (insert at the top) and pop (remove from the top). Both take O(1) time in a standard stack implementation.

Because the last node points back to the head node, a circular linked list can be fully traversed starting from any node in the ring. The tail points back to the head, so traversal can continue cyclically and there is no NULL link at the end. A traversal must stop when it returns to its starting node to avoid an infinite loop.