Hello. I guess you could call this an efficiency tutorial, on any programming language that has ArrayLists or LinkedLists. However, this is focusing on Java's ArrayLists and LinkedLists. I haven't seen any scripting languages with a built-in LinkedList, but I don't think many need the possible extra efficiency either.
Code will be in Java, but it should be pretty easy to understand if you know any high level programming.
Okay, summary's at the bottom, but before then I'll describe what both are, and how they store data. If you don't know what either are, you may want to read the next paragraphs, though. Note that for my examples I use Strings, but any kind of data could be used.
Both LinkedLists and ArrayLists store groups of data. You can basically think of them as many variables in one nice, neat pacakge. Instead of writing things like
String username1 = "someUser";
String username2 = "someOtherUser";
String username3 = "someOtherOtherUser";
. . .
You can write and access it more concisely, using ArrayLists
ArrayList usernames = new ArrayList();
usernames.add("someUser");
usernames.add("someOtherUser");
usernames.add("someOtherOtherUser");
. . .
(For those of you who know what I mean, I'm not using generic programming to keep things simple)
Alright, so the writing thing isn't more concise, but think what happens when you want to dynamically access a username? What if the user gives you their id to find their name? Then you'd have to make a really long if() statement, whereas in a List, you can do
usernames.get(id);
One thing to note about ArrayLists is that they start at 0, however, rather than 1. So usernames.get(1) actually gets the second element.
Okay, in Java, you'd also need to type-cast the Object back to a String, but that isn't hard. You'd just do
(String) usernames.get(id);
And, if you know generic programming, you don't even need to add that.
Okay, anyways, these ArrayLists (and LinkedLists) are quite handy for varying amounts of data. These Lists allow you to store a theoretically unlimited amount of data, just by adding data to it; they don't care how much you add.
By the way, making and adding to a LinkedList is the same as for an ArrayList, though you would define it by replacing the word "ArrayList" with "LinkedList" in the declaration, like this:
LinkedList usernames = new LinkedList();
Accessing the data is a bit different however. I am going to assume your compiler is at Java 5.0 Compliance, now. Here is how you would print the contents of a LinkedList.
for(Object obj : usernames)
{
String username = (String) obj;
System.out.println(username);
}
This is called a for each loop. For every value in the LinkedList usernames, you get a variable of the Object class called obj. I casted this Object into a String, and then printed it out. Technically, you can do this to an array as well, but that would kind of defeat the purpose of it.
ARRAY LISTS
Okay, now for how specifically an ArrayList works. This knowledge is required for making good decisions on which one to use for which case. Both ArrayLists and LinkedLists have their drawbacks and advantages.
ArrayLists store their data in an array of Objects, and they are equip to resize this array at their whim. This resizing is done by creating a new array with a slightly bigger size than the last one, and copying all values of the old one into the new one.
As such, ArrayLists are really fast for random access. That is, asking for the third, eighth, etc. element of the ArrayList. They just look that up in memory and return it to you. It's really fast, and takes only 1 access to the ArrayList to get data (This is written in what is called Big-Oh notation. In this case , it would be O(1)). This means that whenever you want to access 1 element, it takes the same amount of time. An example of the use of this, is that if there is a Bank program, and a user wishes to access his BankAccount by an ID he has. This ID corresponds to the location of the BankAccount object in some ArrayList. It is trivial to get this information to the user. As you will see, it is not the same way for a LinkedList.
Great, you say! ArrayLists are great! But wait! What if I want to add or remove one of those BankAccounts, in the beginning/middle of the ArrayList? Good question! The answer is dreadful: In the case of adding a new element to the beginning of the ArrayList, every element of the array must be pushed down 1 row. That means accessing every single element! The same is true for removing the beginning element, except that they need to be pushed up 1 row. If you want to just add the data to the end of the ArrayList, however, you are in luck. You need not push up or down anything! However, adding/removing elements of an ArrayList requires an average of n/2 accesses (O(n/2)), where n is the number of elements in the ArrayList. If you are only adding/removing data to the end of the ArrayList, however, it is just O(1). That's good, but removing only from the end? That seems quite unlikely. So, ArrayLists are no good at removing or adding data anywhere but to the end.
Okay, this may seem intuitively obvious, but iterating (going) through the ArrayList takes O(n) accesses, 1 for each element. Unlike the adding/removing thing, this is the same for LinkedLists. Ah well, it can't be avoided. If you want to print out every value of an ArrayList, you have to, well, access each value of the ArrayList.
Summary: ArrayLists are great for random access, bad for adding/removing data, and mediocre at iterating through.
(continued in next post)
