Sorting Linked List Nodes in order

[MorrowindFan664]

Write your question here.
I'm trying to sort these nodes in order, but the code below seems to be resulting in an infinite loop and I can't seem to find the issue

 1: // File:  2170_6_8d.cc
2: //
3: // This is the implementation file for the method that inserts an item in
4: // sorted order into a list for a ListClass object.
5: 
6: #include "inlab6.h"
7: #include "structs.h"
8: 
9: #include <iostream>
10: #include <fstream>
11: #include <stdlib.h>
12: using namespace std;
13: 
14: // This function appends the record 'newData' into the sorted position of the linked list.
15: // If the list is empty, the new node is the new head of the list.
16: void ListClass::insertInOrder(RecordType newData)
17: //		INOUT	IN
18: {
19: 	NodePtrType newNode, prev,current;//pointers to the new node and for
20: 										//traversing the list
21: 
22: 	// Create a new node to hold the record. Be sure to put
23:      // the data from newData into the newNode.
24: 	
25: newNode->data = newData;
26: 
27: 	
28: 
29: 
30: 	//The following code should do the following:
31: 	//if (expression to check if the list is empty)
32: 	//{
33: 	//	code to make the new node the head of the list
34: 	//}
35: 
36: 	
37: 	if (head==NULL)
38: 	{
39: 		newNode->next = head;
40: 		head = newNode; 
41: 	}
42: 	
43: 
44: 	//The following code should do the following:
45: 	//else if (expression to check if the new acctNum is less than the head accNum)
46: 	//{
47: 	//	code to make the new node the head of the list
48: 	//}
49: 
50: 
51: 	
52: 	else if (newNode->data.acctNum < head->data.acctNum)
53: 	{
54: 		newNode->next=head;
55: 		head=newNode;
56: 	}
57: 	
58: 	else
59: 	{
60: 		// put the new node where it belongs.
61: 	current = head;
62: prev = NULL;
63: while(current->next != NULL && current->data.acctNum < newNode->data.acctNum)
64: 		{
65: 			current = current->next;
66: 		}	
67: 
68: 	//Replace this with the code necessary to insert the new node into the list
69: 
70: 	newNode->next = current->next;
71: current->next =newNode;
72: 	
73: 	}
74: }//end of insertInOrder function
75:

[MorrowindFan664]

// inlab6.cc
//
// This is the implementation file for the ListClass object. It contains the
// constructor and destructor

#include "inlab6.h"
#include "structs.h"

#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;

//This is the constructor for the ListClass object
ListClass::ListClass()
{
head = NULL;
}//end of constructor

//This is the destructor for the ListClass object
ListClass::~ListClass()
{
NodePtrType q = head;
while (q != NULL)
{
head = head->next;
q->next = NULL;
delete q;
q=head;
}
}//end of destructor

[MorrowindFan664]

//FILE: inlab6.h
#ifndef LIST_CLASS_H
#define LIST_CLASS_H

struct Record;
typedef Record RecordType;
struct Node;
typedef Node* NodePtrType;
typedef Node NodeType;

class ListClass
{
public:
//constructor
ListClass();

//destructor
~ListClass();

//insertion operations for the linked list
void insertAtEnd(RecordType);

void insertAtHead(RecordType);

void insertInMiddle(RecordType, int);

void insertInOrder(RecordType);

//function to print out records in the list
void printList();

//function to count the number of items in a list
int countItems();

//deletion operations for the linked list
void deleteAtHead();

void deleteAtEnd();

void deleteIthNode(int);

void deleteItem(RecordType);
private:
NodePtrType head; //points to beginning of the list
};
#endif

[MorrowindFan664]

//This is the structure of the records that will be stored in the list.
struct Record
{
int acctNum;
float balance;
};

//This is the structure of one node in the linked list.
struct Node
{
RecordType data;
NodePtrType next;
};

[keskiverto]

NodePtrType newNode, prev,current; //pointers to the new node and for
				   //traversing the list
