India Forums .Info

Advanced Linked Lists

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).

sourcecodesworld.com