|
Articles in this issue :
|
Collections in Java
Part 1 - The List Interface
Prior to Java 2, there were three basic ways to hold a group of objects: arrays, Vector, and Hashtable. Since
Java 2, we have a much improved group of Collection classes to fill virtually any need. There are two main interfaces
that inherit from the Collection interface: List and Set. Set objects do not allow duplicates and do not maintain
their objects in the order they are added. List objects allow duplicates and maintain their objects in the exact
order they are added. In this article we will look at the three classes that are implementations of the List interface:
Vector, ArrayList and LinkedList.
Here is a look at the List objects and their relationship to the Collection interface:
The most efficient way to store a group of objects is still an array. Arrays are efficient both in storing and
in randomly retrieving entries. The array is a simple linear sequence, which is why it is very efficient. In addition,
an array can keep track of type information so that you can avoid having to cast objects to their proper type.
With this efficiency comes a price. The size of your array must be allocated before it is used and it is not expandable.
However, if you know how many objects you will need to store, then an array is your probably your best choice.
The three implementations of the List interface are Vector, ArrayList and Linked List. Which one you should choose
will depend on the requirements of your implementation. An ArrayList is very efficient for getting objects from
the list. The LinkedList is more efficient at insertions into and deletions from the list. It also performed very
well at iterating through the list. The Vector performed worst of all 3 List objects. The Vector class is less
efficient than the ArrayList class mainly because the Vector class is synchronizedI would recommend that that you
run your own tests simulating your production environment to determine which List object will perform best for
you.
Testing of various List objects using 50,000 repetitions.
|
Type
|
Get
|
Iterate
|
Insert
|
Remove
|
| array |
297 |
610 |
|
|
| ArrayList |
406 |
1453 |
281 |
6344 |
| LinkedList |
3328 |
1032 |
62 |
16 |
| Vector |
1218 |
3125 |
297 |
6609 |
The Collection interface
The Collection interface is the parent interface of the List and Set interfaces. It contains many of the most commonly
required methods to process a collection. The Collection interface supports sequential processing of the Collection.
The methods to support random access of a Collection are found in the List interface. Here are some of the key
methods of the Collection interface:
- boolean add(Object) - Ensures the Collection holds the argument. In the case of a List object this means that
the Object is added to the Collection. In the case of a Set object, the Object is added only if it isn't already
in the Collection. Returns false if the Object was not added to the Collection.
- void clear( ) - Removes all elements from the Collection.
- boolean contains(Object) - Returns true if the Collection contains the argument.
- boolean isEmpty( ) - Returns true if the Collection contains no elements.
- Iterator iterator( ) - Returns an Iterator object which can be used to traverse through the Collection.
- boolean remove(Object) - Removes the argument from the Collection. Returns true if the argument was removed.
- int size( ) - Returns the number of elements in the Collection.
- Object[] toArray( ) - Returns an Object array containing all the elements in the Collection.
Using an Iterator
The Collection interface does not supply any get( ) methods, so you will need to use the Iterator class to get
items from the Collection object. The Iterator class makes sequential processing of a Collection very easy. The
key methods of the Iterator class are:
- hasNext( ) - tells you if there are more elements in the Collection.
- next() - returns the next element from the Collection.
- remove( ) - removes the last returned element from the Collection.
Here is an example of using an Iterator with an ArrayList:
Iterator myIterator = myCollection.iterator( );
while (myIterator.hasNext( )) {
System.out.println(myIterator.next( ));
}
Iterator and ListIterator (which we will discuss shortly) are fail-fast. That is, after the iterator is created
if the Collection is changed by any method other than a method found in the Iterator class (remove or add) then
the Iterator will throw a ConcurrentModificationException. However, Sun warns that it is possible that under some
circumstances the Collection may not detect the change and the Iterator could exhibit "arbitrary, non-deterministic
behavior". You should be careful to insure that your Collections are synchronized if they can be updated by
multiple threads.
Using the List interface
If random access of the List is required, then the Collection interface cannot be used since it does not have
the methods required. The Collection interface is the parent of both the List and the Set interfaces and since
random access is not meaningful in the Set classes no random access methods are supplied by the Collection interface.
The List interface does have methods for randomly accessing a Collection.
Some of the additional methods supplied by the List interface are:
- void add(int, Object) - Adds the second argument into the List at the index specified by the first argument.
- Object get(int) - Returns the element at the index specified by the argument.
- int indexOf(Object) - Returns the index of the element specified by the argument or -1 if the element was not
found.
- int lastindexOf(Object) - Returns the last index of the element specified by the argument or -1 if the element
was not found.
- Listlterator listlterator( ) - Returns a Listlterator object representing the items in this List.
- Listlterator listlterator(int) - Returns a Listlterator object representing the items in this List starting
with the index specified by the argument.
- Object remove(int) - Returns the element at the index specified by the argument and removes it from the List.
- Object set(int, Object) - Returns the element found at the index specified by the first argument and replaces
it with the second argument.
Using the Listlterator interface
The Listlterator is a child of the Iterator interface and adds additional functionality that the Iterator interface
does not provide. The additional methods allow for reverse traversing of the collection and for inserting or replacing
elements from the collection. The Listlterator includes all the methods of the Iterator interface and adds these
methods:
- void add(Object) - Inserts the argument into the List.
- boolean hasPrevious( ) - Returns true if the previous( ) method would return an element.
- Object previous( ) - Returns the previous element from the List.
- void set(Object) - Replaces the last element returned by either the next( ) or previous( ) method with the
object specified by the argument.
The ArrayList class
The ArrayList class is the simplest implementation of the List interface. The implementation of the ArrayList
is an array that automatically reallocates itself to a larger capacity whenever it runs out of room. That is, when
the array is full a new larger array is created and all the items are copied into this larger array. The ArrayList
is very efficient for locating an element in the list and for inserting objects at the end of the list. The ArrayList
class has only a few methods in addition to those found in the List interface:
- void ensureCapacity(int) - Increases the capacity of the ArrayList so that it can hold the number of elements
specified by the argument.
- void removeRange(int, int) - Removes all the elements from the ArrayList between the first argument, inclusive
and the second argument, exclusive.
- void trimToSize( ) - Sets the capacity of the ArrayList to its current size.
Allocating an ArrayList
By default, ArrayList objects are allocated to be large enough to hold only a few objects. When the limit is
reached, a new ArrayList is allocated larger than the previous one and the old ArrayList is copied to the new ArrayList.
With the ArrayList class the default initial capacity is 10 and the formula to increase the capacity of the ArrayList
each time it reaches its limit is (oldCapacity * 3)/2 + 1. Assuming that we use Collection c = new ArrayList( )
for an ArrayList which will hold 100 elements, we will guarantee that our ArrayList will be allocated 7 times (10
- 16 - 25 - 38 - 58 - 88 - 133). By allocating the ArrayList using Collection c = new ArrayList(100) we can avoid
the overhead of reallocating and recopying our ArrayList.
The LinkedList class
The implementation of a LinkedList is a doubly-linked list. That is, when the list needs to expand, it allocates
a new block and adds a link from the end of the original block to the new block and from the new block to the original
block. In this way the list can be traversed in either direction. The LinkedList is very efficient at insertions
into and deletions from the list. It also performs very well when iterating through the list.
The LinkedList class provides the required methods to simulate queues, stacks, and deques. The additional methods
of the LinkedList are:
- void addFirst(Object) - Adds the argument to the beginning of the list.
- void addLast(Object) - Adds the argument to the end of the list. .
- Object getFirst( ) - Gets the first element from the list.
- Object getLast( ) - Gets the last element from the list.
- Object removeFirst( ) - Returns the first element from the list and removes it from the list.
- Object removeLast( ) - Returns the last element from the list and removes it from the list.
The additional methods are designed to allow you to use method names that will simulate queues, stacks, and
deques. In actual use, there should be little difference between getFirst( ) and get(0) although
the comments in the code suggest that the stack/queue/deque operations may run slightly faster.
The Vector Class
As we already mentioned, the Vector class is the only one of the three List objects which is synchronized. The
Vector class was included in Java prior to the development of the Collection and List interfaces. It has been retrofitted
into the List interface without removing the methods which were originally in the class. This is the reason that
the Vector includes both an add method and an addElement method. When you use the Vector you should
use only the methods found in the List interface so that it will be easy to switch to another List object if it
becomes desirable.
Conclusion
We have taken a quick look at the main components of the List interface. As you can see, which List object you
wish to use will depend greatly upon how you intend on using it in your production environment. You may wish to
do performance checking using the various List objects to determine which is most suited for your needs.
Next month we will take a tour of the Set interface and explore the classes implementing this other main child
of the Collection interface.
Return to Top
|
|
Cindy's Segment - a Whimsical View of the World
Segment 4:
Stereotyping and pigeonholing
Or -
When is an Interface too tight
|
A while back we were talking about variables and how "Not all Variables are created equal". However do you know what all variables have in common? They are all TYPES. Mind you being a variable is what they ARE - being a type is what they DO.
And they do it with a vengeance!
Fiercely Loyal Labor
Being a variable is not as easy as it looks. To the casual observer it looks like they just sit there and hold some tiny bit of information, like a primitive value or the location that one can find the object that they reference. NOT SO! In fact variables have one of the hardest jobs in JVMLand. It doesn't matter if they are local variables, static variables or fields in an object - they all are assigned the task of being the "enforcer" for some type.
When a variable is created there is a little ceremony called "The Declaration" - something like being dubbed a knight. It is during this event that the variable declares it's eternal allegiance to a particular class or interface, or sometimes to a primitive. And from then on it spends the rest of it's life insuring that every activity that it performs conforms to the rules and regulations as declared in the Classfile Castle of it's liege lord. (Yes! Even interfaces have Classfiles that are built out at the edges of the Heap). Of course those variables that declare themselves to primitives have rules and regulations declared at even a higher level in the Commandments for JVMLand itself!
So what exactly is it that a they DO? Well their job has several aspects. These are divided into three major areas: Customs Inspections, Insuring that the correct Orders are issued from the proper Method Decrees, and Getting information from the Field.
A job well done
First there are the Customs Inspections at initialization. You can be assured that a variable will NOT allow anything but one of it's OWN to use it's services. Each time that a variable takes on a new value it demands to see the passport for the guy that wants in. Then the variable goes to that guy's Classfile and looks in it's Royal Listing. Here is maintained a List of all of the Types and SuperTypes and Interfaces and SuperInterfaces that are allies. The variable also checks all of the Supertypes of the Supertypes etc. If the variables does not find HIS type on this list of allies - then you can expect the variable to call in the Justice Department at compile time. It will NOT get past inspection.
Of course this complete Inspection is necessary so that the variable can rest assured that this guy will be able to do all the things that might be requested of the variable. When a call comes in to perform some method, then the variable knows that this guy will be able to do it, so the variable goes to his Classfile and looks up that method. If the method is marked as one of the Royal Static Decrees, then the variable requests that the method from his own Classfile is used. If the method is not marked static, then variable goes to the method area and hands over the passport for the guy that he is representing and waits while polymorphism is performed.
Polymorphism is sort of a "sorting ceremony" where all of the potential methods meeting the naming requirements that are related to types in the hierarchy of this guy are organized, and the one that is closest in the hierarchy to this guy wins. What a farce! Let me tell you this is ALL politics. It is ALL about keeping the little guy on the heap happy. This way he believes that he has some power or control over his destiny. Sheesh. Variables really HATE polymorphism, but they have to put up with it.
At any rate, in addition to having to figure out which Method decree to use, the variable has to figure out which field value from this guy to use. If the variable goes to his Classsfile and sees that the requested field is Static, then it is fairly straightforward. He just uses the Static field from his Classfile. He may have to run up to his SuperClassfile to find the thing, but it is clear which to use.
However, some of the guys that come to use his service have fields with the EXACT same name as those that variables type has. So they may have more than one field with the same name. Luckily each of these other fields are branded with the type that they were inherited from. These guys like to pretend that they only have ONE version by hiding the other fields with the same name. So if you ask this guy for that field, he will always pretend that you must mean his branded version of the field, but in fact the hidden ones really ARE physically there - inside that object. This requires extra special caution, because of course variables are much too loyal to use anything but the fields branded with their own type. So the variable ALWAYS checks the brand of the field and makes SURE that it is the one that came from HIS type definition.
So you can see that the job of a variable is VERY demanding. It is IMPERITIVE that you assign correct variable to the job to get it done right.
Before selecting the one you decide to use you must understand what is to be expected of this variable, and then select the type that provides all of that functionality. On the other hand if you select a type that has MORE than what you envision using then you can be sure that someone else out there is going to notice that and use that ability incorrectly. Therefore it is best to stick with something that provides what you need and not much more. That is why interfaces are such popular types for variables. They define just a certain set of job responsibilities and not more. NO matter what other type with MORE capabilities lands in that variable - they will be limited to only those things that the type allows.
So choose your variable with care - it MAY fit awfully tight when you actually try to USE it.
|
Copyright ? 2002. Cindy Glass. All rights reserved.
Graphics by Pauline McNamara and Stephanie Grasson
Next month - " Second Class Citizens"- or - "Living Life by the String Pool"
Return to Top
|
Movin' them doggies on the Cattle
Drive
It's where you come to learn Java, and just like the cattle drivers of the
old west, you're expected to pull your weight along the way. The Cattle
Drive forum is where the drivers get together to complain, uh rather,
discuss their assignments and encourage each other. Thanks to the enthusiastic
initiative of Johannes
de Jong, you can keep track of your progress on the drive with the Assignment Log. If you're tough enough to get through the nitpicking,
you'll see your name on the Graduation Log.
Gettin' them doggies...
Lots of activity on the Cattle Drive lately! Around 20 drivers are keeping the nitpickers busy lately, the majority kickin' up dust in
the OOP and Servlets corrals. Activity in the JDBC corral has raised quite a bit of dust - more on that later... And a shiny spur goes to...
After this month's storm of drivers we're gonna be needin' to stock up on some more spurs. Two notable drivers, Dirk Schreckmann and Louise Haydu each picked up not just one, but two silver spurs by whipping their way through both the Java Basics and the OOP sections of the Drive. Incredible! Our very own Michael Pearson picked up a gold spur by gettin' himself through the Servlets, not an easy task. A major milestone was set by Marilyn deQueiroz, who is the first to get herself out of the JDBC corral. Awesome. (But we knew that.) Y'all done real good, keep up the good work! Back from being out on the range...
Good news from one of our wayward Cattle Drivers who found their back: Manju Jain, a.k.a jytsika, is back with us to share in the dust and grime of the Servlets section. Welcome back jytsika, glad you made it! Saddle sore...
So close and yet so far, that's how it feels when you're just about to graduate from one of the Cattle Drive "schools." Elouise Kivineva is well on her way to pullin' in that oh-so-coveted first silver spur after the Java Basics assignments.
Ronald Schindler still has his eye on the silver spur for OOP, his saddle is well broken in by now. Hang in there, Ronald! He's joined by Josué Cedeno, who has moseyed his way up to the last OOP assignment and is just itchin' to get onto those Servlets! Peter Gragert has been sweatin' in the saddle with the final assignment in the Servlets section. He'll enjoy that sasparilla at the graduation celebration! Greg Harris has been steady on the trail, and is now about to attack the last Servlets hurdle. The JDBC corral has three cow pokes hoping to join Marilyn to form an elite group of JDBC graduates: Jason Adam, Lance
Finney and Daniel Olsen are already picking out new belt buckles to match their JDBC spurs!
Nitpicking is hard work too...
We know they're workin' reeeeeally hard, after all we've seen what those assignments look like once the nitpickers have combed through 'em. Hats off to Marilyn deQueiroz and Jason
Adam for their dedication and patience with the pesky vermin that always manage to make their way into those assignments. Newbie nitpicker Pauline McNamara has just started collecting nits too.
Tips for the Trail...
Here's one that comes back time and again: if you've gone through the Cattle Drive you've most likely heard of "print as you go". Often you don't need to track all those strings or pass 'em through a bunch of methods, you just need to print 'em! Check out the interesting threads on this topic over at the Cattle Drive forum.
Written by Jason
Adam and Pauline
McNamara
Return to Top
|
Book Review of the Month
Peopleware / Productive Projects and Teams (2nd ed)
by Tom DeMarco & Timothy Lister
|
|
|
This is my all-time favorite software engineering book. Peopleware
accurately recognizes that software engineering is about people, not technology.
It looks at the many facets of human issues in the software development process,
and shows why people aren't simply cogs in a software development machine.
The book spends a lot of time focusing on teams, and making you appreciate the
value of teams. It is not the usual 'teams are good' BS in a generic management
book. Instead it focuses on what makes a good team, and just how hard it is.
For managers trying to build or run a team, this book will help you recognize
the skills and techniques you need to do so successfully. It won't teach you
about a development process. It will teach you how to make your development
process work by getting you to recognize the value of people in software
development. (But it's not just for managers, I strongly recommend this book to
everyone, from the most junior engineer to the CEO.)
The book also contains large section on the office environment, and provides a
lot of strong evidence as to why conventional wisdom doesn't work. I turn down
jobs based on what I've learned from this section alone!
Oh yeah, this book is a little different from most books out there, it provides
hard evidence based on years of research.
This book fundamentally changed my views on software engineering!
(Mark A. Herschberg - bartender, April 2002)
More info at Amazon.com ||
More info at Amazon.co.uk
|
Chosen by Cindy Glass and Madhav Lakkapragada
Return to Top
|
June Giveaways
For more information on JavaRanch's Giveaways see Book Promotion Page.
Return to Top
|
June News
JavaRanch has a new Look and Feel!
Announcing a new Bartender!
If you look at our main Saloon page, you will see a new name. Yes, I'm pleased to announce that we've added a new Bartenders here at JavaRanch:
Corey McGlone
He was selected based on his history of helpful, informative posts, and we're very happy to have him join us. Welcome, Corey!
JavaRanch Shirts and Caps
Hey, we've added a Tack Room. No one should be out on the range without their vital JavaRanch supplies. T-shirts, caps, lunch bags, and mugs will keep you ready whether you are out on a cattle drive or just dropping in to the saloon.
As always JavaRanch is dedicated to providing you with the best source of information on Java Programming and Engineering.
by Carl Trusiak
Return to Top
|
Managing Editor: Carl Trusiak
Comments or suggestions for JavaRanch's NewsLetter can be sent to the NewsLetter Staff
For advertising opportunities contact NewsLetter Advertising Staff
|
Bitter Java
The JDK 1.4 Tutorial
Instant Messaging in Java: The Jabber Protocols
Java 2 Micro Edition