Linked List in C++

An elementary linked list implemented in C++

A doubly linked list represents a series of data elements that each point to another successor and a predecessor in the list.  The diagram depicting this structure is below.

For this elementary implementation, I define the following operations to add data elements to the list:

• Append to the end
• Insert "n" after "p"
• Insert "n" before "p"
• Delete

I also provide a few extra functions to navigate and search.

Append

Link* Link::append(Link *n) {
    Link* p = last();
    if (p == nullptr) { return n; }
    if (n == nullptr) { return last(); }

    p -> succ = n;
    n -> pred = p;
    return n;
}

Insert "n" after "p"

Link* Link::insert_after(Link* n) {
    Link* p = this;
    if (n == nullptr) { return last(); }
    if (p == nullptr) { return n; }

    if (p -> succ) {             // if p has a successor
        p -> succ -> pred = n;
        n -> succ = p -> succ;   // p's succesor's predecssor is now n
    }
    n -> pred = p;
    p -> succ = n;
    return n;
}

Insert "n" before "p"

Link* Link::insert_before(Link* n) {
    Link* p = this;
    if (n == nullptr) { return last(); }
    if (p == nullptr) { return n; }

    if (p -> pred) {
        p -> pred -> succ = n;
        n -> pred = p -> pred;
    }
    p -> pred = n;
    n -> succ = p;
    return n;
}

Delete

void Link::erase(Link* n) {
    if (n -> succ) {
        n -> succ -> pred = n -> pred;
    }
    if (n -> pred) {
        n -> pred -> succ = n -> succ;
    }
}

Class Definition

class Link {
    public:
        string value;
        Link(const string& v, Link* p = nullptr, Link* s = nullptr) : 
            value{v}, pred{p}, succ{s} {} ;

        Link* append(Link* n);
        Link* insert_before(Link* n);
        Link* insert_after(Link* n);

        // 
        Link* find(const string& s);
        void erase(Link *n);
        
        // Traversal
        Link* previous() { return pred; }
        Link* next() { return succ; }
        Link* last();

    private:
        Link* pred;
        Link* succ;
};

Find method

Link* Link::find(const string& s) {
    if (value == s) { return this; }
    
    Link* next_link = last();

    while (next_link) {
        if (next_link->value == s) { return next_link; }
        next_link = next_link -> previous();
    }

    return nullptr;
}