Data Structures, unit: Linked Lists. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
27 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a linked list?
- A linear data structure where each element (node) points to the next
- What is a node in a linked list?
- A structure containing data and a reference (pointer) to the next node
- What is the time complexity of inserting at the head of a linked list?
- O(1)
- What is the time complexity of accessing the nth element of a linked list?
- O(n), since you must traverse from the head
- What is a singly linked list?
- A linked list where each node points only to the next node
- What is a doubly linked list?
- A linked list where each node points to both the next and previous nodes
- What is a circular linked list?
- A linked list where the last node points back to the first node
- What is the head of a linked list?
- The first node in the list
- What is the tail of a linked list?
- The last node in the list, whose next pointer is typically null
- What is the time complexity of inserting at the tail of a singly linked list without a tail pointer?
- O(n), requiring a full traversal to find the end
- What advantage does a linked list have over an array for insertion and deletion?
- No shifting of other elements is required, just pointer updates
- What advantage does an array have over a linked list?
- Constant-time random access by index, and better memory locality
- What is a common technique to detect a cycle in a linked list?
- Floyd's cycle detection (the 'tortoise and hare' technique using two pointers)
- How does the tortoise and hare technique detect a cycle?
- Using a slow and fast pointer; if they ever meet, a cycle exists
- What is the time complexity of reversing a singly linked list?
- O(n)
FlashKeepers