Home CPSC 340

Linked Lists Continued

Removing a Node

So now we have a Linked List class that we can add data to, and access. What if we want to delete elements from the list? The ease of deleting elements is one of the biggest advantages of a linked list.

How could we add a remove function to the IntList class which removes a particular item?


void remove(int value) {
    // if the list is empty, do nothing
    if (head == NULL) {
        return;

        // if the item to remove is the first one
    } else if (head->data == value) {
        Node* temp = head;
        head = head->next;
        delete temp;

        // else we need to find the item
    } else {
        // keep track of the current and the one before it
        Node* previous = head;
        Node* current = head->next;

        while (current != NULL) {
            // if this item is the one we're looking for
            if (current->data == value) {
                // fix the link before it to point to the next one
                previous->next = current->next;
                // remove it from memory
                delete current;
                break;
            }

            // move on to the next element
            previous = current;
            current = current->next;
        }
    }
}



Adding a Destructor

Because our linked list allocates memory inside of it, we will need a destructor.

How could we add a constructor to our class? Because we will be deleting all of the nodes elsewhere as well, we will put the code to do so in a separate function:


// function which clears all of the nodes from the list
void clear() {
    // delete the head node until there is no head left
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

// the destructor removes all of the nodes that have been allocated
~IntList() {
    clear();
}

Adding a Copy Constructor & Assignment Operator

Because we have a destructor, the Rule of Three says we must also have a copy constructor and assignment operator.

Indeed if we try to copy our IntList objects, it will not work correctly.

How could we add these in?


// copy a new list from another one
IntList(const IntList& other) {
    //start with an empty list
    head = NULL;

    // copy the other ones in
    Node* current = other.head;
    while (current != NULL) {
        addEnd(current->data);
        current = current->next;
    }
}

// assign an existing list the nodes of another one
IntList operator=(const IntList& other) {
    // prevent self-assignment
    if (this == &other) {
        return *this;
    }

    // clear the existing nodes
    clear();

    // copy the other ones in
    Node* current = other.head;
    while (current != NULL) {
        addEnd(current->data);
        current = current->next;
    }

    return *this;
}

Notice that the copy constructor calls a function to add the nodes at the end of the list. If we were to add the nodes at the beginning of the list, it would result in the linked list being reversed when it is copied.

Adding to the end of a linked list is more complicated than adding to the beginning because we have to loop through to find the last node in the list first:


// add a new value to the end
void addEnd(int value) {
    if (head == NULL) {
        head = new Node;
        head->data = value;
        head->next = NULL;
    } else {
        Node* prev = head;
        Node* curr = head->next;
        while (curr != NULL) {
            prev = curr;
            curr = curr->next;
        }
        prev->next = new Node;
        prev->next->data = value;
        prev->next->next = NULL;
    }
}

Linked Lists vs. Arrays

Linked lists and arrays both store data. So how would we decide which one to use to store something in our program?

The choice of which data structure to use has a huge impact on our programs in terms of efficiency. Some operations are much faster with an array and some are much faster with a linked list.

Advantages of Linked Lists:

Advantages of Arrays:

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.