What is the best way to reject duplicates in a sorted doubly linked list

Question

I am trying to make a sorted doubly linked list that doesn't insert duplicates, but I am having trouble finding a way to do this. I looked at posts on how to remove duplicates, but no posts on preventing duplicate insertions.

Here is the code I have to insert and sort without rejecting duplicates. The parameter, dataIn takes values from a predefined Student object list in main (Student s = {{gpa, name}, ..., {gpa, name}}:

void StudentList::insertNode(Student dataIn)
{
    ListNode *newNode; // A new node pointer
    ListNode *pCur; // To traverse the list
    // Allocate a new node and store num there.
    newNode = new ListNode;
    newNode->stu = dataIn;
    newNode->forw = NULL;
    newNode->back = NULL;
    
    //Check if there is node in list
    if(head ->forw == NULL && head->back == NULL){
        head->forw = newNode;
        newNode->back = head;
        newNode->forw = head;
        head->back = newNode;
    }
    else{
        // Initialize pointers
        pCur = head->forw;
        // Find location: skip all nodes whose name is less than dataIn's name
        while (pCur != head && pCur->stu.name < dataIn.name)
        {
            pCur = pCur->forw;
        }
        // Insert the new node between pPre and pCur
        ListNode *pPre = pCur->back; // The previous node
        newNode->back = pPre;
        newNode->forw = pCur;
        pCur->back = newNode;
        pPre->forw = newNode;
    }
    // Update the counter
    count++;
}

Does anyone know a way for rejecting duplicates without deleting? Thanks everyone!

Answer 1

What is the best way to reject duplicates in a sorted doubly linked list?

I suggest delaying the creation of the new ListNode until you know that the new node isn't a duplicate.

Assuming that the ListNode looks like this

struct ListNode {        
    Student stu;
    ListNode *back;
    ListNode *forw;
};

and that you have a head and tail ListNode* that is set to nullptr when the StudentList is empty, then the insertNode function could look like this:

bool StudentList::insertNode(const Student& dataIn) { // return true if node is inserted
    ListNode* prev = nullptr;
    ListNode* pCur = head;

    // search for a good insertion spot
    for(; pCur; prev = pCur, pCur = pCur->forw) {
        if(dataIn.name == pCur->stu.name) return false; // equal, reject
        if(dataIn.name < pCur->stu.name) break;         // found a good spot before pCur
    }

    // delayed creation until here:
    ListNode* newNode = new ListNode{dataIn, prev, pCur};

    // linking        
    if(prev) prev->forw = newNode;
    else head = newNode;
    
    if(pCur) pCur->back = newNode;
    else tail = newNode; // comment this line out if you don't have a "tail"

    ++count;

    return true; // node inserted
}