1

Hi I have a data structures programming project involving creating my own array based list and then efficiently storing String read from a file but in reverse. So that arr[0] = the last line of the file

Initially I just thought to have two for loops:
First to store the data by its order in my list
Second to create a new list and add elements in reverse order

Then I thought about just creating an array based list that stores data in reverse, so that the first line of the file is stored at arr[arr.length-1] and so on. This I believe is saving me a for loop

I know in the end both are O(n), but is this what my professor means when he says "as efficient as possible"?

Are there any other ways I could reverse my list?

Thanks.

Improve this question
4
  • 4
    I can't say what your professor means when he say "as efficient as possible". In term of performance ? Of memory consumption ? Ask him first for that.
    – Spotted
    Oct 18, 2016 at 5:24
  • It helps if you have some code you have already created to solve the problem. At this point (design), there is a lot of good choices that can be made, and since this is an assignment, we also don't know the constraints on what you can use (generics, streams, etc) to make useful suggestions. Based on array and file, read the file into an array, then reverse the array (walk the array, swapping(arr[i], arr[length - i]). O(n) time, O(n) space where n is the number of lines in the file.
    – Kristian H
    Oct 18, 2016 at 15:23
  • 1
    Is there something wrong with developing a class that stores the contents in an array in forward order and retrieving elements in reverse by calculating an element number relative to the end?
    – Blrfl
    Oct 19, 2016 at 3:14
  • 1
    I'm voting to close this question as off-topic because it's a homework question.
    – Pieter B
    Feb 3, 2017 at 0:54

3 Answers 3

Reset to default
1

Does it have to be a list? Storing the data in a reverse order sounds to me like a situation where a stack should be used.

You could implement a stack and just push every row on top of it. Then, when you pop every element of the top of the stack, they would be popped in the reverse order.

Considering that this is a data structures programming project, it might be what your professor would like to see.

Improve this answer
0

I am not sure on constraint for given problem.You can get the number of lines from given file. If length is n. You can fill arraylist in reverse order. or You can create list with original order. Then try reversing created list.

Improve this answer
1
  • How would you get the number of lines from the file efficiently? AFAIK on *nixes, usually you need to read the entire file to count the number of lines, which would be slower than OP's current solution of reading all the lines first and reversing them in memory since two reads of the entire file will take up a lot more I/O time. But maybe there's a way to do that efficiently that I don't know about!
    – Gaurav
    Nov 4, 2016 at 20:20
0

Then I thought about just creating an array based list that stores data in reverse, so that the first line of the file is stored at arr[arr.length-1] and so on. This I believe is saving me a for loop

Yup, it does, and I think this is probably the most efficient way to do this! Remember that your array-based list doesn't have to know how many items will eventually be added to it: when someone calls yourArrayList.get(2), you can return the last item currently in your list (i.e. array.length-2-1).

I think your professor meant both computational complexity (i.e. O(n)) as well as taking the least amount of time. One loop will take less time than two!

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.