Cheryl Scodario

fred rosenberger wrote:Not if you are inserting in the first position.

I am not talking about any special(best) case. So let's just say sorted list: insert and find (average case).

Ernest Friedman-Hill wrote:

Cheryl Scodario wrote:

Ernest Friedman-Hill wrote:
Removing from a linked list does, indeed, always take constant time.

Hi Ernest, why removing from a linked list always takes constant time? Because I kinda agree with Jesper that it will have to find the element to remove first, then actually do the remove action.

Finding an object takes linear time; subsequently removing it takes constant time. For an array, finding takes linear time for unsorted, and logarithmic time for a sorted list; and removing takes linear time.

Removing does not always imply finding. For example, consider removing the first element of a list. For a linked list, it's done in constant time, and for an array or ArrayList, it takes linear time.

I see...How about insert in a sorted list? I always think of remove and insert very similar. But is insert implying find for sure? Because you need to find the right position to insert it. Then it would be N, linear time?

Ernest Friedman-Hill wrote:
Removing from a linked list does, indeed, always take constant time.

Hi Ernest, why removing from a linked list always takes constant time? Because I kinda agree with Jesper that it will have to find the element to remove first, then actually do the remove action.

What's the time complexity to remove an element from a sorted and unsorted linked list? I have heard different answers. I mean for remove, do we need to concern with the "find" part? Because in an unsorted linked list, you need to find it first, which takes O(n), though the remove action itself just takes 1. So do we say N or 1? Sorted and unsorted have the same time complexity I think. Insert also has to do with "find".

Thanks!

Hi all, I am doing an encryption program, and need to find the x and y in this formula: gcd(a,b)=a*x+b*y;
I know the idea is to follow the steps of the actual Euclidean algorithm, and then just doing everything backwards, but I don't know how to put that in code.
One thing to note, gcd (a, b) will be 1 in my case, because a and b are coprime. so basically we are looking at 1=a*x+b*y and find x and y.
Please give me some hints!

Thanks.

Jason Koonce wrote:;

Now, below that is a bunch of methods, class summaries and things like that. Basically, what this is, is a small description in semi-plain English about what the class does. In this case it takes byte code and translates it to characters for other readers to make use of. In other words, a serialized non-text file that was stored as byte-code.

Hey Jason! Thanks as always. I am just wondering what does a byte-code looks like? Because I feel like so far I have been using text file that contains strings. But I did use InputStreamReader once, but I don't remember why?

Hey Jason! Thanks a lot! This makes a lot of sense now. BufferedReader is more advanced compared to FileReader. I think if I just want to read a sting of characters, then FileReader would suffice. And you are absolutely right that it does take some skill to read API. Many people were like: just read the API. And I was like: I did try! but without much success. I think programming teachers do not really teach those IO stuff, so we have to look up everything on our own. One more question though, do you know when to use InputStreamReader? Because I have seen it being used in BufferedReader as well. BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)) THANKS!

Jason Koonce wrote:One way of looking at the differences is in steps. With FileReader you read what? Just the characters, right? so what do you read should you have something other than simple characters? What if you tried storing multiple lines, serialized objects, or arrays? The stored information would simply read as a sentence for the FileReader.

BufferedReader, on the other hand, is more diverse in its capabilities. Using the information it receives from the FileReader it translates that information into meaningful code as well as Strings, should there be any, for you to then convert and manipulate in your program without adding a lot of additional, already been done for you, code.

Hi Jason, thanks for the explanation. So you were saying that for FileReader, it reads characters from a word, like "hello"? But I think it should also be capable of reading multiple lines since they are just consisted of "many" characters? Arrays are usually words or numbers as well. I am not so clear at what you were trying to say about FileReader? Were you saying that FileReader can read them all, but doesn't process them correctly/ translate them into meaningful code?

