linked_list.cpp

// Author: Taylor Carr
//
// Spring  2016
//
// This program creates and manipulates a linked
// list of numbers
 
#include <iostream>
#include <cstddef>
#include <vector>
#include <ctime>
#include <cstdlib>
 
void createList(struct list *head); // Creates
                                    // Linkled list
 
void insertNum(struct list *head);  // Inserts #
                                    // Into list
 
void searchNum(struct list *head);  // Search for
                                    // # in list
 
void removeNum(struct list *head);  // Remove #
                                    // From list
 
void rotateList(struct list *head); // Shift list
                                    // 2 spaces
 
void displayBackwards(struct list *head); // Display
                                          // list backwards
 
void splitList(struct list *head);  // Split list
                                    // in 2
 
void deleteDuplicates(struct list *head); // Deletes duplicate
                                          // #s in list
 
void deleteList(struct list *head);  // Deletes entire list
 
void displayList(struct list *head); // COUTs list
 
using namespace std;
 
struct list{
    int num;
    list *next;
};
 
int main(){
 
 
    list *head = new list; // Stores the address for
                           // the head of the list
    head->next = NULL;
    char answer,           // Used to keep the program
    run = 'Y';             // running until user promts
                           // an exit
 
    srand(time(0));        // Ensures generation of
                           // random numbers
 
    while(run == 'Y'){
 
        cout << endl << endl;
        cout << "\t\tLinked List Menu\n"
        << "\tA. Build a sorted list of 20 integers\n"
        << "\tB. Insert a new number into the list\n"
        << "\tC. Search the list for a number\n"
        << "\tD. Remove a number from the list\n"
        << "\tE. Check if list is empty\n"
        << "\tF. Rotate the list\n"
        << "\tG. Display the list backwards\n"
        << "\tH. Split the list in 2\n"
        << "\tI. Delete duplicate numbers\n"
        << "\tJ. Delete the entire list\n"
        << "\tX. Exit program\n"
        << endl;
 
        cin >> answer;
        switch(answer){
            case 'A':
            case 'a':
                createList(head);
                displayList(head);
                break;
            case 'B':
            case 'b':
                insertNum(head);
                displayList(head);
                break;
            case 'C':
            case 'c':
                searchNum(head);
                break;
            case 'D':
            case 'd':
                removeNum(head);
                displayList(head);
                break;
            case 'E':
            case 'e':
                if(head->next == NULL){
                    cout << "The list is empty";
                }
                else{
                    cout << "The list is not empty";
                }
                break;
            case 'F':
            case 'f':
                rotateList(head);
                displayList(head);
                break;
            case 'G':
            case 'g':
                displayBackwards(head);
                break;
            case 'H':
            case 'h':
                splitList(head);
                break;
            case 'I':
            case 'i':
                deleteDuplicates(head);
                displayList(head);
                break;
            case 'J':
            case 'j':
                deleteList(head);
                break;
            case 'X':
            case 'x':
                cout << "Thank you for using Taylor Carr's Linked List program";
                run = 'N';
                return 0;
            default:
                cout << "Invalid Option" << endl;
                break;
        }
    }
 
 
    return 0;
}
 
// Case A: Create List
void createList(struct list *head){
    list *node = new list;
    list *current;
    bool changed = true,
    run = true;
    int count = 0;
 
    if (head->next == NULL){
        head->num= rand()%(11);
        head->next = node;
        for (int i = 1; i < 20; i++){
            if (i == 19){
                node->num = rand()%(11);
                node->next = NULL;
            }
            else {
                current = new list;
                node->num = rand()%(11);
                node->next = current;
                node = node->next;
            }
        }
    }
    else{
        cout << "A list already exist";
    }
 
    current = head;
    list *following = current->next;
    list *temp = new list;
    while (current->next != NULL & run == true){
 
        if (head->num > following->num){
            temp->num = head->num;
            head->num = following->num;
            following->num = temp->num;
        }
        if (current->num > following->num){
            temp->num = current->num;
            current->num = following->num;
            following->num = temp->num;
            current = head;
            following = current->next;
            count = 0;
            changed = true;
        }
        current = current->next;
        following = following->next;
        changed = false;
        count++;
        if (count == 20 && changed == false){
            run = false;
        }
    }
}
 
