Adding and Removing Nodes

Add at the front: O(1)

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* next;
    Node(int v, Node* n = nullptr) : value(v), next(n) {}
};

void show(Node* head) {
    for (; head; head = head->next) cout << head->value << ' ';
    cout << endl;
}

int main() {
    Node* head = new Node(2, new Node(3));
    head = new Node(1, head);           // new node points at the old head
    show(head);

    // add at the end: walk to the last node first (O(n))
    Node* cur = head;
    while (cur->next) cur = cur->next;
    cur->next = new Node(4);
    show(head);
    return 0;
}

Output

1 2 3 
1 2 3 4 

Remove every node with a value

To remove a node, the node before it skips over it. A dummy node in front means removing the head needs no special case. In C++ you should also delete the removed node to give its memory back:

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* next;
    Node(int v, Node* n = nullptr) : value(v), next(n) {}
};

Node* removeAll(Node* head, int target) {
    Node dummy(0, head);
    Node* prev = &dummy;
    while (prev->next) {
        if (prev->next->value == target) {
            Node* gone = prev->next;
            prev->next = gone->next;    // skip it
            delete gone;                // free its memory
        } else {
            prev = prev->next;
        }
    }
    return dummy.next;
}

int main() {
    Node* head = new Node(7, new Node(1, new Node(7, new Node(2, new Node(7)))));
    head = removeAll(head, 7);
    for (Node* c = head; c; c = c->next) cout << c->value << ' ';
    cout << endl;
    return 0;
}

Output

1 2 

Think of it like this: Leaving a human chain: the person before you lets go of you and grabs the hand of the person after you.

Common mistake: Using cur->next when cur is nullptr crashes the program. Always check before you follow a pointer.