Now that we have pointers to memory locations, we can implement an ordered list using linked memory locations. A linked list is created using nodes that consist of one item of data and a pointer to the next node in the list. For example, a linked list of integers could use nodes of the following type:
struct Node {
int data;
Node *next;
};
Nodes should be allocated dynamically (using “new”). Why? The reason is that if they are allocated statically (as local Node variables), they will be deallocated when leaving the function in which they are defined, which is usually undesirable. Here is an example:
Node someFunction()
{
Node firstNode;
Node secondNode;
firstNode.next = &secondNode;
secondNode.next = NULL;
return firstNode;
}
This will produce incorrect results, since secondNode will be deallocated when someFunction is complete. The next pointer in the return value will thus point to a memory location that has been deallocated.
The following code would generate a simple linked list:
Node *head = NULL; // The pointer to the 1st element of the list is called the head.
head = new Node;
head->data = 1;
head->next = NULL; // The last node must always have a NULL pointer.
The list generated above has only one item. We can add another like this:
head->next = new Node;
head->next->data = 2;
head->next->next = NULL;
Nodes can also be inserted at the beginning of the list:
Node *n = new Node;
n->data = 3;
n->next = head;
head = n;
We can deallocate the nodes using:
n = head->next;
delete head; // OK, because we still have a pointer to the second node.
delete n->next; // deallocates third node
delete n; // deallocates second node
For larger lists, we need to use iteration or recursion to traverse the list to find, add, or remove elements. To print out the items in a list, we could use the following code fragment:
Node *cur = head;
while (cur != NULL) {
cout << cur->data << endl;
cur = cur -> next;
}
This can be written more succinctly (but not necessarily better) as:
for (Node *cur = head; cur != NULL; cur = cur->next)
cout << cur->data << endl;
We could also perform this operation using recursion:
void printList(Node *list) {
if (list == NULL) return;
cout << list->data << endl;
printList(list->next);
}
We can insert an item into a list at the beginning, at the end, or in the middle. At the beginning is the easiest. Let’s say that we want to insert a node with data 0 at the beginning of a list that is pointed to by head, all we have to do is:
Node *n = new Node;
n->data = 0;
n->next = head;
head = n;
To insert a node at the end, we have to traverse the list first.
Node *n = new Node;
n->data = 23;
n->next = NULL;
if (head == NULL) // Is it necessary to check for this case? Yes!
head = n;
else {
Node *cur = head;
while (cur->next != NULL) cur = cur->next;
cur->next = n;
}
Note that if we wrote this as a function, instead of a code fragment we could not pass head by value. If head is passed in as a Node * parameter, then changing head inside the function will not result in a change outside of the function! This same code will work if the function header is:
void insertNode(Node *&head, int value) // Pass head by reference
Some implementations of linked lists maintain a pointer to the tail of the list in addition to a pointer to the head of the list, to make it easier to insert a node at the end of the list.
Inserting into the middle of a list is the trickiest. Let’s say that we want to keep the list in sorted order. We could use the following code:
// Insert node in sorted order.
// Precondition: list must be sorted into non-descending order.
void insertNodeSorted(Node *&head, int data) {
Node *n = new Node;
n->data = data;
n->next = NULL;
if (head == NULL || data < head->data) {
n->next = head;
head = n;
} else {
Node *cur = head;
while (cur->next != NULL && cur->next->data < n->data)
cur = cur->next;
n->next = cur->next;
cur->next = n;
}
}
Many linked listed functions/methods can be written in a simpler fashion using recursion. Consider the above function to insert a number into a sorted list. The recursive version is considerably shorter:
// Insert node in sorted order.
// Precondition: list must be sorted into non-descending order.
void insertNodeSorted(Node *&head, int data) {
if (head == NULL || data < head->data) {
Node *n = new Node;
n->data = data;
n->next = head;
head = n;
}
else insert(head->next, data);
}
Deleting from a linked list
Now let’s delete a node from a linked list. We will specify the node to delete using the data value:
// Delete first node containing “data.” Return false, if no node with this data is in the list.
bool deleteNode(Node *&head, int data) {
if (head == NULL) return false;
if (head->data == data) {
Node *tmp = head;
head = head->next;
delete tmp;
return true;
}
Node *cur = head;
while (cur->next != NULL) {
if (cur->next->data == data) {
Node *tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
return true;
}
cur = cur->next;
}
return false;
}
Recursively:
bool deleteNode(Node *&head, int data) {
if (head == NULL) return false;
if (head->data == data) {
Node *tmp = head;
head = head->next;
delete tmp;
return true;
}
return deleteNode(head->next, data);
}
Carrano, 6th Edition Chapter 4: Exercises: All problems.