I am trying to build a linked-list in C++ from scratch. Consider the following commented class declaration.
/*
Linked list goes from smallest to largest
*/
class List
{
public:
List():head(0), tail(0), theCount(0) {}
virtual ~List() {};
void insert(int value);
bool is_present(int value) const;
bool is_empty() const { return head == 0; }
void showAll();
int count() const {return theCount;}
private:
class ListCell
{
public:
ListCell(int value, ListCell* cell = 0):val(value), next(cell) {}
int val;
ListCell* next;
};
ListCell* head;
ListCell* tail;
int theCount;
};
Once we create a List instance, we set the Head and Tail to the null pointers. To add values to the head, tail, and middle elements, I implemented the insert method.
insert:
void List::insert(int value) {
theCount++;
if (!head) {
/*
first insert sets the head and points to tail which is a nullPtr.
*/
head = new ListCell(value, 0);
//cout << "head is after initalization is " << head << endl;
return;
}
if (!tail) {
/*
if tail is a nullptr, we set it to be the next node after head.
*/
if (value > head->val) {
/*
Value larger = therefore it should be the tail
*/
tail = new ListCell(value, 0);
head->next = tail;
return;
}
else {
/*
Value smaller, therefore, we swap.
*/
tail = new ListCell(head->val, 0);
head->next = tail;
return;
}
}
ListCell* previousNode = head;
// the major problem, please advise me on the loop.
for (ListCell* nodePtr = head; nodePtr->next; nodePtr++) {
ListCell* next = nodePtr->next; // for convience
if (next == tail) {
if (value > next->val) {
// if the value is the largest in the list.
int oldVal = tail->val;
tail->val = value;
next = new ListCell(oldVal, tail);
previousNode = nodePtr;
break;
}
else {
// if the value is just before the tail.
next = new ListCell(value, tail);
previousNode = nodePtr;
break;
}
}
if (value < nodePtr->val) {
/*
if value is less than the node's value, then we create a nodePtr
*/
previousNode->next = new ListCell(value, nodePtr);
previousNode = nodePtr;
break;
}
previousNode = nodePtr;
}
}
However, I am getting unexpected behavior when I try to showAll in my main function.
int main() {
List mainList;
mainList.insert(10);
mainList.insert(12);
mainList.insert(15);
mainList.insert(11);
mainList.showAll(); // shows undefined values. probably indirecting empty pointers
return 0;
}
I have a feeling that it's the nodePtr++ that's causing problems because I am not used to pointer arithmetic.
There are several issues, including the following:
In the !tail case, in the else block, a second node is created with the same value as was already present in the head node, and the given value is not used. So you'll not have inserted value, but have duplicated the first node.
In the main loop, nodePtr++ is wrong. You need nodePtr = nodePtr->next.
At several of the cases, you assign the new node to next. But this doesn't update the next member of the previous node. For that you really need to assign to previousNode->next and not just to next. You did this right in one case -- the last one -- but wrong in two other cases.
In the else block of the value > next->val case, there are still two possibilities: either value > nodePtr->val is true or it is not. But you don't check this, and deal with both cases in the same way. If it is not true, then the second argument of the ListNode constructor should be nodePtr, not tail. And if it is true, the assignment should be made to nodePtr->next and to previousNode->next otherwise.
Not a problem, but doing previousNode = nodePtr; just before the break is useless.
When the first node is added to the list, tail is left as nullptr, which the rest of your code seems to expect. But this is strange, since by the meaning of tail it should reference the last node of the list, even if there is only one node.
Even though fixing the above points will improve the behaviour of the code, you have over-complicated things. You've identified six places where to create a ListNode and insert it in some way into the list. This is too much. There really should be only two or three cases to deal separately with.
Here is what your code could look like when we reduce the number of different cases, and deal with the other points mentioned above:
void List::insert(int value) {
theCount++;
if (!head || value <= head->val) {
head = new ListCell(value, head);
if (!tail) tail = head;
return;
}
ListCell* previousNode = head;
while (previousNode->next && value > previousNode->next->val) {
previousNode = previousNode->next;
}
previousNode->next = new ListCell(value, previousNode->next);
if (tail->next) tail = tail->next;
}