// Case B: Insert number into list
void insertNum(struct list *head){
    int number,
    position;
    list *traverse = new list;
    list *temp = new list;
    list *newNode = new list;
 
    cout << "What number would you like to insert? ";
    cin >> number;
    cout << endl << "What position would you like to input "
    << number << " at? ";
    cin >> position;
 
    if(position < 1 || position > 21){
        cout << "Invalid position";
    }
    else if(position == 1){
        temp->num=head->num;
        temp->next=head->next;
        head->num=number;
        head->next=temp;
    }
    else{
        for (int i = 1; i < position; i++){
            if (i == 1){
                traverse = head;
            }
            else {
                traverse = traverse->next;
            }
        }
 
        temp->next = traverse->next;
        traverse->next = newNode;
        newNode->num = number;
        newNode->next = temp->next;
    }
}
 
// Case C: Search for number
void searchNum(struct list *head){
    int number,
    count = 1,
    i = 0,
    positions[20];
    list *traverse = new list;
    traverse = head;
 
 
    cout << "what number would you like to search for? ";
    cin >> number;
    while (traverse->next){
        if (traverse->num == number){
            positions[i] = count;
            i++;
        }
        traverse = traverse->next;
        count++;
    }
    if (i > 0){
        cout << endl << number << " was found at the position(s) ";
        for (int j = 0; j < i; j++){
            cout << positions[j] << ", ";
        }
    }
    else {
        cout << "The number " << number << " was not found";
    }
}
 
// Case D: Remove a number
void removeNum(struct list *head){
    int number;
    list *traverse = new list;
    list *last = new list;
    list *temp = new list;
    traverse = head;
 
    cout << "What number would you like to remove? ";
    cin >> number;
 
    while(traverse){
        if(traverse == head && traverse->num == number){
            temp = traverse;
            traverse = traverse->next;
            delete temp;
            *head = *traverse;
            last = head;
        }
        else if (traverse -> num == number){
            temp = traverse;
            traverse = traverse->next;
            delete temp;
            last->next = traverse;
        }
        else{
            last = traverse;
            traverse = traverse->next;
        }
    }
}
 
// Case F: Rotate list
void rotateList(struct list *head){
    list *traverse = new list;
    list *newNode = new list;
    list newHead;
    int i = 2,
        count = 0;
 
    traverse = head;
    while(i > 0){
        traverse = traverse->next;
        i--;
        count++;
    }
 
    newHead = *traverse;
    traverse->next = NULL;
    *traverse = newHead;
 
    while(traverse->next!=NULL){
        traverse = traverse->next;
        count++;
    }
    traverse->next = newNode;
    traverse = traverse->next;
    *traverse = *head;
    *head = newHead;
    traverse = head;
 
    while(count > 0){
        traverse = traverse->next;
        count--;
    }
    traverse->next = NULL;
 
}
 
// Case G: Display backwards
void displayBackwards(struct list *head){
    int arr[20],
        i = 0;
    list *traverse = new list;
    traverse = head;
 
    while(traverse){
        arr[i] = traverse->num;
        i++;
        traverse = traverse->next;
    }
    cout << endl;
    for (int j = i-1; j >= 0; j--){
        cout << arr[j] << " ";
    }
}
 
