An array holds its elements in one unbroken run of memory. That is what makes score[7] instant — the
machine computes an address and goes straight there. It is also what makes an array rigid: its size is fixed
when you define it, and inserting a value in the middle means shifting everything after it along by one.
A linked list gives up the unbroken run. Each value lives in its own separately allocated node, and
each node carries the address of the next one. The nodes can be anywhere in memory; what holds them in
sequence is the chain of pointers, not their position.
What you buy with that is cheap structural change. Inserting a value in the middle of a linked list means
allocating one node and rewriting two pointers — no shifting, no matter how long the list. The list grows
one node at a time, for as long as there is memory. What you give up is instant access by position: to reach
the fifth value you must walk through the first four, because nothing tells you where the fifth node is
except the fourth node.
This lab is built entirely on Lab 7. Every node comes from new, every link is a pointer, and every node
must eventually be released with delete.
A node holds a value and a pointer to the node after it:
class ListNode
{
public:
double value;
ListNode *next;
};
Read that second member carefully: a ListNode contains a pointer to a ListNode. That is legal because
a pointer is just an address — the compiler knows how big a pointer is without yet knowing how big a
ListNode is. A node containing an actual ListNode would be impossible, since its size would have to
contain itself.
Two pointers describe the whole structure. head holds the address of the first node, and is how the
program finds the list at all. The last node’s next is nullptr, which is what marks the end. An
empty list is simply head == nullptr.
Setting value and next by hand on every node gets tedious fast, so give ListNode a constructor with a
default argument for the link:
class ListNode
{
public:
double value;
ListNode *next;
ListNode(double value1, ListNode *next1 = nullptr)
{
value = value1;
next = next1;
}
};
Now new ListNode(13.5) makes an end-of-list node, and new ListNode(12.5, head) makes a node that points
at whatever head pointed at before.
Write nodes.cpp containing the ListNode class above. In main, build a three-node list holding
12.5, 13.5, 14.5 — allocating each node with new and linking them yourself — then print all three
values by following the pointers from head:
cout << head->value << " "
<< head->next->value << " "
<< head->next->next->value << endl;
You will not write code like that again; the point is to see that the chain really is just next after
next, and to notice how unusable it becomes past three nodes.
By hand: 12.5 13.5 14.5
Still in nodes.cpp, read double values from the user until the input fails, putting each one into a new
node at the front of the list:
ListNode *numberList = nullptr;
double number;
while (cin >> number)
{
numberList = new ListNode(number, numberList);
}
That single line is worth staring at. The new node is given the old numberList as its next, and then
numberList is pointed at the new node — so the list grows at the head, and no traversal is needed. It also
works on the first pass, when numberList is nullptr: the first node’s next becomes nullptr, which is
exactly right for the only node in a list.
Then traverse the list and print it. Traversal is the pattern you will write in every remaining task:
ListNode *ptr = numberList;
while (ptr != nullptr)
{
cout << ptr->value << " ";
ptr = ptr->next;
}
ptr is a second pointer walking the list. Never advance head itself — move head and you have lost the
front of the list and every node in it.
$ ./nodes
By hand: 12.5 13.5 14.5
Enter numbers (any letter to stop): 2.5 7.9 12.6 x
List: 12.6 7.9 2.5
Note the order. Explain in a comment why the list comes out reversed.
nodes.cpp leaves head exposed in main, which means any line of code can scramble the list, and nothing
cleans up the nodes when the program ends. The rest of this lab wraps the list in a class, the way Lab 5
wrapped a time.
Split it across files the way you did in Lab 5 — NumberList.h, NumberList.cpp, and a main.cpp client:
#ifndef NUMBERLIST_H
#define NUMBERLIST_H
class NumberList
{
protected:
class ListNode
{
public:
double value;
ListNode *next;
ListNode(double value1, ListNode *next1 = nullptr)
{
value = value1;
next = next1;
}
};
ListNode *head;
public:
NumberList();
~NumberList();
void add(double number);
void addSorted(double number);
void remove(double number);
void displayList() const;
};
#endif
Two things here are new. ListNode is declared inside NumberList, because nothing outside the list has
any business knowing that nodes exist — it is an implementation detail, and nesting it says so. And the
access specifier is protected rather than private. For this lab the two behave identically; protected
additionally lets a derived class reach these members, which is what Lab 12 will need when it extends this
very class.
add, and displayListWrite the constructor (one line: an empty list has head == nullptr), then:
void add(double number); // append to the END of the list
void displayList() const; // print every value, space separated
add appends, which means it has two cases. If the list is empty, the new node is the list. Otherwise walk
to the last node — the one whose next is nullptr — and hang the new node off it:
ListNode *nodePtr = head;
while (nodePtr->next != nullptr)
{
nodePtr = nodePtr->next;
}
nodePtr->next = new ListNode(number);
The loop condition is nodePtr->next != nullptr, not nodePtr != nullptr. You want to stop on the last
node, not past it — run off the end and you will dereference nullptr and crash.
displayList is the traversal from Task B, and it is const because printing changes nothing.
A NumberList owns every node it allocated, so when a list goes out of scope those nodes must be released.
Write the destructor: walk the list, deleting as you go.
The order of the two steps inside the loop is the whole exercise:
ListNode *nodePtr = head;
while (nodePtr != nullptr)
{
ListNode *garbage = nodePtr;
nodePtr = nodePtr->next; // move on first
delete garbage; // then delete
}
Delete the node before reading its next and you are reading memory you have just given away. Write it the
wrong way round deliberately, build with the address sanitizer, and watch it caught:
$ g++ -fsanitize=address -g main.cpp NumberList.cpp -o numbers
$ ./numbers
==...==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000098
Then fix it, and run the same build again. A correct destructor prints nothing extra; omit the destructor
entirely and the same tool reports 96 byte(s) leaked in 6 allocation(s). Try all three states — the bug,
the leak, and the correct version — and note in a comment what each one printed.
This is why destructors exist. In Lab 7 you had to remember to call deleteParticle by hand; here the
cleanup happens because the object went out of scope, whether you remembered or not.
void remove(double number);
Delete the first node holding number, and do nothing at all if the list is empty or the value is not
present. There are three situations, and the first node is genuinely different from the rest:
head itself must be moved on beforenodePtr lands on the target,previousNodePtr is the node before it, and that is the one whose next has to be rewritten.Test all of it from main.cpp: remove a middle value, remove a value that is not in the list, remove the
first value, and remove from a list that is already empty. None of those should crash.
$ ./numbers
Initial: 2.5 7.9 12.6
After remove 7.9: 2.5 12.6
After remove 99.9:2.5 12.6
After remove 2.5: 12.6
void addSorted(double number);
Insert so that the list stays in ascending order. Two cases again, and they are the same shape as remove:
head = new ListNode(number, head); does the whole job in one line.nodePtr is the first node whose valuepreviousNodePtr->next = new ListNode(number, nodePtr);
Notice that the walking loop must stop for two different reasons — finding the insertion point, or running
off the end of the list — so its condition tests both. When it stops because nodePtr is nullptr, the
splice above still works: the new node’s next becomes nullptr and it lands at the end.
Test by adding values deliberately out of order, including one that belongs first and one that belongs last.
Sorted: 1 2.5 7.9 10.5 12.6
Looking ahead. The textbook builds the sorted list as a separate class that inherits from
NumberList, overridingadd. That is section 11.12, which you meet in Lab 12 — and it is whyheadis
protectedhere rather than private. For now a second member function does the same work.
void reverse();
Reverse the list in place — no new nodes, no deleting, no second list. Only the next pointers and
head change.
The trick is that the moment you overwrite a node’s next, you have destroyed your only way forward. So you
need three pointers in play at once: the node you are working on, the one behind it that its next should
now point to, and the one ahead that you saved before overwriting. Work out the order on paper, with a
three-node list, before writing any code.
When it works, a list built by add in the order 1, 2.5, 7.9, 10.5, 12.6 prints as:
Reversed: 12.6 10.5 7.9 2.5 1
Run it under the address sanitizer too. A correct reverse neither leaks nor loses a node — and if you drop
one, the destructor will no longer find it, and the leak report will tell you how many you lost.
Submit all four source files:
nodes.cpp NumberList.h NumberList.cpp main.cpp
Do not submit compiled executables. Each file should start with a comment containing your name and a short
description, for example:
/*
Author: your name
Course: CSCI-135
Instructor: their name
Assignment: Lab 8
Here, briefly, at least in one or a few sentences
describe what this file contains.
*/