Thread: Arrays, Linked Lists and Unordered Lists

  1. #1
    Registered User
    Join Date
    Oct 2019
    Posts
    20

    Arrays, Linked Lists and Unordered Lists

    Note: This is part of an assignment for a course I am currently enrolled in.

    I'm in a C++ programming class and part of my assignment is to write a class function "CopyEarlyList" for AUList (array-based unordered list) that duplicates the first N elements of the list and returns it as a new, separate list, in the same order.
    I know that it would start something along the lines of:
    Code:
    class CopyEarlyList {
        public:
    };
    but passed that I am for some reason having a difficult time creating it completely. Lists, at least in this context, are a kind of new area for me. I have used them before but never using a class function.
    Any help you all can provide is very appreciated!

  2. #2
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    937
    C++ has classes, which are user-defined types, and C++ has functions. There are also member functions, which are like normal functions except:
    - They have an additional hidden parameter: "this."
    - They can be invoked on instances of the class on which they're defined, e.g. myList.CopyPrefix(4).
    - They can access the members of the instance as if they were in scope.

    I'm not sure, but it seems like your assignment is to add a member function to an existing list class, where the function does what you described. Is that right?
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  3. #3
    Registered User
    Join Date
    Oct 2019
    Posts
    20
    In a way yes that is correct but as far as I understand from the professor I am just responsible for creating a class function that if supplied with the necessary main function would run correctly. However, I do not have to supply any other functions passed the class. I also do not have an existing list class to add this CopyEarlyList class to.

  4. #4
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    937
    I thought I had made another reply, but I think I accidentally deleted it.

    I don't know what an array-based unordered list is, but after googling around and reading some Java documentation, my best guess is that it's a resizable array with a sequence interface.

    In C++, the canonical class for that is
    Code:
    std::vector<T>
    , for some element type T, e.g. int. You can use std::vector after including the standard vector header:
    Code:
    #include <vector>
    You can read about the interface of vector and the algorithmic complexity of each operation here: std::vector - cppreference.com

    It's likely that your professor has another type in mind (you mentioned some AUList). In that case, use the corresponding operations on that type.

    Based on the problem described, a function having the following signature ought to do the trick (assuming you are working with integers):
    Code:
    std::vector<int> repeatPrefix(const std::vector<int>& original, int prefixLength);
    That takes a reference providing non-modifiable access to a vector of ints, and returns a new vector of ints, where the idea is that the returned vector has the first prefixLength elements of the original repeated at the front.

    Since you probably won't be using vector, I don't feel too bad writing this for you as an example:

    Code:
    #include <cassert>
    #include <initializer_list>
    #include <iostream>
    #include <vector>
    
    // Return a copy of the specified `original` but that has additionally had
    // the `prefixLength`-length prefix repeated once at the beginning.  For example,
    // `repeatPrefix({1, 2, 3, 4, 5}, 2) == std::vector<int>({1, 2, 1, 2, 3, 4, 5})`.  The
    // behavior is undefined unless `prefixLength` is non-negative and less than
    // or equal to the length of `original`. 
    std::vector<int> repeatPrefix(const std::vector<int>& original, int prefixLength) {
        assert(prefixLength >= 0);
        assert(prefixLength <= int(original.size()));
    
        // This is the object we will return.
        std::vector<int> result;
    
        // Make room for the elements.  This is unnecessary and a premature
        // optimization, but since we know the output length, I can't resist.
        result.reserve(original.size() + prefixLength);
    
        // Add the first `prefixLength` elements.
        result.insert(result.end(), original.begin(), original.begin() + prefixLength);
    
        // Add the entire input.
        result.insert(result.end(), original.begin(), original.end());
    
        return result;
    }
    
    int main() {
         // See what the result is when we use the example from the contract.
         for (int x : repeatPrefix({1, 2, 3, 4, 5}, 2))
             std::cout << x << '\n';
    }
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  5. #5
    Registered User
    Join Date
    Feb 2020
    Posts
    1
    An array is the data structure that contains a collection of similar type data elements whereas the Linked list is considered as non-primitive data structure contains a collection of unordered linked elements known as nodes.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C Programming Arrays and Linked Lists
    By Amrita Ramnauth in forum C Programming
    Replies: 18
    Last Post: 04-16-2016, 03:01 PM
  2. Arrays of linked lists
    By Chuklol in forum C Programming
    Replies: 2
    Last Post: 04-17-2012, 06:45 PM
  3. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 01:07 PM
  4. Arrays Vs Linked Lists
    By ianbd in forum C++ Programming
    Replies: 3
    Last Post: 08-31-2005, 08:41 AM
  5. linked lists / arrays
    By akira in forum C++ Programming
    Replies: 0
    Last Post: 11-27-2001, 01:01 AM

Tags for this Thread