Linked List crashing during runtime

[kingkush]

When I use the insert function the first element seems to e inserted fine but i get a bad exc bad access error. I've tried to debug but I cant seem to locate the error or perhaps I'm missing it.
Insert Function:

    SortedLinkedList() { head = nullptr; }
    void insert(T x)
    {
        Node<T>* previousNode = nullptr;
        Node<T>* newNode = new Node<T>(x);
        if (head == nullptr)
        {
            head = newNode;
        }
        else
        {
            Node<T>* cur = head;
            while (cur != nullptr || cur->getValue() > cur->getNext()->getValue())
            {
                previousNode = cur;
                cur = cur->getNext();
            }
            if(previousNode == nullptr)
            {
                head = cur;
                cur = cur->getNext();
            }
            else
            {
                newNode = previousNode;//->getNext();
                //cur = newNode->getNext();
            }
        }
        
    }

I can post the print function but i believe the actual error is in the insert function.

[kbw]

It looks like you're maintaining a sorted list, sorted in ascending order. So the loop must check the new value (x or newNode->getValue()). But you're using cur->getNext()->getValue() instead.

Assuming you've fixed that, in the check if(previousNode == nullptr), you are dealing with the case when the list is not empty and you want to insert at the front. So:
1. Fixup the next pointer on the new node with: newNode->next = head
2. The new node is now the head of the list. head = newNode

If previousNode is not null, you need to insert newNode at cur.

[kingkush]

Yes, its a sorted linked list. Thank you for your help! It appears i missed a setNext() function so i ended up attempting to set everything backwards. But I've attempted to implement what you've said. Thankfully it stopped giving me the error but now it appears to hang at what appears to be the same spot as the previous error.

SortedLinkedList() { head = nullptr; }
    void insert(T x)
    {
        Node<T>* previousNode = nullptr;
        Node<T>* newNode = new Node<T>(x);
        if (head == nullptr)
        {
            head = newNode;
        }
        else
        {
            Node<T>* cur = head;
            while (cur != nullptr || cur->getValue() > newNode->getValue())
            {
                if (cur->getNext() != nullptr)
                {
                    previousNode = cur;
                    cur = cur->getNext();
                }
                //previousNode = cur;
            }
            if(previousNode == nullptr)
            {
                head = newNode;
                newNode->setNext(head);
                //head = newNode;
                //cur = newNode->getNext();
                //newNode->next = cur;
                //cur = cur->getNext();
            }
            else
            {
                //newNode = previousNode;//->getNext();
                previousNode->setNext(newNode);
                newNode->setNext(cur);
            }
        }
        
    }

[kbw]

I think one way is like this:

void insert(T x)
{
    Node<T>* node = new Node<T>(x);

    // an empty list
    if (!head)
    {
        head = node;
        return;
    }

    // linear search for insertion point
    Node<T>* prev = nullptr;
    Node<T>* curr = head;
    while ( (curr) && (node->getData() < curr->getData()) )
    {
        prev = curr;
        curr = curr->getNext();
    }

    // insert at head
    if (!prev)
    {
        node->setNext( head->getNext() );
        head = node;
        return;
    }

    // middle or end
    node->setNext( prev->getNext() );  // will be null at the end, but that's ok
    prev->setNext( node );
}

[kingkush]

Ohhh I see. That makes more sense. Thanks for the example!