How can I insert linked list nodes in numerical order?

Question

I have come very close to completing this Linked List assignment for school but am struggling with the very last function. The purpose of this function is to take the numbers that have been read in from a text file and place them into the linked list in numerical order. I tried to make it to where it traverses through the list and the node gets added whenever the value is greater than the previous number but have reached a segmentation fault. I've been stuck on this for an embarrassingly long amount of time and would appreciate anyone's help. Below are the files I am working with and the horrible mess of a function named insertStrategic that is supposed to get the list in numerical order.

MAIN

#include "linkedlist.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>


using namespace std;

int main (){

    NodePtr newNode = NULL;

    // after you implemented your functions in .cpp file 
    // - use the code below for testing your linked list. 
    // Demonstrate that ALL functions are working correctly.

    // After that add code for reading data from input file.
    // Every time you read an integer, create a node and insert it
    // in the ascending order into the list.

    int num;

    FILE *fptr;

    // make sure file exists, give message and exit otherwise
        if ((fptr = fopen("input.txt","r")) == NULL){
            printf("Error! opening file");
            exit(1);
        }

    // while we still have items to read
        while( fscanf(fptr,"%d", &num) != EOF){
            newNode = makeNewNode(num);
            insertStrategic(newNode);
    }

    fclose(fptr);  // close the file  

    // At the end print the entire list to show that your code 
    // functions correctly.



    printList();

    cout << "After DeleteFromFront: " << endl; 
    deleteFromFront();
    printList();

    NodePtr seven = makeNewNode(7);     
    insertAtEnd(seven);
    cout <<"Inserting seven at END" << endl;
    printList();

    NodePtr eight = makeNewNode(8);     
    insertAtEnd(eight);
    cout <<"Inserting eight at END" << endl;
    printList();

    cout << "After deleting eight: " << endl; 
    deleteFromEnd();
    printList();

    cout << "After deleting seven:" << endl;
    deleteFromEnd();
    printList();



  return 0;
}

LINKED LIST FILE

#include "linkedlist.h"
#include <stdlib.h>
#include <iostream>


using namespace std;

   NodePtr head = NULL;
   NodePtr tail = NULL;


bool isEmpty(){
   return (head == NULL);
}

NodePtr makeNewNode(int number){
   NodePtr newNode = (NodePtr) malloc(sizeof(Node));
   if(newNode != NULL){
      newNode->data = number;
      newNode->next = NULL;
   }
   return newNode;
}

void insertAtFront(const NodePtr newPtr){
    if (isEmpty()){
        head = newPtr;
        tail = newPtr;
   }
   else{ // not empty
        newPtr->next = head;
        head = newPtr;
   }

}

void insertAtEnd(const NodePtr newPtr){

    NodePtr end = head;
    newPtr->next = NULL;

        while (end->next != NULL){
            end = end->next; 
        }

        end->next = newPtr; 
}



void insertStrategic(const NodePtr newPtr){

        if (isEmpty()){
            head = newPtr;
            tail = newPtr;
        }
        else {
            NodePtr traverse = head;
            newPtr->next = NULL;

                while ((traverse->next = NULL)){
                    while ((traverse->data < newPtr->data)){
                        traverse = traverse->next;
                    }
                    traverse = traverse->prev;
                    traverse->next = newPtr;
                    break;
                }
        } 
}   

void deleteFromFront( ){

    NodePtr temp = head;
    head = head->next;

}

void deleteFromEnd( ){

    NodePtr temp = head;
    NodePtr secTemp;

        while(temp->next != NULL) {
            secTemp = temp;
            temp = temp->next;
        }

        free(secTemp->next);
        secTemp->next = NULL;  
}



void printList( ){
   if (isEmpty()){
     cout << "List is empty" << endl;
   }
   else {
     NodePtr temp = head;
     while (temp != NULL){
       cout << " The data is: " << temp->data << endl;
       temp = temp->next;
     }
   }
}

HEADER FILE

#ifndef MYLIST_H
#define MYLIST_H

#include <cstddef>

   struct listNode {
        int data;
        struct listNode* prev;
        struct listNode* next;
   };

   typedef struct listNode Node;
   typedef Node* NodePtr;


   static int nodeCount = 0;

   bool isEmpty();
   NodePtr makeNewNode(int); 

   void insertAtFront(const NodePtr);
   void insertAtEnd(const NodePtr);
   void insertStrategic(const NodePtr);

   void deleteFromFront( );
   void deleteFromEnd( );

   void printList();


#endif

TEXT FILE TO READ IN