Rob Spoor wrote:Let's make the code a bit more readable by splitting up that one statement, shall we?
public int hashCode() { int x=0; for (int i =0; i < str.length(); i++) { int c = (int) str.charAt(i); // the cast to int is actually not necessary int temp1 = c + 256 * x; // pretty straight forward x = temp1 % modulus; } return x; }Now, let's take "Hello" and walk through it.

i = 0: c is the int value of "H" which is 72 (see http://www.asciitable.com/). temp1 is 72. x is 72 % modulus.
i = 1: c is the int value of "e" which is 101. Assuming modulus > 72, temp1 is (101 + 256 * 72 == 18533. x is 18533 % modulus.
etc.

Hi Rob, thanks for rearranging the code! I hate the one-liners as well. I get the mechanism, but I was just wondering why x*256? My teacher mentioned something about binary numbers.

Hi guys, I just have a question about a method that my teacher wrote to generate hash codes for Strings. I guess there are many different ways to get hash codes. The code is the following:
public int hashCode() { int x=0; for (int i =0; i < str.length(); i++) { x=(((int) str.charAt(i)) + 256*x)% modulus; // modulus here is the size of the hash table. } return x; }

So I think 256 comes from 2^8, and does that have to do with 8 bits integers/memories and two's complement? I am pretty bad with those. Can anyone explain to me in understandable terms? I don't get the "x=" part. Suppose we have a string:Hello.

Campbell Ritchie wrote:There should be lots in the Java™ Tutorials; look for the "buffered" subsection.

Thanks, Campbell. The link was very useful. However, it didn't explain FileReader. I use it only when I need to use BufferedReader. So I am wondering if it has other uses, or like what's the difference between FileReader and BufferedReader?

fred rosenberger wrote:

So why we need FileReader? What is its function? Why can't we just have: ... = new BufferedReader("personDataBase")?

When you bake a cake, do the directions say "plant some grain, wait 6 months, harvest it, grind the seeds into a white powder. You will need two cups of that powder" or does it say "get two cups of flour"?

The idea here is that each of these objects do a little something, and you build off what others have done. And sometimes, you may what whole wheat flour, sometimes cake flower, sometimes all purpose flour...there may be times when you would want to pass something other than a FileReader into a BufferedReader.

Hi fred, thanks for some brief explanation. However, to be totally honest, I did check API for all of these before I posted these questions, but I still couldn't figure out the differences.
Let's now look at FileReader and BufferedReader:
"FileReader is meant for reading streams of characters. For reading streams of raw bytes, consider using a FileInputStream."
BufferedReader: "Reads text from a character-input stream, buffering characters so as to provide for the efficient reading of characters, arrays, and lines."
I still can't tell the difference between the two. And what does it mean by "raw bytes, using FileInputStream"?
I just need someone to give me some examples of each, so I get an idea of when to use them. Thanks!

Hi guys, so whenever I program, I always experience problems like reading a file as input and output the result to another file, or to the screen. So I just have some questions regarding the different java classes that I have used so far, and what their differences are. I also gave some examples.

1. BufferedReader, FileReader, InputStreamReader. The following are some applications:
BufferedReader reader = new BufferedReader(new FileReader("personDataBase"));
Its parameter is: new FileReader. So why we need FileReader? What is its function? Why can't we just have: ... = new BufferedReader("personDataBase")?
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
So here we have InputStreamReader in the parameter, what's its difference from FileReader?

2. So is FileWriter correspondent with FileReader? BufferedWriter is correspondent with BufferedReader?
ex. FileWriter output= new FileWriter(args[0]); BufferedWriter writer = new BufferedWriter(output);
How is FileWriter different from BufferedWriter, and vice versa?

3. File class. So when I work on unix, and I want to feed a file to a class, I type: java HelloWorld greeting.txt. That's when we need File class:
File inFile=new File(args[0]); Scanner input=new Scanner(inFile);
So the File class here simply just creates an instance of this file? why can't we use FileReader or something like above to directly read it?

4. What are PrintStream class and PrintWriter class?
PrintWriter output = new PrintWriter(args[1]);

Thanks for all the clarifications!

marc weber wrote:When you start...

Index i holds element i

Index j holds element j

In the "wrong" code, you have...
this.set(i, get(j));
After this line runs...

Index i holds element j

Index j holds element j

...so element i is lost (and the next line of code makes no difference).

The correct code avoids losing element i by storing it in a temporary variable.

Hey marc! Your first explanation has already made perfect sense! Thanks a lot for attempting the second time! I got it. This is really elementary java knowledge, and I should have mastered it by now! I will remember that for future reference!

Darryl Burke wrote:
// Pattern.java

public String[] split(CharSequence input, int limit) {
:
: // for certain conditions
return new String[] {input.toString()};

:
: // for other conditions
String[] result = new String[resultSize];
return matchList.subList(0, resultSize).toArray(result);
}[/code]So you see an array is always created in the same way, although that may not be in your own code.

Thanks, Darryl. I see it now, so in the split method, it has already "new" the array implicitly (not visible to the human eye) for String[] parts.