UPI Study › Courses › C++ Programming › Free lessons › Lesson 11.6 Free with a free account
Hand-Crafting Linked Lists
C++ Programming · Chapter 11: Inheritance and PolymorphismSection 11.6 · lesson 83 of 84video coming soon
← How Polymorphism Enables Flexible CodeNext lesson: Capstone: Inheritance, Polymorphism and Memory →
In this lesson
Applied challenge: pointer chains.
- Define a self-referencing node, and represent the empty list
- Insert at the front, the end, and a position
- Traverse, search, delete and release safely
- Compare singly and doubly linked lists, and lists with vectors
Transcript
Everything said in the video, section by section (1,819 words). Read along, or search it.
Opening Question
Which Operation Order Keeps the List
A vector keeps its elements side by side, which makes indexing instant, and inserting near the front expensive. A linked list makes the opposite trade. Each element sits wherever there's room, and carries the address of the next. Building one by hand is the clearest exercise in pointer discipline there is. Every operation is three or four lines, and getting them in the wrong order loses the entire list. So which order is the right one, and why?
Node Definition
A Struct Holding a Pointer to Itself
A node holds an int value, and a pointer to another node. A struct can't contain an instance of itself. That would need infinite space. But it can perfectly well contain a pointer to one. A pointer's size is known regardless of what it points at, so the compiler can lay out node while it's still being defined. The last node's next is nullptr, and that's what marks the end. Nothing else records where the list stops.
Diagram
Three Values Linked From Head
Here's a list of three values: twelve, seven, and thirty-one. Head points at the first node. Each node's next points at the one after, and the last one's next is nullptr. The nodes need not be anywhere near each other in memory. So be careful. Lose head, and every node is unreachable. Lose any next, and everything after it is gone.
List Class
Head, Count, and the Empty List
The list class keeps just two members: a head pointer, and a count. It offers insertion at the front, at the end, and at a position, along with remove, find, print and size. The empty list is head equal to nullptr, and that single fact does more work than it appears to. Every operation has to behave correctly when it's true. Most bugs in hand-written lists are an operation that assumed at least one node existed.
Insert Front
Point Next First, Then Move Head
To insert at the front, make a fresh node and store the value. Point its next at the old first node, and only then move head to the fresh node. Those two assignments must happen in that order. Reversed, head is overwritten before anything records where the old first node was. Every existing node becomes unreachable in one line, and nothing is reported. Notice that the empty case needs no special handling. When head is null, the new node's next becomes null, which is exactly right. An operation that handles the empty case without a branch is usually correctly written.
Insert End
Walking to the Last Node
Inserting at the end makes a fresh node whose next is nullptr. Here the empty case does need its own branch, because the loop would immediately dereference a null pointer. If the list is empty, the new node is the list. Otherwise, walk to the last node, and attach the fresh one there. The walk checks cur's next, not cur itself. You want to stop on the last node so you can attach to it, not step past it into nothing. This operation grows with the length of the list. Keeping a tail pointer would make it instant, at the cost of maintaining it everywhere.
Insert At Position
Link Forward Before Linking Back
Inserting at a position first refuses any position outside zero to count. Position zero reuses insert front, rather than repeating it. Otherwise, walk to the node before the target slot. Then link the fresh node forward to the rest of the list first, and only then link the node before it to the fresh one. That's the general rule for every splice. Attach the new node to the rest of the list, before detaching the rest from what preceded it. Do it the other way, and the tail is orphaned between the two statements.
Traversal
Printing and Finding With One Loop
Printing walks the list: start at head, stop at nullptr, and advance by following next. Find uses exactly the same loop, returning the node if the value matches, or nullptr if it's absent. That loop is the shape of every list traversal you'll ever write. Two rules go with it. Never advance head itself. Use a separate walking pointer, or the list is lost. And check for null before dereferencing. The loop condition does that for you, provided nothing inside the body steps forward as well.
Deletion Diagram
Relink Around the Node, Then Free
Deletion is where the discipline is tested. Three things must happen in order: find the node, relink around it, and only then release it. Before, prev points at the target, which points at after. Step one: set prev's next to the target's next, so prev now points straight at after. The target is now unreachable from the list, but still allocated. Step two: delete the target. Reverse those steps, and you read a freed node, because the address needed to relink lives inside the node being freed.
Remove Code
Remove in Full, Head Case Included
Here's remove in full. An empty list returns false straight away. If the first node holds the value, it has no predecessor, so it gets its own branch. Move head off it first, then delete it. Otherwise, walk until prev's next holds the value, or the list runs out. If it runs out, the value is absent. Then relink around the doomed node, and only then release it.
Common Mistakes
Three Ways Deletion Goes Wrong
There are three deletion faults, in order of frequency. First, freeing before relinking. Deleting the node, then reading its next, reads a field of a node that no longer exists. It often appears to work, because the memory hasn't been reused yet. That is undefined behavior, so the code is shown but never run. Second, forgetting the head case. The first node has no predecessor, so the general code has nothing to relink from. It needs its own branch, which moves head before freeing. Third, losing the tail. Setting prev's next to null, instead of the doomed node's next, removes the node and everything after it, leaking them all. This one is safe to run. Three nodes in, one comes out the other side.
Destructor
Releasing Every Node Individually
Every node was requested individually, so every node must be released individually. The loop needs one extra pointer. Save the next link before freeing the current node, then delete it, then move on. Writing delete cur, then cur equals cur's next, reads the freed node to find out where to go. It's the same fault as deleting before relinking, in a tighter loop. One more responsibility. This class owns memory through a raw pointer, so it must say what happens when it's copied. As written, a copy would hold the same node addresses, and both destructors would try to free them. Making it safe to copy is a separate obligation.
Demo
Using the List Class End to End
Now let's use the class. Insert thirty-one, seven and twelve at the front, and the list reads twelve, seven, thirty-one. Insert forty at the end, and ninety-nine at position two. Find thirty-one succeeds, and find five reports absent. Then remove the first node, the last, and one in the middle, and print what's left. Removing a value that isn't there returns zero for false, and the size is still two.
Test Checklist
Edge Cases Every Submission Must Pass
Test every submission against these. Printing an empty list prints only the end marker, with no crash. Inserting one, then deleting it, leaves the list empty, with head null rather than dangling. Deleting the first node moves head. Deleting the last node leaves the new last node's next as nullptr. And deleting an absent value returns false. Inserting at position zero and at size are both accepted, but size plus one is refused. And build a thousand nodes, then destroy them, in a loop. Memory use should stay flat.
Variation
Doubly Linked Lists and Their Tradeoffs
Adding a second pointer to each node, aimed backward, produces a doubly linked list. It costs two pointers per node, noticeably more when the values are small. In exchange, you can traverse backward directly, and delete a node you already hold immediately, since its predecessor is right there. But each change can touch up to four links, and every one is a chance to make a mistake. Use a doubly linked list when you move both ways, or delete by node rather than by value.
Comparison
Linked List Versus Vector Costs
Here's the honest comparison with a vector. Reaching element n means walking from the front of a list. A vector computes it instantly from the index. Inserting at the front of a list is instant. In a vector, every element shifts. In the middle, a list is instant once you're there, and a vector shifts everything after. At the end, a vector is effectively instant, amortized, and a list must walk unless a tail is kept. A list stores one or two pointers alongside each value, in separately obtained nodes. A vector stores the values alone, in one block. And a full traversal of a list is slower, because nodes are scattered. A vector's elements sit together, and are fetched together.
Verdict
Why a Vector Usually Wins
So which one wins? Use a vector. On real machines, memory and traversal dominate, so heavily that a vector often beats a list even at inserting in the middle. Shifting a contiguous block is something hardware is extremely good at. Chasing scattered pointers is not. Lists earn their place in narrower cases. When you hold the position and must insert or delete there constantly, when elements must never move, or when one insertion must be guaranteed fast. The reason to build one by hand is that the node-and-pointer pattern underlies trees, graphs, and much else.
Assignment
The Tiered Graded Exercise
The graded exercise builds the full list, then extends it by tier. Tier one completes every function, adds clear, and adds positional access that never exposes a node to callers. Tier two reverses the list in place using three pointers, keeps a sorted list with insert sorted, and removes every match. Deleting consecutive matches is the case that catches people. Tier three rewrites the class as doubly linked, with a tail pointer. And it detects a cycle, without modifying the list, and without extra storage proportional to its length.
Marking Guide
How the Exercise Is Graded
Here's the marking guide. Thirty-five percent is for correct linking: every operation leaves the chain intact, with the count matching the nodes present. Twenty-five percent is for boundary cases: the empty list, a single node, the first node, and the last node. Twenty-five percent is for memory discipline: each node released exactly once, and nothing read after being freed. And fifteen percent is for the interface: callers never handle raw nodes, and every operation reports success or failure.
Quick Check
Inserting at Count and Past It
Quick check. The list reads 12, 7, 31. Call insertAt(3, 50), then insertAt(5, 60). What does each call return, and what does the list print? Pause and think. The first is accepted: position 3 equals the count, so 50 goes on the end, and it returns true. Now the count is 4, so position 5 is past the end: refused, false. The list prints 12, 7, 31, 50.
Key Takeaways
Pointer Discipline in Six Rules
To summarize. A node holds a value and a pointer to the next, and nullptr marks the end. Link the new node in, before unlinking the old route. Never advance head. Walk with a separate pointer. Relink, then free. And save next before deleting. In practice, use a vector. But lists are the clearest teacher of pointer discipline.
About C++ Programming at UPI Study
C++ Programming (Computer Science 242) is a self-paced online course of 84 video lessons in 11 chapters, from your first program to decisions, loops, arrays, functions, classes, files, pointers and inheritance. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus Every course with PRO →
Why take it here
Why students take C++ Programming with UPI Study
Where the credit goes
Universities that work with NCCRS
C++ Programming carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Hand-Crafting Linked Lists
Why can a linked list node contain a pointer to its own type but not an object of its own type?
In what order do you insert a node at the front of a singly linked list?
How do you delete a node from a singly linked list without a memory error?
When should I use a linked list instead of a vector in C++?
About the C++ Programming course
How many college credits is C++ Programming?
How much does C++ Programming cost and what is included?
Which universities accept UPI Study credits?
How long does C++ Programming take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in C++ Programming.
84 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →