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.
Study 03 Linked Lists with 12 free online flashcards. Review key terms, definitions, and concepts with this interactive flashcard deck.
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.
A focused set of flashcards covering Python variables, data types, expressions, control flow, functions, input, output, and common programming practices.
Learn how Boolean expressions, logical operators, and conditional structures let programs make reliable decisions, including how to handle boundaries, branch order, and testing.
A structured guide to the main data structures, their operations, efficiency trade-offs, representations, and practical selection criteria.
A 14-question quiz on trees, binary trees, traversals, recursive algorithms, and binary search trees. The questions progress from foundational concepts to applied reasoning about structure, complexity, and BST operations.
A structured guide to comparison-based sorting algorithms, their complexity, stability, memory use, and practical selection criteria.
A progression through how data is organized, searched, exposed through software interfaces, and managed through abstraction layers in modern computer systems.
A medium-difficulty quiz on integrating problem definition, representation, algorithms, complexity analysis, testing, correctness, ethical evaluation, and documentation in a computer science capstone.
A practical guide to integrating problem definition, data representation, modular programming, algorithms, complexity analysis, testing, correctness, and ethical evaluation into a responsible computer science capstone.
This quiz covers process management, context switching and scheduling, multitasking, traps and interrupts, and RISC-V privilege transitions.