Circular Doubly Linked list with header node

Question

I am supposed to implement a Circular Doubly Linked list with header node in C++.

My professor gave me this algorithm but i can't understand the use of it.

Where and how should i use precede and follow and out?

Inside precede there is a 'P' which i dont understand where it came from, same goes for r in the follow method, and p and r in out method but i figured those might be just a new E2* so i created this

class E2 {

public:
    E2* prev;
    E2* next;
    int key;

    E2() {
        prev = this;
        next = this;


    };


};

void precede(E2* q, E2* r) {

    //insert (*q) before (*r)

    E2* p = new E2();
    p = r->prev;
    q->prev = p;
    q->next = r;
    p->next = r->prev = q;



}

void follow(E2* p, E2* q) {

    E2* r = new E2();

    r = p->next;
    q->prev = p;
    q->next = r;
    p->next = r->prev = q;


}

void out(E2* q) {

    E2* r = new E2();
    E2* p = new E2();

    p = q->prev;
    r = q->next;
    p->next = r;
    r->prev = p;
    q->prev = q->next = this;
}

In the out method, the 'this' gives me an error which says: 'this' may only be used inside a nonstatic member function

E2* p = new E2(); p = r->prev; here you lose pointer to just allocated node. — fas
The more common names for these functions are "precede" == "push front" and "follow" == "push back". As answered below, p is just a temp variable, (not a node that is allocated), and is assigned as shown in the function descriptions. — rcgldr

lil_noob lil_noob · Accepted Answer · 2020-04-21T17:46:24

In precede method:
p is a temporary variable. It is used to name whatever node is before R. Imagine a doubly linked list containing 2 nodes, A and R. The precede method will insert a node Q before R. The steps followed are:

Mark the node preceding R as p. Thus A is marked as p. Now we shall insert Q between p and R.
Make p as the previous of Q and R as the next node of Q. The next of p is still R. Similarly, the previous of R is still p. We change that in the next step.
Mark Q as next of p and previous of R.

You can use the same logic to understand the follow function.

In the remove method, p and r are the previous and next nodes of q. Here we need to create a double link between them (i.e mark r as next of p and p as previous of r). This will delete the node q.

Hope this helps.

Circular Doubly Linked list with header node

1 Answers