Chapter 14 — Node-Based Data Structures

0.0(0)
Studied by 0 people
call kaiCall Kai
Locked
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/36

encourage image

There's no tags or description

Looks like no tags are added yet.

Last updated 8:01 PM on 7/29/26
Name
Mastery
Learn
Test
Matching
Spaced
Call with Kai
Chat

No analytics yet

Send a link to your students to track their progress

37 Terms

1
New cards
Node
A unit of data that also stores a link to another node
2
New cards
Node-based data structure
A data structure built from nodes connected by links
3
New cards
Linked list
A node-based data structure where each node points to the next node
4
New cards
Classic linked list
A linked list where each node links only to the next node
5
New cards
Singly linked list
Another name for a classic linked list where nodes point forward only
6
New cards
Data field
The part of a node that stores the actual value
7
New cards
Link
The part of a node that points to the next node
8
New cards
next_node
The link from one node to the next node in a linked list
9
New cards
Null link
The final node’s link value showing that the list has ended
10
New cards
First node
The starting node of a linked list
11
New cards
Head
Another name for the first node in a linked list
12
New cards
Last node
The final node in a linked list
13
New cards
Tail
Another name for the last node in a linked list
14
New cards
Array memory
Arrays store values in one continuous block of memory
15
New cards
Linked list memory
Linked list nodes can be scattered across memory
16
New cards
Why linked lists can be flexible
Nodes do not need to be stored next to each other in memory
17
New cards
Linked list reading
O(N), because the computer must follow links from the first node
18
New cards
Linked list search
O(N), because each node may need to be checked one by one
19
New cards
Linked list insertion at beginning
O(1), because only the first-node link needs to change
20
New cards
Linked list insertion at an index
O(N), because the computer must first walk to the node before that index
21
New cards
Linked list insertion after known node
O(1), because only links need to be updated
22
New cards
Linked list deletion at beginning
O(1), because the first-node link can move to the next node
23
New cards
Linked list deletion at an index
O(N), because the computer must first find the node before the deleted node
24
New cards
Array vs linked list reading
Arrays are faster because reading by index is O(1), while linked lists are O(N)
25
New cards
Array vs linked list insertion at beginning
Linked lists are faster because arrays must shift values right
26
New cards
Array vs linked list deletion at beginning
Linked lists are faster because arrays must shift values left
27
New cards
Doubly linked list
A linked list where each node points to both the next node and the previous node
28
New cards
previous_node
The link from one node to the node before it
29
New cards
Doubly linked list advantage
It can move forward and backward through the list
30
New cards
Doubly linked list first node
The node at the front of the list
31
New cards
Doubly linked list last node
The node at the end of the list
32
New cards
Doubly linked list insertion at end
O(1), if the list tracks the last node
33
New cards
Doubly linked list deletion from front
O(1), because the first node can be removed and links updated
34
New cards
Queue with doubly linked list
A queue can use a doubly linked list to enqueue at the end and dequeue from the front efficiently
35
New cards
Why arrays are weaker for queues
Deleting from the beginning of an array is O(N) because values must shift
36
New cards
Why doubly linked lists are good for queues
They can insert at the end and delete from the beginning in O(1)
37
New cards
Main lesson of Chapter 14
Linked lists trade fast index access for flexible node insertion and deleti