English
Menu

What is Linked list?

A data structure in which each element holds a value and a pointer to the next element, and the elements are linked by following the pointers. Once the position is known, insertion and deletion are O(1) pointer changes, but reading the i-th element requires walking from the front, O(n). The elements tend to be scattered in memory, so caches work less well than with arrays.

Japanese name: 連結リスト

Linked list appears in 9 practice questions across 5 topics, including Data Structures and Algorithms, Memory Hierarchy, Programming Basics (Pseudocode Tracing).

Field: Data Structures and Algorithms

Try it: questions about Linked list

Compared with an array, which is a correct description of a linked list (a list in which each element holds a pointer to the next element)?

  1. AIf the element just before the insertion point is known, a new element can be inserted just by changing pointers without moving other elements, but reading the i-th element requires following the list from the front
  2. BThe position of the i-th element can be computed, so any element can be read in constant time, O(1)
  3. CThe elements are stored contiguously in memory, so caches and prefetching work well when reading them in order
Show answer and explanation

Answer: A. If the element just before the insertion point is known, a new element can be inserted just by changing pointers without moving other elements, but reading the i-th element requires following the list from the front

In a linked list, once the position is known, insertion and deletion only require rewriting the neighboring pointers, which takes O(1). Reading the i-th element, however, requires following i pointers from the front, which takes O(n). An array can compute the address of the i-th element from its start address and element size, so it reads any element in O(1), but inserting in the middle takes O(n) to shift the following elements. Also, because array elements are contiguous, caches and prefetching work well, whereas the nodes of a linked list tend to be scattered in memory, so even an O(n) traversal can be much slower.

Which correctly compares chaining (linking the elements at the same position into a linked list) and open addressing (finding another free position within the table) as ways to resolve hash table collisions? The load factor is the number of stored elements divided by the table size.

  1. AChaining can store elements even when the load factor exceeds 1, but open addressing cannot store more elements than the table size, and its number of probes rises sharply as the load factor approaches 1
  2. BOpen addressing has no collisions, so a search always takes one probe regardless of the load factor
  3. CWith chaining, the search cost stays the same however high the load factor becomes
Show answer and explanation

Answer: A. Chaining can store elements even when the load factor exceeds 1, but open addressing cannot store more elements than the table size, and its number of probes rises sharply as the load factor approaches 1

Chaining links elements at the same position into lists, so it can store more elements than the table size, but the average list length grows in proportion to the load factor and so does the search cost. Open addressing stores everything inside the table, so it can hold at most as many elements as the table size, and the number of probes to find a free slot rises sharply as the load factor approaches 1. With either method, it is usual to enlarge the table and reinsert all elements (rehash) once the load factor exceeds a chosen limit, such as about 0.5 to 0.75. Collisions also occur in open addressing; it handles them by looking for a free position.

Linked list in the explanations

Questions that mention Linked list (9)

  1. Why does traversing the linked list above tend to be much slower than reading an array with the same number of elements in order?
  2. Compared with an array, which is a correct description of a linked list (a list in which each element holds a pointer to the next element)?
  3. Which correctly compares chaining (linking the elements at the same position into a linked list) and open addressing (finding another free position within the table) as ways to resolve hash table collisions? The load factor is the number of stored elements divided by the table size.
  4. The following program outputs a linked list, whose elements are linked by the array next, by following it from the element at index 1. Array indices start at 1. A next value of 0 marks the end of the list. What sequence of values is output?
  5. The following program inserts "F", in val[6], right after "C" (index 3) in the linked list A → C → E → D → B, linked by the array next, and then outputs the list from the element at index 1. Array indices start at 1. A next value of 0 marks the end of the list. What should replace 【a】 so that the output is A, C, F, E, D, B?
  6. For which access pattern is hardware prefetching especially effective?
  7. Which describes the ABA problem that affects lock-free data structures built with CAS?
  8. Which processing tends to run inefficiently on a GPU?
  9. The values 1, 2, 3, …, 1000 are inserted in this order into an empty binary search tree (no rebalancing is done). When searching this tree for 1000, how many nodes are compared, starting from the root, before it is found?

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

Semiconductor, Electronics and Computing Calculators

Hash table calculatorShow the collisions and storage positions when keys are inserted into a hash table, with chaining, linear probing, quadratic probing and double hashing; also calculates the load factor and the average number of probes

Related terms

Array Prefetching Pointer Hash table ABA problem Load-reserved/store-conditional (LR/SC) GPU Binary search tree Binary heap Binary search

Back to the glossary