Doubly Linked List: Sorting nodes in ascending order

Question

I'm working on a program using doubly linked lists. I have already gotten the functionality to insert nodes, remove nodes, retrieve the value from a node, display the list, output the size of the list, telling if the list is empty, and deleting all nodes.

What I am having problems with is sorting the values in ascending order, and finding which node a certain value is in.

I am going to a help lab tomorrow I just thought I would see if anyone could help before then.

I have no idea what to do about sort(). I have find() somewhat working, but when I ask it to find the node of a value, it just returns the value I entered.

EDIT: deleteAll() now works properly!

#include <iostream>
#include <limits>

using namespace std;

struct node
{
int data; //data
struct node *next; //link to next node
struct node *back; //link to previous node
};

class LinkedList //class LinkedList
{
struct node *root;
struct node *end;

int size;
public:

LinkedList() : root(NULL), size(0){}

bool isEmpty() const { return (root == NULL); }
void create();    //cleate list
void insert();    //insertion
void remove();    //deletion
void display();   //display list
void sort();     //sort list
void find();      //find a values' node
void deleteAll(); //delete all values
void retreive();  //retrive node
void getSize();      //return the number of nodes
};

//Creating a new list
void LinkedList::create()
{
struct node *nxt_node;
struct node *prev_node;

int value;
int n;
int i;

root = nxt_node = NULL;

cout << "How many nodes will the list have?: ";
cin >> n;

cout << "Enter the numbers to create the list: ";

for(i = 1; i <= n; i++)
{
    cin >> value;
    nxt_node = new node;
    nxt_node->data = value;
    nxt_node->next = NULL;
    nxt_node->back = NULL;

    if(root == NULL)
    {
        root = nxt_node;
    }
    else
    {
        prev_node->next = nxt_node;
        nxt_node->back = prev_node;
    }
    prev_node = nxt_node;
}
end = nxt_node;

size = n;

cout << endl;
cout << "The list has been created!" << endl;
cout << endl;
display();
}

//Displaying the list
void LinkedList::display()
{
if(isEmpty())
{
    cout << "The list is empty!" << endl;
    return;
}
else
{
    struct node *tmp = root;

    cout << "The list is: ";

    cout << "root -> ";
    while(tmp != NULL)
    {
        cout << tmp->data << " -> ";
        tmp = tmp->next;
    }
    cout << "end";
    cout << endl << endl;
}
}

//Instert a node anywhere
void LinkedList::insert()
{
int pos;
int dat;

struct node *ptr_b;
struct node *ptr_f;
struct node *tmp;

cout << "At what node do you want to insert the new data?: " << endl;
cout << "(If the node is not found the data will be added to the beginning)" << endl;
cout << "Node: ";
cin >> pos;

cout << endl;
cout << "Enter the data to be inserted: ";
cin >> dat;

ptr_b = root;
tmp = new node;
tmp->data = dat;

while(ptr_b->next != NULL && ptr_b->data != pos)
{
    ptr_b = ptr_b->next;
}
if(ptr_b->next == NULL && ptr_b->data != pos) //insertion to front
{
    root->back = tmp;
    tmp->next = root;
    tmp->back = NULL;
    root = tmp;
}
else if(ptr_b->next == NULL && ptr_b->data == pos) //insertion at the end
{
    ptr_b->next = tmp;
    tmp->next = NULL;
    tmp->back = ptr_b;
    end = tmp;
}
else // insertion between two nodes
{
    ptr_f = ptr_b->next;
    tmp->next = ptr_b->next;
    tmp->back = ptr_b;
    ptr_b->next = tmp;
    ptr_f->back = tmp;
}
size++;
cout << "The new data has been inserted!" << endl << endl;
display();
}

//remove any node
void LinkedList::remove()
{
int loc;
int dat;

struct node *ptr_b;
struct node *ptr_f;
struct node *tmp;

cout << "Enter the node to delete: ";
cin >> loc;

tmp = root;

if(loc < size && loc > 0) //return the value at loc
{
    int ind = 0;

    while(++ind < loc && tmp->next != NULL)
    {
        tmp = tmp->next;
    }
}
if(tmp->next == NULL && tmp->data != loc) //Data not found
{
    cout << "Node not found!" << endl << endl;
    return;
}
else if(tmp->next == NULL && tmp->data == loc) //Delete from the end of the list
{
    ptr_b = tmp->back;
    dat = tmp->data;
    ptr_b->next = NULL;
    end = ptr_b;
}
else //Delete between two nodes or first node
{
    dat = tmp->data;

    if(root == tmp) //delete the first node
    {
        root = tmp->next;
        ptr_f = root;
        ptr_f->back = NULL;
    }
    else //deletion between two nodes
    {
        dat = tmp->data;
        ptr_b = tmp->back;
        ptr_b->next = tmp->next;
        ptr_f = ptr_b->next;
        ptr_f->back = ptr_b;
    }
}
delete tmp;

size--;
cout << endl;
cout << "The node has been deleted!" << endl << endl;
display();
}

