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;
 }
}

• user1201210: Could you explain a bit more about the Find function? Is it used elsewhere in the class? Is it public?
• JDiPierro: It is public. It'll return true if the item is found in the list, and it makes currPos point to the node that the item is in. If the item is NOT found in the list, it returns false, and currPos points to the node in front of where it should be inserted. Example in case it's not clear: List of:{[7][9]} Find(8) would return false and currPos would be pointing at the [7] node, so if find was called via Insert(8); it will make the list {[7][8][9]}. I put the source for Find in the OP.
• asveikau: I agree with @tenterhook's answer in that it's weird to have Find implictly update some currPos member and have Insert depend on this behavior. It'd be much better to have the lookup function return a node more explicitly, through a return value or out parameter.

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.

• Corbin: nullptr is a C++11 feature: en.wikipedia.org/wiki/C%2B%2B11#Null_pointer_constant (though he could have aliased it to NULL I suppose... >.<)