03 Linked Lists Free Online FlashCards

What is a linked list?

A linked list is a linear structure of separate nodes connected by pointers or references; its nodes need not occupy contiguous memory.

What fields does a singly linked node contain?

A singly linked node stores data and a `next` link. The final node's `next` is conventionally `null` or `None`.

What does the head reference identify?

The `head` reference identifies the first node. In an empty list, `head` is `null` or `None`.

What is the complexity of iterative list traversal?

Iterative traversal takes $O(n)$ time and $O(1)$ extra space because it visits each of the $n$ nodes once.

How do you insert a node at the front?

Set `new.next = head`, then set `head = new`. This preserves access to the original list and takes $O(1)$ time.

How does a tail reference affect append complexity?

With only `head`, appending takes $O(n)$ because the last node must be found. With a maintained `tail`, it can take $O(1)$.

How do you insert after a known node?

Set `new.next = current.next`, then `current.next = new`. Once `current` is known, the insertion takes $O(1)$ time.

What distinguishes a doubly linked node?

A doubly linked node stores `data`, `prev`, and `next`, allowing traversal toward both the predecessor and successor.

What is the complexity of removing a known doubly linked node?

Once the target node is known, removing it takes $O(1)$ time by reconnecting its predecessor and successor links. Locating it may take $O(n)$.

What defines a circular linked list?

In a circular linked list, the final node links back to the first instead of storing `null`; for a circular singly linked list, `tail.next` is `head`.

How should traversal stop in a circular list?

Stop when `current == head` after processing the starting node, because a circular list never reaches `null`.

Why is indexed access slow in a linked list?

Access by index is generally $O(n)$, because the implementation must follow links from the head to reach the requested position.