Skip to content

Instantly share code, notes, and snippets.

@CarrCodes

CarrCodes/linked_list.cpp

Created April 3, 2018 17:37
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save CarrCodes/3b3c8a964ae453c2dfcf303fc6e00a63 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save CarrCodes/3b3c8a964ae453c2dfcf303fc6e00a63 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Taylor Carr created this gist Apr 3, 2018.
    580 changes: 580 additions & 0 deletions linked_list.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,580 @@
    // 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;
    }
    }
    }