Ordered Doubly Linked List Insertion

Question

I'm working on a school project right now. It's an ordered(ascending) doubly linked list. I just wrote the Insert operation on it but I feel like the way I wrote it isn't that great.

void OrdListClass::Insert(ItemType item)
{
    if(Find(item))
    {
        //throw DuplicateKeyException;
    }//End Duplicate Key Check
    else
    {
        //Due to Find, currPos points to the node that we're inserting AFTER
        node* newNode = new node;
        newNode->data = item;

        if(currPos == nullptr)
        {
            //We're inserting at the head.
            newNode->prev = nullptr;
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        else if(currPos->next == nullptr)
        {
            //We're inserting at the tail
            newNode->next = nullptr;
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
        else
        {
            //We're inserting in the middle of the list.
            newNode->prev = currPos;
            newNode->next = currPos->next;
            currPos->next->prev = newNode;
            currPos->next = newNode;
        }
        currPos = newNode;
    }//End Not Duplicate Else
}//End Insert

EDIT: Of note.. ItemType is just a typedef for an int.

bool OrdListClass::Find(/*IN*/ItemType searchKey)
{
    //Skip operations if empty.
    if(IsEmpty()) return false;

    currPos = head;
    while(!EndOfList())
    {
        if(currPos->data == searchKey)
        {
            return true;
        }
        else if (currPos->data > searchKey)
        {
            currPos = currPos->prev;
            return false;
        }
        //else continue;
    }
}

Answer 1

I think your Insert function is about as tight as you can make it without getting into strictly-organizational functions to tuck the list details (head, tail) and node details (next, prev) out of sight. Not a big deal for this one function and probably not for the class overall.

If I could make one suggestion, though, it would be that you reconsider having the Find function serve as both a match-finding function (returning true or false accordingly) and a state-modifying function that updates member currPos.

If I saw the definition of Find in the header, I would wonder why it was not a const function since the name and return value give me no reason to think it's modifying the object itself -- surely it just returns true if a match is found and nothing else. Also, since the list is ordered, it would seem that currPos must always be updated before any meaningful modification is performed: it determines where the current insert/delete occurs (not an arbitrary insert/delete like against head or tail) so currPos has no value to insertion/deletion before or after the call and thus no value as a member. So currPos as a member seems like unnecessary temporary storage at best and error-prone storage at worst.

Assuming my assessment of Find and currPos are fair, consider removing member currPos and adding a function to manage the list search without storing the node or the match flag in the object, like so:

node* OrdListClass::FindNode(/*IN*/ItemType searchKey, bool& matchFound) const
{
    matchFound = false;

    //Skip operations if empty.
    if(IsEmpty()) return nullptr;

    node* currPos = head;

    while(currPos != nullptr)
    {
        if(currPos->data == searchKey)
        {
            matchFound = true;
            return currPos;
        }
        else if (currPos->data > searchKey)
        {
            currPos = currPos->prev;
            return currPos;
        }
    }
}

Find then becomes:

bool OrdListClass::Find(/*IN*/ItemType searchKey) const
{
    bool matchFound = false;
    //FindNode is only called to determine if there is an exact match.
    FindNode(searchKey, matchFound);
    return matchFound;
}

And Insert becomes:

void OrdListClass::Insert(ItemType item)
{
    bool matchFound = false;
    node* currPos = FindNode(item, matchFound);

    if (matchFound)
    {
      //Nothing to insert.
      return;
    }

    //currPos points to the node that we're inserting AFTER
    node* newNode = new node;
    newNode->data = item;

    if(currPos == nullptr)
    {
        //We're inserting at the head.
        newNode->prev = nullptr;
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
    else if(currPos->next == nullptr)
    {
        //We're inserting at the tail
        newNode->next = nullptr;
        newNode->prev = tail;
        tail->next = newNode;
        tail = newNode;
    }
    else
    {
        //We're inserting in the middle of the list.
        newNode->prev = currPos;
        newNode->next = currPos->next;
        currPos->next->prev = newNode;
        currPos->next = newNode;
    }
}//End Insert

There are alternative ways to implement FindNode rather than passing a bool reference for the matching flag (e.g., returning something like a NodeSearchResult object that contains the flag and the node together), but the gist is that FindNode is a function that manages the insertion/deletion point without resorting to using a member for temporary storage.

Whether or not you choose to go with something like this, I hope it gives you something to think about. Otherwise, like I said, Insert itself seems fine.

Answer 2

2 questions:

1. What is the expected logic for inserting the first node to an empty list?
2. Is nullptr just a typedef to NULL, or you used the 'dummy node' approach? If it is NULL, you cannot move your currPos there - you should be 'in the list', and check next/prev for null-ness.