Arizona State University (ASU) CSE240 Introduction to Programming Languages Midterm Practice Exam

The choice of a linked list as the best data structure for efficient insertion and deletion is based on its inherent design. A linked list is composed of nodes, each containing data and a reference (or pointer) to the next node in the sequence. This allows you to efficiently insert or delete a node at any position without needing to shift elements around, which is necessary in an array.

When you insert or delete a node in a linked list, you need to adjust a few pointers, which can be done in constant time, assuming you have a reference to the node before the one you want to insert or delete. This makes operations like adding or removing elements particularly efficient.

In comparison, arrays require shifting elements, which can lead to a linear time complexity for insertion or deletion, especially if you're working near the beginning of the array or need to maintain the order of the other elements. Stacks and queues, while also efficient for their respective operations (LIFO for stacks and FIFO for queues), do not offer the same flexibility for arbitrary insertion and deletion as linked lists do. Thus, the linked list is the optimal choice for scenarios that require frequent modifications of the data structure.