//retrieve a nodes data value
void LinkedList::retreive()
{
int loc;

//if the list is empty, say so
if(isEmpty())
{
    cout << "The List is empty!";
    return;
}
else
{
    //If the list is not empty
    cout << "What nodes' value do you want to retrieve?: ";
    cin >> loc;

    if(loc < size && loc > 0) //return the value at loc
    {
        struct node *tmp = root;

        int ind = 0;

        while(++ind < loc && tmp->next != NULL)
        {
            tmp = tmp->next;
        }
        cout << "The nodes value is: " << tmp->data << endl;
        cout << endl;
    }
    else //if the node is out of range
    {
        cout << "Invailid location!" << endl;
    }
}
}

//sort the list in acending order
void LinkedList::sort()
{
cout << "The list has been sorted!" << endl;
}

//delete all the values
void LinkedList::deleteAll()
{
struct node *tmp;

for(int i = 1; i < size; i++)
{
    while(root != NULL)
    {
        tmp = root;

        root = tmp->next;

        delete tmp;
    }
}
display();
}

//find a values' node
void LinkedList::find()
{
int value;

//if the list is empty, say so
if(isEmpty())
{
    cout << "The List is empty!";
    return;
}
else
{
    //If the list is not empty
    cout << "What values' node do you want to find?: ";
    cin >> value;

    struct node *tmp = root;

    int ind = 0;

    while(++ind < value && tmp->data != value)
    {
        tmp = tmp->next;
    }

    if(tmp->next == NULL && tmp->data != value) //Data not found
    {
        cout << "Value not found!" << endl << endl;
        return;
    }
    else
    {
        cout << "The value is at node: " << tmp->data << endl;
        cout << endl;
    }
}
}

void LinkedList::getSize()
{
cout << "The list has " << size << " nodes" << endl << endl;
}

int main()
{
LinkedList list;

list.create(); //create a new list
int choice;
while(1)
{
    cout << "What would you like to do? (1-7): " << endl;
    cout << "1. Insert a number" << endl;
    cout << "2. Delete a node" << endl;
    cout << "3. Delete ALL values" << endl;
    cout << "4. Retrieve a nodes' value" << endl;
    cout << "5. Retrives a values' node" << endl;
    cout << "6. Return the size of the list" << endl;
    cout << "7. Exit the program" << endl;
    cout << endl;

    cout << "Enter your choice (1-7): ";
    cin >> choice;
    cout << endl;

    switch(choice)
    {
        case 1: //insertion
            list.insert();
            break;
        case 2: //deletion
            list.remove();
            break;
       case 3: //delete all the values
            list.deleteAll();
            break;
        case 4: //retrieve a nodes' value
            list.retreive();
            break;
        case 5: //retrieve a values' node
            list.find();
            break;
        case 6: //returns the lists size
            list.getSize();
            break;
        case 7: //Exit the program
            exit(0);
            break;
        default:
            cout << "Please enter a vaild choice (1-7)!" << endl;
            break;
    }
}
return 0;
}

Any help would be appreciated. I understand if you don't want to help on both things, just getting the one I have close to being done (find()) would be awesome!

Thanks.

Answer 1

For deleteAll your for loop needs to start from 0, not from 1 (or go to size+1). Think about a list of size 1, your code would not execute, which is why there is 1 node left in your linked list. Your code also needs to be rethought. Rather than a for loop maybe a while loop?

struct node *tmp;
while (root != NULL)
{
    tmp = root;
    root = root->next;
    root->back = NULL;    //Is this even necessary? You're deleting ALL nodes.
    delete tmp;
}
display();

As for your find function, you've set it to return void (nothing). It's printing the node value because you tell it to but you're not returning the node. You need to think about what find should return (the node, or null).

I would suggest looking up QuickSort to sort your list. Because this is a specialized case you'll have to tailor the QuickSort to sort by node->value and when you sort you'll have to make sure your nodes point to the correct previous and next nodes when you swap values. Continue posting your code as you run into more errors and please make sure you let us know what you've tried and what's not working, we'd be happy to help point you in the right direction.