// Case H: Split the list in 2
void splitList(struct list *head){
    list *traverse = new list;
    list *firstListHead = new list;
    list *firstList = new list;
    list *secondListHead = new list;
    list *secondList = new list;
    list *newNode;
    traverse = head;
    firstListHead->next = NULL;
    secondListHead->next = NULL;
    bool fail = false;
    int count = 0;
 
    for (int i = 0; i < 10; i++){
        if (traverse->next == NULL){
            cout << "The list cannot be split\n";
            i = 10;
            fail = true;
        }
        else if (firstListHead->next == NULL){
            firstListHead->num = traverse->num;
            firstListHead->next = firstList;
            traverse = traverse->next;
        }
        else if (traverse->next != NULL && firstListHead != NULL){
            firstList->num = traverse->num;
            newNode = new list;
            firstList->next = newNode;
            firstList = firstList->next;
            traverse = traverse->next;
        }
    }
    firstList->next = NULL;
 
    while(traverse){
        if (secondListHead->next == NULL){
            secondListHead->num = traverse->num;
            secondListHead->next = secondList;
            traverse = traverse->next;
            count++;
        }
        else {
            secondList->num = traverse->num;
            newNode = new list;
            secondList->next = newNode;
            secondList = secondList->next;
            traverse = traverse->next;
            count++;
        }
    }
    secondList->next = NULL;
 
    if (fail == true){
 
    }
    else {
        traverse = head;
        cout << "Original List: ";
 
        while(traverse){
            cout << traverse->num << " ";
            traverse = traverse->next;
        }
 
        traverse = firstListHead;
        cout << endl << "First Sub-list: ";
 
        for (int i = 0; i< 10; i++){
            cout << traverse->num << " ";
            traverse = traverse->next;
        }
 
        traverse = secondListHead;
        cout << endl << "Second Sub-list: ";
 
        while(count > 0){
            cout << traverse->num << " ";
            traverse = traverse->next;
            count--;
        }
 
        cout << endl << "Union list: ";
 
        traverse = head;
        vector <int> Union;
        Union.push_back(traverse->num);
        traverse = traverse->next;
        list *next = traverse;
        next = next->next;
        while(next != NULL){
            if (traverse->num == next->num){
                next = next->next;
            }
            else {
                Union.push_back(next->num);
                traverse = next;
                next = next->next;
            }
        }
 
        for (int i = 0; i < Union.size(); i++){
            cout << Union[i] << " ";
        }
 
        cout << endl << "Intersection list: ";
 
        vector<int> Intersection;
        vector <int> Intersection2;
        traverse = firstListHead;
        list *traverse2 = new list;
        traverse2 = secondListHead;
        int temp = -1;
 
        while(traverse2 !=NULL){
            if(traverse2->num != traverse->num){
                if(traverse->next == NULL){
                    traverse2 = traverse2->next;
                    traverse = firstListHead;
                }
                else {
                    traverse = traverse->next;
                }
            }
            if (traverse2->num == traverse->num && traverse->num != temp){
 
                cout << traverse->num;
                if(traverse->next == NULL){
                    traverse2 = traverse2->next;
                    traverse = firstListHead;
                }
                else {
                    traverse = traverse->next;
                    temp = traverse->num;
                }
            }
            else {
                if(traverse->next == NULL){
                    traverse2 = traverse2->next;
                    traverse = firstListHead;
                }
                else {
                    traverse = traverse->next;
                    temp = traverse->num;
                }
 
            }
        }
       Union.clear();
    }
 
 
}
 
// Case I: Delete duplicate numbers
void deleteDuplicates(struct list *head){
 
    list *traverse = new list;
    list *trail = new list;
    list *temp = new list;
    temp = head;
    trail = temp;
    traverse = temp->next;
 
    while(traverse && temp){
        if(temp->next == traverse && temp->num == traverse->num){
            temp->next = traverse->next;
            delete traverse;
            traverse = temp->next;
        }
        else if(temp->next != traverse && temp->num == traverse->num){
            trail->next = traverse->next;
            delete traverse;
            traverse = trail->next;
        }
        else if(temp->num != traverse->num && traverse->next == NULL){
            temp = temp->next;
            trail = temp;
            traverse= temp->next;
        }
        else if(temp->num != traverse->num && traverse->next != NULL){
            trail = trail->next;
            traverse=traverse->next;
        }
    }
 
}
 
// Case J: Delete list
void deleteList(struct list *head){
    list *traverse = new list;
    list *last = new list;
    last = head;
    traverse = last->next;
 
    while(traverse->next != NULL){
        delete last;
        last = traverse;
        traverse = traverse->next;
    }
    cout << "The list is empty" << endl;
    head->next = NULL;
 
}
 
// COUT the list
void displayList(struct list *head){
    if (!head){
        cout << "The list is empty" << endl;
    }
    else{
        cout << endl;
        list *traverse = new list;
        traverse = head;
        while(traverse){
            cout << traverse->num << " ";
            traverse = traverse->next;
        }
    }
}