Here is my linked list class. I cannot figure how to sort through the list. Please take a look at my sort function and point me in the right direction.
//Pablo Salinas
//COSC 2436
//Assignment 2: Linked List
//Due Date 11/09/2016
#include <iostream>
#include <string>
#include <algorithm>
usingnamespace std;
class LinkedList { // creating the link list class
private:
struct nodeType { //struct used to create nodes
string info;
nodeType* link;
};
nodeType *first, *last, *newNode;
int count1;
public:
LinkedList() {//Default contstructor setting the first and last nodes to nullptr
first = nullptr;
last = nullptr;
}
void addElement(string name) { //Adding a new node to the linked list
newNode = new nodeType;
newNode->info = name;
newNode->link = nullptr;
if (first == nullptr) {
first = newNode;
last = newNode;
}
else {
last->link = newNode;
last = newNode;
}
count1++;
}
void removeElement(string name) { //Removing an existing node from the list by searching and deleting the node
nodeType *current, *bcurrent;
if (first == nullptr) {
cout << "Cannot delete from an empty list." << endl;
}
else {
if (first->info == name) {
current = first;
first = first->link;
if (first == nullptr) {
last = nullptr;
}
delete current;
}
else {
while (current != nullptr) {
if (current->info == name) {
}
else {
current = current->link;
}
}
}
}
}
bool isEmptyList() { //Bool function to check if the list is empty or full
return (first == nullptr);
}
void listSize() {
nodeType *current;
current = first;
int count = 0;
while (current != nullptr) {
current = current->link;
count++;
}
cout << count;
}
void printList() { // function to print the list
nodeType *current;
current = first;
while (current != nullptr) {
cout << current->info << ", ";
current = current->link;
}
}
void sort() { // function to sort through the list. Using a bubble sort variation.
nodeType *current, *bcurrent;
current = first;
bcurrent = first->link;
for (int i = count1 - 1; i >= 0; i--) {
for (int j = 0; j < count1 - 1; j++) {
if (current->info > bcurrent->info) {
swap(current->info, bcurrent->info);
}
current = bcurrent;
bcurrent = bcurrent->link;
}
}
}
void reverse() { // function to reverse the order of the list.
nodeType *current, *next, *prev;
current = first;
next = nullptr;
prev = nullptr;
while (current != nullptr) {
next = current->link;
current->link = prev;
prev = current;
current = next;
}
}
};
int main() {
string str1; //declaring a variable to store the string
LinkedList b; // declaring my class object
if (b.isEmptyList() == true) { //checking if the list is empty
cout << "The list is empty" << endl;
}
do { // do while loop to prompt the user to enter a word and do the functions inside the class
cout << "Enter a word(1 to quit): ";
cin >> str1;
if (str1 == "1") { // option to quit the loop
break;
}
else {
b.addElement(str1);
cout << endl;
b.printList();
cout << endl << "The list size is ";
b.listSize();
cout << endl;
}
} while (str1 != "1"); // option to continue the loop
cout << "Sorted list: ";
b.sort();
cout << endl;
b.printList();
cout << endl;
system("pause");
return 0;
}
Sorting a linked list is actually very difficult. However, you can store all linked list elements into a vector, sort the vector and build the linked list again based on the sorted vector.
