### Sorting Linked List Nodes in order

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
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475`` `````` 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 10: #include 11: #include 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:``````
// 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()
{
}//end of constructor

//This is the destructor for the ListClass object
ListClass::~ListClass()
{
while (q != NULL)
{
q->next = NULL;
delete q;
}
}//end of destructor
//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 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 deleteAtEnd();

void deleteIthNode(int);

void deleteItem(RecordType);
private:
NodePtrType head; //points to beginning of the list
};
#endif
//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;
};
 ``123456`` ``````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.

 ``12345678`` ``````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}.
prev is left over from something I tried previously for that bit, which was:

prev = NULL;

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

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

I think you killed an innocent bystander.

You have:
 ``1234567891011`` ``````//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.
 ``12345678910`` ``````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:
 ``12345678`` ``````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.
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++.
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
Literal zero can implicitly convert to a pointer type.
Pointer type does not convert to integer:
 ``12345`` ``````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```

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

 ``1234`` ``````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.

 ``123456789101112`` ``````#include 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) }``````
Topic archived. No new replies allowed.