There are two main ways of representing lists of things. One is arrays. The other is linked lists. We will briefly define what a linked list is and then go over ways of working with linked lists.
Before we go further, let's introduce a way of describing a list of things more general than arrays or linked lists. We simply enclose the list of things in a pair of parentheses and separate each thing with a space. For example, (1 2 3) is the list with 1 as its first element, 2 as its second, and 3 as its third. (17 76) is the list with 17 as its first element and 76 as its second. () is a special list, the empty list. It has no elements.
A linked list is built out of nodes. A node is a structure that holds a value and a link to another node. The first element of the list is the value of the first node. The first node in the list holds a link to the second node. The second node has a link to the third. And so on. The last link in a linked list is given a special value so that we can recognize it. In C++, this special value is NULL.
Here is the list (1 2 3) as a linked list:
[1|-]-> [2|-]-> [3|NULL]
Throughout this page, we will be working with lists of ints. We will use the following struct to represent our nodes:
struct Node {
//The data for this node.
int data;
//A link to the next node in the list,
//NULL if there isn't one.
Node* link;
};
A linked list is a sequence of Nodes ending with NULL. We refer to a linked list by a pointer to its first element. The empty list is represented by a NULL pointer. (The constant NULL is defined in the header "cstdlib".)
Node* list1 = NULL; //The empty list, (). Node* list2 = new Node; list2->data = 2; list2->link = NULL; //list2 is the list (2). //Note that list2's link is also a list -- the empty list. Node* list3 = new Node; list3->data = 1; list3->link = list2; //list3 is the list (1 2). // //The link of a Node is itself a list. //The link of list3 is list2. //The link of list2 is the empty list.Notice that we have repeated some code. Each time we create a Node with new, we set the new node's data and its link. To avoid writing the same thing over and over again, let's write a function that creates a new Node, sets its data to a given value, and sets its link. Very often, we will want the link to be NULL so let's make NULL the default value for it:
//Pre: If next is given, it is a valid linked list.
//Post: Returns a new Node with its data equal to value and
//its link equal to next or NULL if next isn't given. The
//caller is responsible for deleting the memory of the new Node.
Node* createNode(int value, Node* next = NULL)
{
Node* newNode = new Node;
newNode->data = value;
newNode->link = next;
return newNode;
}
Notice that the return value of createNode is a list.
Using createNode, we can rewrite the sample code above as:
Node* list1 = NULL; //The empty list, (). Node* list2 = createNode(2); //list2 is the list (2). //Note that list2's link is also a list -- the empty list. Node* list3 = createNode(1, list2); //list3 is the list (1 2). // //The link of a Node is itself a list. //The link of list3 is list2. //The link of list2 is the empty list.
There are two main patterns for processing the elements of a list. The first is to iterate over the elements of the list using a loop.
Node* head;
//...
for (Node* current = head; current != NULL;
current = current->link) {
//Do something with current
}
Note that this is basically equivalent to:
Node* current = head;
while (current != NULL) {
//Do something with current
current = current->link;
}
The above pieces of code embody these steps:
//Pre: out is not errored and head is a valid linked list.
//Post: head has been printed to out. For example, if head
//is the list (1 2 3), (1 2 3) is printed on out.
//If head is NULL, the empty list, () is printed.
void printList1(Node* head, ostream& out)
{
out << "(";
for (Node* current = head; current != NULL; current = current->link) {
if (current != head) {
out << " ";
}
out << current->data;
}
out << ")";
}
Here is a function to compute the sum of a list of numbers. (We define the sum of the empty list as 0.):
int sum1(Node* head)
{
int result = 0;
for (Node* current = head; current != NULL; current = current->link) {
result += current->data;
}
return result;
}
for (Node* current = head; current != NULL; current = current->link)What is the purpose of current != NULL?
The other major method for processing a list is to recurse down the list.
Recall that a recursive function is a function that calls itself. Many problems can be solved very naturally using a recursive function. Probably the most famous example is computing the factorial. A recursive implementation follows directly from the definition of factorial.
Recursive functions work well with lists because the tail of a non-empty list is a list; a list is a recursive data structure. (The empty list has no tail. Recall that the tail of a list head is head->link.)
... aFunction(Node* aList, ...)
{
if (aList == NULL) {
//...
//Do the default action. This is usually
//to return a default value.
}
else {
//Recurse on the rest of the list.
... aFunction(aList->link, ...);
}
}
aFunction takes a linked list as its argument. Step 3 works because the link of a node is also a list.
Here is a recursive function that computes the sum of a list of numbers:
//Post: Returns the sum of the numbers in the list head.
//Returns 0 if head is the empty list.
int sum2(Node* head)
{
if (head == NULL) {
return 0;
}
else {
return head->data + sum2(head->link);
}
}
How do we compute the sum recursively?
int length(Node* head)
{
if (head == NULL) {
return 0;
//The empty list has length 0
}
else {
return 1 + length(head->link);
//The list head->link has one less element
//than the list head does.
}
}The function length doesn't quite fit our pattern:
//Pre: head is a valid linked list.
//Post: Returns a deep copy of head.
Node* copyList(Node* head)
{
if (head == NULL) {
return NULL;
}
else {
Node* copy = new Node;
copy->data = head->data;
copy->link = copyList(head->link);
return copy;
}
}
Here is a recursive function that creates a new list by multiplying each element of the given list by a given constant://Pre: head is a valid linked list.
//Post: Returns a copy of head with each element multiplied by m.
Node* scaleList(Node* head, int m)
{
if (head == NULL) {
return NULL;
}
else {
Node* scaled = new Node;
scaled->data = m * head->data;
scaled->link = scaleList(head->link, m);
return scaled;
}
}
What's the general pattern here for building up a new linked list recursively?
//Pre: head is a valid linked list.
//Post: Returns a deep copy of head.
Node* copyList(Node* head)
{
if (head == NULL) {
return NULL;
}
else {
return createNode(head->data, copyList(head->link));
}
}
Here is a recursive function that creates a list of numbers from the given number down to zero (inclusive):Node* countDown(int number) {
if (number < 0) {
return NULL;
}
else {
return createNode(number, countDown(number - 1));
}
}
The code for countDown follows the pattern we laid out above:
1. Implement a function countUp that uses recursion to count up from 0 to a given number. For example, countUp(3) is the list (0 1 2 3) and countUp(2) is the list (0 1 2). If the given number is less than 0, countUp should return NULL, the empty list. For example, countUp(-1000) is the empty list. Hint: Have countUp call a recursive function that takes a second parameter -- a variable to hold the current count.
2. Implement a recursive function collectMatches that copies only the elements of a list that equal a given value. For example, if x is the list (2 1 3 2), collectMatches(x, 2) is the list (2 2) and collectMatches(x, 1) is the list (1). If no elements match, return the empty list, NULL. For example, collectMatches(x, 5) is the empty list.
3. Implement a function readList that uses recursion to read a list in the format we've described from a given istream. For example, if you call readList(cin) and the user enters "(1 2)" your function should return the list (1 2). If the user enters "()", readList() should return the empty list, NULL. Hint: Have readList read just the opening parenthesis, '('. Implement a recursive function to do the rest of the work.
//An iterative implementation of list copy.
//Pre: head is a valid linked list.
//Post: Returns a deep copy of head.
Node* copyList2(Node* head) {
Node* result = NULL;
Node* last;
for (Node* current = head; current != NULL; current = current->link) {
Node* copy = createNode(current->data);
if (result == NULL) {
result = copy;
last = result;
}
else {
last->link = copy;
last = copy;
}
}
return result;
}
//An iterative implementation of scaling a list's elements.
//Pre: head is a valid linked list.
//Post: Returns a copy of head with each element multiplied by m.
Node* scaleList2(Node* head, int m)
{
Node* result = NULL;
Node* last;
for (Node* current = head; current != NULL; current = current->link) {
Node* scaled = createNode(m * current->data);
if (result == NULL) {
result = scaled;
last = result;
}
else {
last->link = scaled;
last = scaled;
}
}
return result;
}
//An iterative implementation of count down.
Node* countDown2(int number) {
Node* result = NULL;
Node* last;
for (int n = number; n >= 0; n--) {
Node* next = createNode(n);
if (result == NULL) {
result = next;
last = result;
}
else {
last->link = next;
last = next;
}
}
return result;
}
When building up a list iteratively:
Send your comments or questions on this page to dfaden@gmail.com.