Question

Which of the following statements about linked lists is true?

• A. Elements of a linked list are stored in contiguous memory locations.
• B. Accessing the $n^{th}$ element of a linked list takes $O(1)$ time.
• C. In a singly linked list, each node contains a data part and a pointer to the next node.
• D. A linked list cannot be dynamically resized.

Hint:

While Linked Lists have slower access times ($O(n)$) compared to Arrays ($O(1)$), they are much more efficient at insertions and deletions ($O(1)$ if you have the pointer) because no shifting of elements is required.

Answer 1

The Correct Option is C

Concept: A linked list is a linear data structure where elements are not stored at contiguous memory locations.
• Node: The basic unit of a linked list. It consists of a Data field and a Link/Next field.
• Dynamic: Memory is allocated at runtime as needed.

Step 1: Evaluating Option (A).
Linked list elements are scattered in memory; they are linked via pointers. Arrays are the ones stored in contiguous memory. So, (A) is false.

Step 2: Evaluating Option (B) and (D).

• Accessing the $n^{th}$ element requires traversing from the head through $n-1$ nodes, which takes $O(n)$ time. Only arrays offer $O(1)$ random access. So, (B) is false.
• Linked lists are specifically designed to be dynamic. They can grow or shrink by simply allocating or freeing nodes. So, (D) is false.

Step 3: Confirming the structure.
By definition, a singly linked list node has two components: the information (data) and the address (pointer) of the successor node. This matches Statement (C) exactly.