Compare a linked list to an array in terms of insertion and access costs.

Compare a linked list to an array in terms of insertion and access costs.

• A. Linked lists have O(1) insertions at the head but O(n) access; arrays have O(1) access but O(n) insertions in the middle.
• B. Linked lists have O(n) insertions and O(1) access; arrays have O(1) insertions in the middle.
• C. Linked lists have O(1) access and O(1) insertions anywhere; arrays have O(n) access.
• D. Linked lists have O(n) access and O(n) insertions; arrays have O(1) access and O(1) insertions.

Answer: (A)

The main idea is that how data is laid out in memory changes how fast we can do certain operations. In an array, elements are stored contiguously, so accessing any element by index is a quick O(1) operation. However, inserting a value in the middle means shifting all the subsequent elements to make room, which takes O(n) time. In a linked list, elements are scattered in separate nodes linked by pointers, so inserting at the front is just creating a new node and re-linking the head pointer, which is O(1). But to reach a specific position, you have to traverse from the head through the nodes until you get there, which takes O(n) time. This combination—constant-time insertions at the head for linked lists and linear-time access, versus constant-time access for arrays with linear-time insertions in the middle—best describes the typical costs.

The main idea is that how data is laid out in memory changes how fast we can do certain operations. In an array, elements are stored contiguously, so accessing any element by index is a quick O(1) operation. However, inserting a value in the middle means shifting all the subsequent elements to make room, which takes O(n) time. In a linked list, elements are scattered in separate nodes linked by pointers, so inserting at the front is just creating a new node and re-linking the head pointer, which is O(1). But to reach a specific position, you have to traverse from the head through the nodes until you get there, which takes O(n) time. This combination—constant-time insertions at the head for linked lists and linear-time access, versus constant-time access for arrays with linear-time insertions in the middle—best describes the typical costs.