Think carefully about the condition in `while ((traverse->next = NULL))`. (If you added parentheses to get rid of a compiler warning, you should reconsider that choice. The warning was important.) — molbdnilo, Feb 07 '20 at 09:46
You should probably initialise `node->prev` to null (or implement a constructor and use `new` instead of `malloc`), in fact you never seem to set `prev` at all — Alan Birtles, Feb 07 '20 at 09:50
Please don't ever typedef pointers. That's bad practice, all that you achieve with is hiding information without *any benefit at all*; similarly [`using namespace std`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)... — Aconcagua, Feb 07 '20 at 09:53
You tagged your question C++. Why don't you just name your struct `Node`? Then you don't need that typedef. `struct Node { Node* prev; Node* next; };` is totally legal in C++ (unlike C, where you need the struct keyword...). — Aconcagua, Feb 07 '20 at 09:59
About design: You might consider adding a tail pointer to your list, then you don't have to iterate through the entire list to append new nodes. As is, you only can implement one single linked list that way. Maybe you want to make a class `LinkedList`? Then you can have multiple lists at once. All those functions you now have as free-standing would then get member functions, like: `class LinkedList { Node* head; Node* tail; public: void insertAtFront(Node const* ptr); /*... */ };` — Aconcagua, Feb 07 '20 at 10:04
By the way, you have introduced quite some trouble with your pointer typedef: `void insert(const NodePtr)` is equivalent to `void insert(Node* const)`, *not* to `void insert(Node const*)`, i. e. the pointer only is constant, *not* the object pointed to (which presumably is what you actually wanted...). Apart from, it would be better just to pass the data (`int` in given case) and create the nodes *inside* the function... — Aconcagua, Feb 07 '20 at 10:06
You shouild prefer C++ *keywords* (`nullptr`) over old (obsolete?) C *macros* (`NULL`). — Aconcagua, Feb 07 '20 at 10:08
Joining @AlanBirtles (`new` + constructor instead of `malloc`): Apart from, you don't ever `free` your nodes again, so you have introduced a memory leak... — Aconcagua, Feb 07 '20 at 10:09
@Aconcagua Honestly I'm a first year computer science student just doing an assignment. The out of date keywords, typedef pointers, and namespace std flaws are helpful to know of, but are just apart of the code that was provided to me for the assignment itself. I was given about 70% of the code, and was told to implement functions to get the program to work. Not the best way to teach students in my opinion but that's where I'm at lol — , Feb 07 '20 at 10:30
*'are helpful to know of'* – and that actually was the only intention of my comments, so please don't feel critisised... I very much agree on your *'not the best way'* comment, especially as the code you have been provided with is pretty bad C++. Looks far more like C-code spiced with a bit of C++... And you might present the teacher my last note about the typedef for pointer (the one where const-ness goes wrong – and that would have gone wrong even in C!), because that's pretty important. — Aconcagua, Feb 07 '20 at 10:37

score 0 · Answer 1 · answered Feb 07 '20 at 11:22

Here follows a simple solution, probably not the very best, but works. This function will insert the elements in ascending order.

Please note that we are not updating the "tail" of the list in this function.

void insertOrdered(const NodePtr newPtr){
        if (isEmpty()){
            head = newPtr;
            return;
        }

        NodePtr lastNode, whereToInsert = head;

        while (whereToInsert){
            if (whereToInsert->data > newPtr->data){
                break;
            }
            lastNode = whereToInsert;
            whereToInsert = whereToInsert->next;
        }

        if (whereToInsert == head){
            newPtr->next = head;
            head->prev = newPtr;
            head = newPtr;
        }
        else if (whereToInsert) {
            newPtr->next = whereToInsert;
            whereToInsert = whereToInsert->prev;
            newPtr->prev = whereToInsert;
            whereToInsert->next = newPtr;
        }
        else {
            lastNode->next = newPtr;
            newPtr->prev = lastNode;
        }
}

Also, please avoid using code like:

if ((fptr = fopen("input.txt","r")) == NULL){

Use in separated lines of code instead:

fptr = fopen("input.txt","r")
if (fptr == NULL){ /* your stuff */ }

score 0 · Answer 2 · answered Feb 07 '20 at 11:49

You can write something like this in insertStrategic(); 2 times while is not needed

while ((traverse->next != NULL)){
  if(traverse->data < newPtr->data)){
    traverse = traverse->next;
  }
  else{
    traverse->prev->next = newPtr;
    newPtr->next = traverse;
    break;
  }
}

How can I insert linked list nodes in numerical order?

2 Answers2