Linked List Operations in C++
A singly linked list consists of nodes containing data and a next pointer, with head identifying the first node.
Summary
A singly linked list consists of nodes containing data and a next pointer, with head identifying the first node. An empty list has head == nullptr; the final node of a nonempty list has next == nullptr.
Insertion and deletion modify links rather than shift elements. To insert at the head, execute newNode->next = head; before head = newNode;. To insert after a valid node p, execute newNode->next = p->next; before p->next = newNode;.
To delete after p, save its non-null successor as victim, connect p to victim->next, and then delete victim. Head deletion similarly saves the current head, advances head, and deletes the saved node. Traversal follows next pointers from head until nullptr.
| Operation | Time | Condition |
|---|---|---|
| Head insertion or deletion | Deletion requires a nonempty list | |
| Search or indexed access | worst case |
🧠 Key Concepts
- Node structure
- Head insertion
- Predecessor links
- Node deletion
- List traversal
- Empty list invariant
- Tail maintenance
- Memory ownership
- Copy control
🧠 Quick Check
See what you remember from the summary.
A newly allocated node must be inserted after a valid node p. Which sequence preserves access to the existing successor?
🧠 Flashcards Preview
Tap a card to reveal the definition.
Ready to quiz yourself?
Test what you remember with a full practice quiz on this note. Create a free account and start in seconds.
Full Notes
Read the original note content before deciding whether to save or study from it.
Linked List Operations in C++
📘 Overview A singly linked list stores nodes connected by next pointers, with a head pointer identifying the first node. Operations depend on preserving links, handling empty lists, and managing dynamically allocated nodes correctly.
🧠 Key Idea Linked list insertion and deletion change pointers rather than shifting elements. These updates take constant time when the required predecessor is already available; locating that predecessor may require linear traversal.
⚔️ Core Details: - Node structure: A typical C++ node contains a data member and a Node* next member initialized to nullptr. - Head insertion: For a newly allocated node, execute newNode->next = head; followed by head = newNode;. - Insertion after a valid node p: Execute newNode->next = p->next; followed by p->next = newNode;. - Deletion after p with a non-null successor: Execute Node* victim = p->next; then p->next = victim->next; then delete victim;. - Head deletion for a nonempty list: Execute Node* victim = head; then head = head->next; then delete victim;. - Traversal: Start a cursor at head and repeatedly follow next until nullptr, processing each visited node.
🎯 Why It Matters: - Saving the successor before overwriting a link prevents accidental loss of access to the remaining nodes. - Deleting a node invalidates every pointer to that node; later dereferencing such pointers causes undefined behavior. - An owning C++ list must release its nodes and define or disable copying to prevent leaks, shallow-copy aliasing, and double deletion. - Unlike arrays, linked lists do not provide constant-time indexed access and often have poorer cache locality.
🧠 Quick Recall: - Empty-list invariant - head == nullptr; the last node of a nonempty list has next == nullptr. - Head insertion and deletion -
More ways to study when you copy this note
Copy this note into your library to unlock focused practice sessions and long-term review.
Answer all questions first, then see feedback at the end — the way real exams work.
Focuses each session on what you got wrong, not what you already know.
Full timed exam with all questions, no pausing, and results at the end. Built for board exam prep.
Part of 🗄️ BS Information Systems — 1st Year
Browse this Review Set →More Computer Engineering notes
See all →More in Data Structures and Algorithms
See all →More from NoteLib
Browse NoteLib's public notes →Copy this note to your library and get the full Study Pack instantly — summary, key concepts, and practice quiz included.