Explain the difference between a linked list and an array in terms of memory allocation.

In terms of memory allocation, a linked list dynamically allocates memory for each element, meaning that each element can be stored at a different memory location, connected through pointers. On the other hand, an array has fixed memory allocation, meaning that elements are stored in contiguous memory locations. This gives arrays constant-time access to any element, while linked lists have O(n) access time since you need to traverse the list. Despite this, linked lists offer constant-time insertion and deletion compared to arrays, which may require shifting elements, resulting in O(n) time complexity.