Deallocation using iteration:
void deallocateList(Node *&head) {
Node *cur = head;
while (head != NULL) {
head = head->next;
delete cur;
cur = head;
}
}
Deallocation using recursion:
void deallocateList(Node *&head) {
if (head == NULL) return;
deallocateList(head->next);
delete head
head = NULL;
}
Copying a linked list
We can copy a linked list as follows:
Node *copyList(Node *head) {
if (head == NULL) {
return NULL;
}
Node *newHead = new Node;
newHead->data = head->data;
Node *cur = newHead;
head = head->next;
while (head != NULL) {
cur->next = new Node;
cur = cur->next;
cur->data = head->data;
head = head->next;
}
cur->next = NULL;
return newHead;
}
Recursively:
Node *copyList(Node *head) {
if (head == NULL) {
return NULL;
}
Node *newHead = new Node;
newHead->data = head->data;
newHead->next = copyList(head->next);
return newHead;
}
Merging sorted linked lists
Another example is merging two sorted linked lists into a new sorted linked list, without modifying the original two lists. First, let’s do it iteratively:
Node *mergeLists(Node *head1, Node *head2) {
// Make sure there is at least one list to merge.
if (head1 == NULL && head2 == NULL) return NULL;
// Take care of head first.
Node *head3 = new Node;
Node *cur = head3;
while (head1 != NULL || head2 != NULL) {
if (head1 != NULL && (head2 == NULL || head1->data < head2->data)) {
cur->data = head1->data;
head1 = head1->next;
}
else {
cur->data = head2->data;
head2 = head2->next;
}
if (head1 != NULL || head2 != NULL) {
cur->next = new Node;
cur = cur->next;
}
}
cur->next = NULL;
return head3;
}
Here is a recursive solution:
Node *mergeLists(Node *head1, Node *head2) {
// Make sure there is at least one list to merge.
if (head1 == NULL && head2 == NULL) return NULL;
// Take care of head first.
Node *head3 = new Node;
if (head1 != NULL && (head2 == NULL || head1->data < head2->data)) {
head3->data = head1->data;
head3->next = mergeLists(head1->next, head2);
}
else {
head3->data = head2->data;
head3->next = mergeLists(head1, head2->next);
}
return head3;
}
Linked list variations
Sometimes it is useful for a linked list to be circular. This means that the last node, instead of pointing to NULL, points to the head of the list. In this case, when you traverse the list, you need to check whether you have gone all of the way around.
// Display the data in a circular linked list
if (head != NULL) {
Node *cur = head;
do {
cout << cur->data << endl;
cur = cur->next;
}
while (cur != head && cur != NULL); // Do we need to check for NULL?
}
Another common variation is to use a dummy node at the head of the list. This prevents the need for a special case when you insert a node at the beginning of the list.
Node *head = new Node; // This is the dummy node.
head->next = NULL;
Now, we can insert into a sorted list with simpler code:
void insertNode(Node *head, int data) {
Node *newNode = new Node;
newNode->data = data;
newNode->next = NULL;
// Don’t need to check for (head == NULL)!
// Don’t need to check whether head->data is greater than input data!
// Must have precondition that dummy node exists, though.
Node *cur = head;
while (cur->next != NULL && cur->next->data < newNode->data)
cur = cur->next;
newNode->next = cur->next;
cur->next = newNode;
}
In this case, we never change the value of head, so we can pass head by value rather than by reference. The use of a dummy node also makes deleting nodes simpler.
The last variation is a doubly linked list. In this type of list, each node points to both the previous and the next node in the list:
struct Node {
int data;
Node *prev;
Node *next;
}
This allows you to travel either direction in the list. Also, a node can be deleted, without traversing the list to determine which node precedes it. It is more difficult to insert and delete nodes into a doubly linked list. Here is an example of deleting a node toDelete that has already been found in the list:
if (toDelete->prev == NULL)
head = toDelete->next;
else
toDelete->prev->next = toDelete->next;
if (toDelete->next != NULL)
toDelete->next->prev = toDelete->prev;
delete toDelete;
You can also have circular doubly linked lists, or doubly linked lists with dummy nodes at the head and/or tail of the lists.
Memory
allocation and deallocation (in relation to OOP in C++)
The Array
class -- header file
The
Array class -- .cpp
Using
Array objects -- sample driver
Using
Array objects -- What happens if you don't write a copy constructor?
Why not
just call the assignment operator from copy constructor?