// Create a new node to hold the record. Be sure to put
// the data from newData into the newNode.

newNode->data = newData;

If newNode is a pointer, then what does it point to?

Looks like you dereference an uninitialized pointer. That is undefined behaviour.

current = head;
prev = NULL;
while ( current->next != NULL && current->data.acctNum < newNode->data.acctNum)
{
  current = current->next;
}	
newNode->next = current->next;
current->next =newNode;

What is the purpose of 'prev'?

Lets take list {A, C}. We want to insert B.
List is not empty and B can't go before A, so we go to the else:
1. current = A
2. There is something after A and A<B
3. current = C
4. There is nothing after C
5. B->next = NULL
6. C->next = B
In other words, we got list {A, C, B}. We were supposed to get {A, B, C}.

[MorrowindFan664]

prev is left over from something I tried previously for that bit, which was:

current = head;
prev = NULL;

while(current != NULL && current->data.acctNum < newNode->data.acctNum)
{
prev = current;
current = current->next;
}

prev->next = newNode;
newNode->next = current;

Test runs still hung and returned no results in most cases.

[keskiverto]

I think you killed an innocent bystander.

You have:

//This is the destructor for the ListClass object
ListClass::~ListClass()
{
    NodePtrType q = head;
    while (q != NULL) {
        head = head->next;
        q->next = NULL;
        delete q;
        q = head;
    }
}

Note how you delete nodes.
When did you create nodes? (The new and delete work in pairs; can't have one without the other.)
In other words, you don't have any nodes.
With no nodes your pointer dereferences cause undefined behaviour; anything can happen.


Note: The NULL is a C macro. Modern C++ has a more precise keyword: nullptr.
Furthermore, there is implicit conversion from pointer to bool. Null pointer is false. Non-null is true.

ListClass::~ListClass()
{
    NodePtrType q = head;
    while ( q ) {
        head = head->next;
        q->next = nullptr;
        delete q;
        q = head;
    }
}

However, you don't need* to change the 'next' of node that you will immediately delete:

ListClass::~ListClass()
{
    while ( head ) {
        auto q = head; // C++11 auto: type of q is deduced from type of head
        head = head->next;
        delete q;
    }
}

*Unless the destructor of Node does something that has to be coped with.

[jonnin]

Furthermore, there is implicit conversion from pointer to bool. Null pointer is false. Non-null is true.

which is another way to say that zero has about 30 different ways to be expressed in c++.

[JLBorges]

The underlying hardware representation of the null pointer need not hold an address with a value which evaluates to zero; it is not another way to express the concept of the number zero. It expresses the concept of a pointer that does not point to something.

The implicit conversion from pointer p to bool is equivalent to one performed by evaluating the expression p == 0, it requires that the literal zero is first converted to a pointer type. The literal zero when used in source code in the context of a pointer represents the null pointer.

Primarily of historical interest:
Q: Seriously, have any actual machines really used nonzero null pointers, or different representations for pointers to different types? http://c-faq.com/null/machexamp.html

[keskiverto]

Literal zero can implicitly convert to a pointer type.
Pointer type does not convert to integer:

int main()
{
  double* x = 0; // OK
  unsigned long y = nullptr; // error
}

 In function 'int main()':
4:21: error: cannot convert 'std::nullptr_t' to 'long unsigned int' in initialization

[JLBorges]

The implicit conversion to pointer (null pointer conversion) applies only to literal zero;
there is no implicit conversion from integer to pointer.

const int* ptr = 0 ; // fine; literal zero

constexpr const int zero = 0 ;
// const int* ptr2 = zero ; // *** error: bad initialiser 

Null pointer conversion is applied only as a second resort.

#include <iostream>

void foo(int) { std::cout << "foo(int)\n" ; }
void foo( const void* ) { std::cout << "foo(pointer)\n" ; }

int main()
{

    foo(0) ; // foo(int)
    foo(nullptr) ; // foo(pointer)
    foo(NULL) ; // may be either foo(int) or foo(pointer) (implementation-defined)
}