4 Linked Lists Free Online FlashCards

What is a linked list?

A linked list is a linear structure of nodes connected by links, with a reference to its first node, the head.

What does a linked-list node contain?

A node stores a payload, or value, and one or more links that reference neighboring nodes.

What is the head?

The head is the reference to the first node in a linked list.

How does a singly linked list mark its end?

The final node's next link is null, which marks the end of a singly linked list.

How do you traverse a singly linked list?

Traversal starts at head and repeatedly follows next until the current node is null.

What is linked-list traversal complexity?

Traversal takes $O(n)$ time because each of the list's $n$ nodes may need to be visited.

How do you insert at the front?

Front insertion takes $O(1)$ time: set new_node.next to head, then update head to new_node.

When is insertion after a node $O(1)$?

If the predecessor is known, insertion after it takes $O(1)$ time by assigning new_node.next = current.next and current.next = new_node.

How do you delete the first node?

Deleting the first node takes $O(1)$ time: save head if needed, then set head = head.next.

Why cannot a singly linked list move backward directly?

A singly linked list cannot move backward directly because each node links only to the next node, not the previous one.

What distinguishes a doubly linked list?

A doubly linked node has both next and prev links, allowing movement toward the next and previous nodes.

Why can known-node deletion be $O(1)$ in a doubly linked list?

Deleting a known node in a doubly linked list takes $O(1)$ time by connecting its neighbors with A.next = C and C.prev = A.