Java Data Structures - Contents
A D V E R T I S E M E N T
We have already talked about linked lists previously
in this document, and the assumption was that you'll learn how to use them. We didn't
however explain a lot of the more used types of lists (not many people use a plain old
linked list). As it stands, the linked list explained earlier is pretty bad and
inefficient.
The most critical problem is that insertions and
deletions from the tail of the list are slow. To delete something from the end, we would
have to loop until we hit the end, and only then remove the item. This limitation is
fairly obvious, since it would be extremely inefficient to use that kind of a list (single
linked) to implement a queue.
The solution is to use a doubly linked list; where
each node has two pointers, one to it's left neighbor, and one to it's right, and to have
a head and a tail pointer. We will later implement this type of
a list.
Another critical problem with the previous lists is
that they have special cases in insert and remove methods. Ideally, we would just like to
insert and/or delete, without any special cases (like null head pointer). How
can we speed-up, and simplify the insertion and deletion operations? Easy! We simply have
a dummy head pointer which is always there (but is not storing any data).
Since we're interested in doubly linked lists, we would have two dummy pointers; the dummy
head, and dummy tail.
Some may argue that having nodes that store no data
is useless, and wastes memory. That may be true for some cases, where memory is critical,
but for most purposes, the speed and simplicity gained greatly outweigh the wasted memory
disadvantage.
You should still keep in mind the above. Sometimes,
you end up with arrays of arrays of arrays of linked lists, and in those cases, those few
wasted bytes, can add up to hundreds of megabytes. For example, it's pointless to have
dummy pointers if the lists never get beyond two or three elements. Before implementing anything,
think about the approach you're using.
Another strange thing our previous lists had was a peek(int)
method. We used it to go through the list, and view it's contents. This may have worked
quite well when the list was implemented using an array (where we directly jump to that
location), but when we were using linked lists, this peek(int) procedure got
quite slow. Given that we're looping through every element, and every time, we have to
loop until we hit that number inside the list, it starts to become obvious that it's a
waste of time.
What can we use to go through the items in the list,
do it safely, and more efficiently? In C++ world, programmers are quite familiar in
writing iterators. Iterators are used to iterate through objects contained in some data
structure (usually some data container class). In Java, we have something similar
available to us. It is called the Enumeration. Java provides the standard java.util.Enumeration
object for us to use to go through the items in the list. In fact, because the java.util.Enumeration
is standard, even java.util.Vector class uses it!
So, whenever we need to iterate through every
element in the list, we simply get the Enumeration for the class, and use
that to go through the elements. Details of the implementation are described later.
For now, we have improved our view of the list quite
a bit. You should still never forget to be inventive. There are other ways to represent a
linked list (for example, make it circular, with head and tail
being the same node). Hopefully, we'll later examine tree representation of a linked list.
A tree representation gives you the best of both worlds, linked structure, and fast
insertions and deletions (more on that later, hopefully).
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
|
Add to Favorites
Make Home Page
