Categories : Java

 

1. Introduction
1.1. What’s a Linked List?

2. Singly Linked Lists (Implimented as a FIFO)
2.1. The isempty() Method
2.2. The enqueue() Method
2.2.1. temp.next = listNode;
2.2.2. listNode = temp;
2.2.3. if(tail == null) { tail = temp; }
2.3. The dequeue() Method
2.3.1. char c = tail.data;
2.3.2. temp = listNode;
2.3.3. if (temp.next == null){ … }
2.3.4. if(temp.next.next == null)
2.3.5. temp = temp.next;
2.4. Congratulations!

3. Doubly Linked Lists
3.1. But What if You Have to Go the Other Way?
3.2. The isempty() Method
3.3. The addToTail() Method
3.3.1. if (tail == null) { … }
3.3.2. else { … }
3.3.3. tail.data = c;
3.3.4. current = tail;
3.3.5. The addToHead() Method
3.3.6. The addToCurrent Method
3.3.7. if (current == null) addToHead(c);
3.3.8. else if (current == head) addToHead(c);
3.3.9. else if (current == tail) addToTail(c);
3.3.10. Node temp = new Node();
3.3.11. temp.data = c;
3.3.12. temp.next = current.next;
3.3.13. current.next = temp;
3.3.14. temp.prev = current;
3.3.15. temp.next.prev = temp;
3.3.16. current = temp;
3.3.17. char getCurrentData(){ … }
3.4. The moveHead() Method
3.5. The moveTail() Method
3.6. The moveNext() Method
3.7. The movePrev() Method
3.8. The removeTail() Method
3.9. The removeHead() Method
3.10. The removeCurrent() Method
3.10.1. current.prev.next = current.next;
3.10.2. current.next.prev = current.prev;
3.10.3. current = current.next;
3.11. Wrap-up

4. Using java.util.LinkedList
4.1. Constructor Method
4.2. The enqueue(Object o) Method
4.2.1. list.addFirst(o);
4.3. The dequeue() Method
4.4. The isempty() Method

5. And They Lived Happily Ever After…

1. Introduction

Top

1.1. What’s a Linked List?

A Linked List is a particularly useful data structure that allows you to create a storage space that is capable of growing in size to suite the needs of the program. Basically, you can think of it as an array that can add cells when there is a need for more storage, and remove them when there is no longer a need to keep track of certain things. Still Confused? Let me see if I can clarify…

You know what an array is, right? It’s a collection of cells, each cell being capable of storing data. When creating the array we set aside a specific amount of memory for storage purposes. Let’s say we have an array that needs to hold 5 integers; int array[5]. We could start putting these integers into the array by saying array[0] = 10; for the first cell, array[1] = 6; for the second, etc. (remember that arrays begin indexing at 0). Of course if the need to add a 6th number to our collection of data arises, we have a problem: an ArrayIndexOutOfBounds problem to be specific. Now, we COULD just make the array bigger than it will ever need to be. If we “know” that we only will ever need 5 integers, we could make an array that could hold 10. This way if there is ever a situation that we haven’t accounted for (and there almost always is), then we have a little room to play with. Of course, this is inneficient. For this many integers, any modern system should be able to handle it, but in situations where we have to keep track of large amounts of data in an array, about 10 MB for example, doubling the size (to 20 MB) is a serious problem. Even if you do have RAM to spare the negative performance would be noticeable. This reveals the ultimate limitation to arrays in Java; once you make them, the size is set in stone.

Enter the linked list; a data structure whose size is variable depending on the needs of the program (and, of course, the total available memory on the system). In our above example, we were planning on needing to store 10 MB of data, but there may be times when we only need to store 8, and there may be time when we need to store 15. Of course memory is cheaper these days then it was a decade ago, but wasting memory is still something that is a no no; remember, it is abundant, not infinite, and if you program long enough, you’re going to run into a situation where every byte counts.

That being said, a linked list does resemble an array in some ways. A linked list is a collection of cell-like units called nodes. A node typically has two parts, one part is a cell with which to hold data, and the other is a refference to one of two things; the heap (that portion of memory that is available for programs to grab), or another node. Want a picture? I thought you would.

[]{}–>

There you have a single node. The [] represents the data portion of the node, and the {} represents the refference portion. The –> shows what the refference is reffering to; at this point in the story of single node, the refference portion of the node reffers to nothing but a bunch of memory, which we can describe as NULL. But now we need another node to store some more data…

[]{}–>[]{}–>

Now the refference section of the first node is pointing to the data segment of the second node, and the refference section of the second node is pointing to NULL. In this fashion, the data in the second node comes right after the data in the first node; we don’t worry so much about the refference sections because they are written in such a way as to take care of themselves. And what follows the data section of the second node? You guessed it! NULL.

By now you’re probably wondering how we can access an individual node of a linked list. Well, theres one limitations of the linked list; we have to extract the data in some sequential order, which means either first in first out (FIFO) or last in first out (LIFO), and generally speaking, we have to know which way we’re going to keep track ahead of time. But in many cases, we don’t actually need the random access that an array can provide us with, so in practice this is not as much of a problem as it seems. So how is it we keep track of data? Well, typically we start at the first node, and begin moving down the list until we run out of nodes, using an index to keep track of our current position in the list. But what if we need to move back? I’ll get to that a little bit later, for now let’s worry about creating the list and moving forward :)

Top

2. Singly Linked Lists (Implimented as a FIFO)

Okay, I’ve talked long enough, let’s start to look at some code. The following is all the code that we need to begin implimenting our linked list. This particular class describes the node of a singly linked list….

 

   class Node
   {
    char data;
    Node next;
   }

Yes, the node is that simple. The first line in the class; char data; defines the storage space of the node. We’ve defined it to be of type char, which is completely arbitrary. The second line of the class, Node next; is the fun part. It recursively builds another node each time we construct the first node in the list; next, of course, initially points to NULL, and it won’t actually reffer to another node until we explicitly tell it to. The nice thing is that we can do this recursively too.

Of course I can talk forever about how a node of a list works, but I doubt that it will actually mean anything until I show you an implimentation of class Node. Fortunately, there is a familiar concept, the FIFO, which greatly benefits from having a linked list as its underlying data structure. This example is going to take a little while, but don’t worry if you don’t completely understand it yet, I’ll walk you through the details when I’ve shown you the whole thing.

 

   class ListFIFO
   {
    Node listNode; // A standard node in the linked list.
    Node tail; /* This is a special node, we use it to keep track of the 
                * first node in the list.
                */ 

    /* First define a function that determines whether or not
     * the list is empty.
     */

    boolean isempty()
    {
     return tail == null; 
    }

    void enqueue(char c)
    {
     Node temp = new Node(); // Create a temp node for data manipulation. 
     temp.next = listNode; // Assign the pointer of temp to another Node
     temp.data = c;  // Give the char passed into enqueue to the data segment

     /* Now we need to find out if this is the first node in the list.
      * If it is, we'll assign it to be tail, otherwise we'll make it a
      * regular node in the list.
      */  

     if(tail == null)
     {
      tail = temp;
     }

     listNode = temp;
    } // end void enqueue(char c)

   char dequeue()
   {
    char c = tail.data; /* Read the data segment of the first node into 
                         * the method.
                         */
    Node temp = new Node(); // Create a temp node for data manipulation.
    temp = listNode; // copy "current" node to temp.

    /* If temp.next is pointing to NULL, then we only have this one 
     * Node, and since we've already extracted data from it, we can just
     * return that data to the calling method.
     */

    if (temp.next == null)
    {
     tail = null;
     listNode = null;
    }

    /* As long as temp.next points to non-null data, then we have 
     * more nodes we can work with.
     */

    while (temp.next != null)
    {

     /* If the refference section of the next node in the list points to
      * null, then assign tail the temp node, set tail.next to null,
      * and break out of the loop. 
      */

     if(temp.next.next == null)
     {
      tail = temp;
      tail.next = null;
      break;
     }

     /* Otherwise set the current temp node to the value of the 
      * next temp node.
      */

     temp = temp.next;
    } // end while (temp.next != null)

    return c;
   } // end char dequeue();
  } // end class ListFIFO

Wow, that’s a lot. I’ll be examining this class one method at a time. Just to give you a general overview right now, isempty() just checks to see whether or not our list is empty; enqueue() creates a new list node, and stores data in that new node; dequeue() returns data from the “first” list node in the list, and then “forgets” about it so that the list shrinks. Since garbage collection takes care of any allocated memory we’re not using, we don’t need to explicitly free it up, just making it so that it is no longer accessable is good enough.

Top

2.1. The isempty() Method

This is pretty strait forward. If tail is set to NULL, then we don’t have anything left in our list, and we’re done. This works because 1) If there is nothing in the tail node (and hence the list is empty), the tail will be set to null, and 2) If we have removed every node from the list (and hence the list is empty), the tail will be set to null. The isempty() function, like the one we use for the array version of a FIFO, doesn’t directly manipulate the FIFO, but it is useful for implimentation in various other classes that may extend this one. It’s also useful for illustrating the major difference between our ListFIFO and a FIFO using an array; in this case we’re not keeping track of indexes, we’re keeping track of whether anything is actually there or not.

Top

2.2. The enqueue() Method

Top

2.2.1. temp.next = listNode;

This is the first really “interesting” piece of code in the enqueue() method. After creating the temporary node, which we will be using for immediate data manipulation, we immediately set the pointer sedment of that node to point to another node in the list. This way, all we’ll have to do is copy the temp node into the list when we figure out where exactly it belongs.

Top

2.2.2. listNode = temp;

Here we’re just assigning a generic node to our current value of temp. We need to do this no matter what so we can create a “physical” node in our list, and so it really doesn’t matter whether we do it now, or after we determine if it will be the tail.

Top

2.2.3. if(tail == null) { tail = temp; }

I’ve squished this all onto one line in the hopes that it’ll be a little more understandable this way. Just read it from left to right; if the tail is NULL (and therefore the list is empty), then copy the temp node into tail. This means that the tail will be the first node in the list, and so it is extremely important to keep track of it. Without the tail node, we will have no way of refferencing the list in any meaningful order, and will only be able to keep track of the node we are currently working on (since the node that exists >after the current one doesn’t exist yet, and we don’t have a way of looking backwards yet).

Of course, this is not exactly accurate, as we are creating out list in reverse order. That means that the dequeue() method is going to have to be a bit complicated, but I’ll get to that in a moment. Say we were to enqueue the latters “X”, “Y”, and “Z”… our ListFIFO would look a lot like:

[Z]{}–>[Y]{}–>[X]{}–>NULL

I know before I said that we can’t go backwards, but in reality, we don’t have the ability to go forwards yet. Remember that a node can only refer back to a parent node. Since we enqueued “X” first, it is the root node (tail) of the bunch, and it cannot refer to a parent node because it doesn’t have one. The second char we enqueued (“Y”), will refer back to the node storing X, because that node was a valid space in memory at the time, and the Y node is linked to it by virtue of the fact that listNode was linked to temp.next when we started the enqueue process.

So the task for dequeing our list (returning data and removing nodes) means that we start with the tail, and return the data, and then count backwards from the current position of the list (in this case Z), until the node after the one we are currently looking at is NULL. Why? Because when the node after the one we are curretly looking at is NULL, that means we are currently looking at the original tail of the list, and ipso facto the current node of the list (the one we are standing on) is the one that wants to be the new tail. Since we are going to make this node (the one we are standing on) the new tail, we are going to lose any refference to our previous tail, the garbage collector will take care of it, and now the node we are standing on, the new tail, will be pointing to NULL.

Now that you have a bettr idea as to how our list was constructed, and how we’re going to take it apart, lets actually walk through the deconstruction code.

Top

2.3. The dequeue() Method

Top

2.3.1. char c = tail.data;

Fairly strait forward here; we take the data from the first node in the list (the tail), and store it in a buffer inside of the method.

Top

2.3.2. temp = listNode;

This should also be nice and strait forward, but I want everyone to be clear on exactly what is going on here. The “current” (read last) node in the list is copied into temp. Remember how I said we have to move backwards? We’re going to be moving backwards from the last item in the list, checking for tail all the way (see above).

Top

2.3.3. if (temp.next == null){ … }

I’ll refer to this entire block of code by this line to save space here. If temp (the “last” node in the list) points to NULL, that means that there is only a single node in the list, and we’re sitting in it. By setting everything that we keep track of to NULL, we’re de-refferencing it, and since we’re going to be returning the one piece of data in our list (which we are already storing within this method), we don’t need the list anymore.

Top

2.3.4. if(temp.next.next == null)

This is the only way out of our while loop. If the pointer in the node that the pointer in temp is pointing to is NULL; in other words if the node after next points to NULL, then the next node is tail, the beginning of the list. If this is the case, we can copy the contents of temp into tail (setting the tail pointer to NULL just to be safe), and break out of the loop.

The effect of this is that the current node (the one we’re standing in), which is just AFTER the tail in the list (i.e., it is the second item enqueued), becomes the new tail. We don’t need the old tail anymore because we already have copied the data out of it. The next time we dequeue, we’ll be extracting data from the current node of the list (which will then be tail).

Top

2.3.5. temp = temp.next;

Just to clarify, as long as the above if conditional does not apply, and the next node is not the tail, then we can set temp to the next node. Eventually, we will get back to the tail if we follow this pattern, at which point we will break out of the loop, and this line will not be executed.

Top

2.4. Congratulations!

You now know how a linked list implimented as a FIFO works. Taking the above example and turning into a LIFO is trivial, and so I leave to you to practice (HINT, the list moves backwards anyway). Of course you can also figure out how large the list is by traversing it to the tail and not removing any items from the head. You can also move down the list and look at data without removing it, but since this data structure is fairly common, and thisprovides you with a nice framework for implimenting singly linked lists in the future.

Top

3. Doubly Linked Lists

Top

3.1. But What if You Have to Go the Other Way?

Up to now, I’ve been talking about a singly linked list that can only be traverses in one direction, but it is possible to create a list which has two node sections, and keeps track of the next node that is created as well as the node that was previously created. Whaa?!? Let me show you…

The first thing we have to do is re-define our Node class. Since we are now keeping track of two positions, we have to add another refference section in our node:

 

   class Node
   {
    Node prev; //short for previous
    char data;
    Node next;
   }

There’s the easy part, now we have to start using it. The following example is a departure from the FIFO; it is a simple two-way list that allows us to move back and forth in the list. We can create or remove a Node at either the head, the tail, or at the “current” position. In this list, we’ll be able to retrieve data without deleting it. I’m sure you can see where more sophisticated implimentations of this sort of list can be extremely useful, but now lets see some code…

 

  class doubleList  
  {
    Node listNode; // A standard node
    Node head = null; // The head of the list.
    Node tail = null; // The tail of the list.
    Node current = null; // This will be a marker for the current node of list.
    Node lastNode;  

    /* First, a method to determine if the list is empty */

    boolean isempty()
    {
      return tail == null;
    }  

    /* Now we need a method to add elements to the tail of the list. */

    void addToTail(char c)
    {

      if (tail == null)
        {  
          tail = new Node();  
          tail.next = null; 
          tail.prev = null;

          /* If this is the first node in the list, then 
           * make it the head as well.
           */

	  if (head == null)
	    {
	      head = tail;
	    }

        }

        else
          {  
 	    Node temp = new Node(); //for data manipulation.
	    temp.prev = tail;
	    temp.next = null;
	    tail.next = temp;
	    tail = temp;
          }

      tail.data = c; // We need to store data no matter what.

      current = tail;

    } //end void addToTail(char c)

    void addToHead(char c)
    {

      if (head == null)
        {
	  head = new Node();
	  head.next = null;
	  head.prev = null;
      
          /* If this is the first node in the list, then 
           * make it the tail as well.
           */

	  if (tail == null)
	    {
	      tail = head;
	    }

        }

        else
          {
	    Node temp = new Node(); //for data manipulation.
	    temp.prev = null;
	    temp.next = head;
	    head.prev = temp;
	    head = temp;
          }

        head.data = c; // We need to store data no matter what.

        current = head;

    } //end void addToHead(char c)


    /* The next function will add a node to the list directly after
     * the current position.  If we really need to add before the current 
     * position, it is trivial to simply move the current position back one
     * place, and equally trivial to write a method for adding before the
     * current position.
     */

    void addToCurrent(char c)
    {
      /* The only time current will be null is if the list doesn't yet
       * exist.  Just add to the head in this case.
       */

      if (current == null) addToHead(c);

      /*
       * If we are already at the head or the tail, we already have 
       * methods for adding to these, and adding to the head or the 
       * tail requires special considerations, so if we try calling 
       * this method at one of those two points, we should just
       * pass the data along to one of the methods for adding to the
       * head or the tail.
       */

      else if (current == head) addToHead(c);

      else if (current == tail) addToTail(c);

      else
        {
	  Node temp = new Node();
	  temp.data = c;
	  temp.next = current.next;
	  current.next = temp;
	  temp.prev = current;
	  temp.next.prev = temp;

	  current = temp;
        }
    } //end  void addToCurrent(char c)


    /* Now that we can create the list, we need a method for retrieving 
     * the data that we've entered...
     */

    char getCurrentData()
    {
      Node temp = new Node();
      temp = current;

      return temp.data;
    } // end char getCurrentData()

    void moveHead()
    {
      if (current != head) current = head;
    }

    void moveTail()
    {
      if (current != tail) current = tail;
    }

    void moveNext()
    {

      /* If we are at the tail, we don't need to do anything,
       * otherwsie we just move the current position to the 
       * next node.
       */

      if (!(current.next == null))
        {
	  System.out.println("moving to next.");
	  current = current.next;
        }

      else
        {
	  System.out.println("Couldn't move next!");
        }
    } //end void moveNext()

    /* And now one for moving towards the head of the list. */

    void movePrev()
    {

      /* If we are at the head, we don't need to do anything,
       * otherwsie we just move the current position to the 
       * previous node.
       */

      if(!(current.prev == null))
        {
	  System.out.println("moving to prev.");
	  current = current.prev;
        }
      else
        {
   	  System.out.println("Couldn't move prev!");
        }

    } //end void movePrev()

    /* Now that we can create, move around in, and read from 
     * our list, we need to be able to remove nodes from the 
     * list.  We'll focus on simply removing from the head and
     * the tail.
     */

    void removeTail()
    {
      if(tail != null)
        {
	  if (tail == current) current = tail.prev;
	  tail = null;
        }
    } 

    void removeHead()
    {
      if(head != null) 
        {
	  if (head == current) current = head.next;
	  head = null;
        }
    }

    /* This method will delete the current node, and set the next (read,
     * next towards tail) node as the new current.
     */

    void removeCurrent()
    {
      /* If current is null, then we haven't created the list yet, and
       * we don't want to do anything.
       */

      if (current != null)
        {
	  /* If current is the same as head or tail, we already have
	   * methods for diong that, so just call them.
	   */

	  if (current == head) removeHead();
	  else if (current == tail) removeTail();

	  /* Now we get down to buisiness */

	  else
	    {
	      current.prev.next = current.next;
              current.next.prev = current.prev;
	      current = current.next;
	    }
        } // end if(current != null)
    }// end void removeCurrent()

  } //end class doubleList

Wow that’s a lot of code isn’t it? Because the list moves in two directions, we have a lot more to keep track of, and so a lot of the code has changed. It is, however, not quite as complicated as it may first appear. Lets start from the beginning:

Top

3.2. The isempty() Method

Here we have the all important task of figuring out if the list is empty. There are a couple of ways of figuring this out, but all of them involved determinging if one of the special refferences (head, tail, or current) is null. If any one of these is null, than no node has been added to the list or all nodes have been deleted from the list, and the list is therefore empty.

Top

3.3. The addToTail() Method

Our first really interesting function definition. When we add a new node to the list, we are always going to specify the data to be contained in that node. Hence the char c. But what happens in the meantime?

Top

3.3.1. if (tail == null) { … }

The first thing we should do is check to see if there is a tail already, and if there’s not then we make one. Since it is the only node in the list at this point, all of its pointers are directed at null (that will change as we add more nodes. Since it is also the first node in the list, the tail is also the head, but it couldn’t hurt to do a simple check just to be on the safe side.

Top

3.3.2. else { … }

Lets take this one step at a time. The first thing we do is create a new node. Since we are adding to the tail, this new node will become the new tail, meaning that the previous node in the list (the old tail) is no just an ordinary node. We need to initialize the prev pointer of the new node to point to the old tail (temp.prev = tail;) so that we can keep track of where that node is. Since the new node is the new tail, there is nothing next, so we can go ahead and set the next pointer to null (temp.next = null;). Having done that, we still need to link the old tail to this node (in case we are approaching the tail from the head and not the other way around). That’s why we haven’t done away with the old tail node yet. We simply set the next pointer of the old tail node (still reffered to as “tail”) to point to this temp node that we just created (remember that tail’s next pointer still points to null)(tail.next = temp;). Finally, now that the old tail node has been linked apprpriately to this node (and vice versa) we can change the refference so that this node is the new tail (tail = temp;).

Top

3.3.3. tail.data = c;

This shouldn’t be any real surprise. Now that the new tail node has been assigned, we give it the data that has been passed into the method. It is important to do this after we have created the new node, or else the data stored in the old tail node would be changed, and we certainly don’t want that.

Top

3.3.4. current = tail;

Just as a house-keeping measure, whever we add to the head or the tail we set current to be either the head or the tail. In practice this isn’t very efficient, but this is an educational program after all. This way, when you’re writing your test driver for all of these methods, you’ll be able to know where current is set to based on whether you last added to the head or the tail, so you’ll know which way you need to move.

Top

3.3.5. The addToHead() Method

I’m not going to spend a great deal of time with this method, as it is basically the inverse of addToTail(). All of the same concerns I discussed in the addToTail() description apply here, but you do have to make sure that you’re updating the prev pointer instead of the next pointer.

Top

3.3.6. The addToCurrent Method

This method bears discussing because adding a node somewhere in the “middle” of the list is a bit different than adding it to the head or the tail of the list. When you add to the head or tail, you only have to keep track of one set of pointers. When adding to the tail, you know that next will always be null, when adding to the head, you know that prev will always be null, but when you add something to the list in between nodes, both next and prev have to refer to somehting else. As a result, this method is a little more ocmplicated than the other two, but don’t worry, I’ll walk you through it.

Top

3.3.7. if (current == null) addToHead(c);

The first thing we should do is see if current exists (of course). The only circumstance in which it wouldn’t is if the list has yet to be created. There’s absolutely no reason to re-invent the wheel here. We already have two perfectly good methods that can be used to create a list from scratch, and there really isn’t any difference between them (all pointers will point to null, and all refferences will point to the single node in the list). In this case I’ve just made an arbitrary decision to call addToHead() but addToTail() would do exactly the same thing.

Top

3.3.8. else if (current == head) addToHead(c);

I hope this makes sense. If the current node is the head, we already have a perfectly good method for adding nodes to the head, so we can just call that method.

Top

3.3.9. else if (current == tail) addToTail(c);

Again, a perfectly good method already exists for adding a node to the tail. No need to reinvent the wheel.

Top

3.3.10. Node temp = new Node();

If we can’t get away with calling some other method to do our work for us, then the first thing we’ll need to do is create a new node.

Top

3.3.11. temp.data = c;

And again, stash that data in the node.

Top

3.3.12. temp.next = current.next;

Since we’re squeezing this node in between two pre-existing nodes, we need to make sure that this node’s pointers will reflect that it is between two nodes. In this case, we set the next pointer the new node to be the same as the node that is next after current.

Top

3.3.13. current.next = temp;

Remember that we are squeezing in this node next after the current node. Therefore, the set the current pointer to point to the new node (we’ve already set the new node to point next to what current.next was pointing at, so we haven’t lost track of the node.

Top

3.3.14. temp.prev = current;

Since the new node comes after the current node, we set the prev pointer of the new node to point to current.

Top

3.3.15. temp.next.prev = temp;

And just to make absolutely certain that all of our pointers are properly updated, we set the node that is previous after next after the new node (i.e. the new node) to point to temp… the new node. This makes certain that the node that is next after the new node does in fact refer prev to the new node. Otherwise the node would derail when it tried traversing prev as soon as it got to this newly created node.

Top

3.3.16. current = temp;

And last but not least we set the new node as the current node in the list. Strictly speaking, we do not have to do this, and the list would certainly work if we did not. This was purely a matter of prefference on my part.

Top

3.3.17. char getCurrentData(){ … }

This is a fairly straitforward method. We first make a copy of the current node into a remp buffer, and then we return the data portion of that buffer to the calling function. Note that the data that is in the node remains untouched, which is a major departure from the method of removing items from the list when we get their contents.

Top

3.4. The moveHead() Method

This one is a no brainer. If we are not already at the head of the list, jump there.

Top

3.5. The moveTail() Method

Another no brainer.

Top

3.6. The moveNext() Method

This one may look intimidating, but it is really very simple. If the next node in the list is not null, then set the next node after current as the current node in the list. We print a little message saying whether or not we were able to move

Top

3.7. The movePrev() Method

movePrev is trivially different from moveNext(). If the prev node in the list is not null we set the node that is prev before current as the current node in the list. Print the same sort of status indications about success or failure.

Top

3.8. The removeTail() Method

It is extremely handy to be able to remove parts of the list, and so we have created a series of methods that allow us to do this at verious points. This one checks to see if the tail (and hence the list itself) is empty. If there is a tail on the list, then we need to see if the tail is the current position. If it is, then we simply set current to the node that is prev before tail. In either case, we set the tail of the list to null. Anything pointing to it will now also point to null. The node no longer exists in the list.

Top

3.9. The removeHead() Method

This is fairly well the same as removeTail(), except if the head is the current node, we need to set the current node to the node that is next after the head before setting the head to null.

Top

3.10. The removeCurrent() Method

Here we are deleting the node of the list that was are currently positioned at. Like adding a node to the list, this means we have to keep track of which pointers are pointing where, or the list will no longer be properly linked, and traversals of the list will derail. If the current node is either the head or the tail, we can just call removeHead() and removeTail() respectively. Otherwise there is a little bit of finagling involved.

Top

3.10.1. current.prev.next = current.next;

In this case, we need to set the next pointer of the node that is prev before current to point to the node that is next after prev. Now there is no next pointer pointing to the current node.

Top

3.10.2. current.next.prev = current.prev;

Likewise, we have to set the prev pointer of the node that is next after current to point to the node that is prev before the current node. When we have done this, there will be nothing pointing to the current node, and as soon as we re-assign the value, the node will cease to exist.

Top

3.10.3. current = current.next;

Now we set the current refference to the node that comes next after the current node. When we do this, all traces of the old current node will be gone from the list.

Top

3.11. Wrap-up

And there you have it, the explanation of that doubly-linked list. It is a lot of effort, but the lists we have created here are a good basis for creating more functional lists. Commonly, we would use Objects as the storage medium (since they can store anything), but there is no hard and fast rule that our nodes only can have one storage portion. As long as the pointers are linked, we can store as much data in a nodes as we want. So go out and have some fun experimenting with these lists. Play around with them a bit, and pretty soon you’ll know them inside and out.

Top

4. Using java.util.LinkedList

You slacker! What’s wrong, is it too much work to copy and paste what is listed above into your own file, and compile that, extending your classes to use it, or even coming up with an interface so you can use the methods available? Well, I guess I have been the one saying this whole time that you don’t need to re-invent the wheel, now haven’t I? And as most of you had probably guessed, I wouldn’t waste my time typing all of this if the answer to the question weren’t that this work has already been done for you in the Java platform itself. Bless those folks over at Sun. So if you don’t need to write your own linked lists, you already understand how to do so but don’t want to do it each time, you want to take advantage of Java built in classes, or you’re not doing this for homework, read on.

This isn’t something I plan on spending too much time on. For starters, you should already have a good idea as to how a linked list works, and since all of the details are taken care of for you, there really isn’t much that goes into using these methods, but to put them in their proper perspective, allow me to show you a familiar example using them.

Do you remember the linked list implimented as a FIFO from above? We’re going to re-do that using the java.util.LinkedList package…

 

   import java.lang.*;
   import java.util.*;

   public class javalist 
   {
       LinkedList list = new LinkedList();
    
       public javalist(LinkedList list){this.list = list;}

       void enqueue(Object o)
       {
	   list.addFirst(o);
       }

       Object dequeue()
       {
           return list.removeFirst();
       }

       boolean isempty()
       {
	   if (list.size() < 1)
	       {
		return true;
               }

	   else
	       {
		   return false;
	       }
       }
   }

Much shorter and simpler than some of the other code we’ve seen, and there should be very little that is completely unfamiliar to you here, but lets go through it just to make sure. Remember that since we are using something from the java.util package, we’ll be needing to import that package to make sure everything we need is available to us.

Top

4.1. Constructor Method

I’m not sure if you’ve ever dealt with constructors in your code before, but if you haven’t here’s the crash course. A constructor is a special type of method that allows us to pass data to a class when we create an instance of that class; it’s very similar to passing data to a method when we call it. All classes have, by default, a constructor that takes no arguments (a no arg constructor). You’ve seen this in action whenever you create an instance of a class. In the above example, LinkedList list = new LinkedList(); without passing any arguments to it. BUT in the case of the javalist class, we want to be able to pass a list already created in a calling program to this class. We do this so the methods we define here will be able to manipulate a copy of the list that we create ni the calling program.

Defining a constructor has some special rules. A constructor has no return type. Don’t confuse this with having a return type of void; when defining a constructor for the class there is no return type. Period. Also, the constructor must have the same package access as the class itself. For the sake of simplicity, I’ve been making these classes public, so any constructor we define must also be public. If you are using a different access level for your class, than the constructor’s package access level must be identical to that of the class.

Once you get past the special restrictions on constructors, this should be as familiar as any other method definition. First we define the input parameters for the method (yes, a constructor is a method). In this case we’ll be expecting to see a linked list. In the body of the method we copy the list that has just been passed into the method (and hence the class) into the list that we created before doing anything else in the class. That’s where this.list = list comes in; this.list refers to the variable that is local to the class, while list refers to the variable that was just passed into the class. If this confuses you too much, then I would suggest doing some reading on classes and inheritance in Java…. hmmmm…. maybe I should make a tutorial about that….. anyway….

Top

4.2. The enqueue(Object o) Method

You will first notice that the enqueue method takes in an Object type as data rather than the char we were using before. Chars are good for cimplicity, but Objects are good for functionality. The LinkedList class was designed to store any type of data, and for that it needs to read in objects.

Top

4.2.1. list.addFirst(o);

The bread and butter of our enqueue method only changes in so much that we are calling a method of the LinkedList class. In this case, we are calling the addFirst() method to add the data we have just enqueued to the beginning of the list.

Top

4.3. The dequeue() Method

This is simple enough. Our dequeue method continues to take no input, and returns items of the sort that we have stored in the list (Objects in this case). Like enqueue, we are actually calling a method that is part of the LinkedList class. Since we keep pushing items into the “first” position in the list, we want to remove them from the last position (and thus we retain the first in first out order). In this case we will simply call the removeLast() method to do our dirty work for us.

Top

4.4. The isempty() Method

For error checking purposes, it is still nice to have a way of telling whether or not our list is empty. Fortunately the LinkedList class keeps track of how many nodes exist in the list at any given point in time. By calling the size() method of the LinkedList class, we can find out how many nodes currently exist (keeping in mind that a node will no longer exist when we have dequeued it. If the value returned by a call to size() is less than one, then we obviously have no nodes in the list, and so it is empty, and thus we return our boolean true. Otherwise, there are nodes in the list, and so we can safely return our boolean false.

If you’re looking for some more information about the LinkedList clas, I would heartily recommend checking out Sun’s online class refference entry for Class LinkedList. It will give you a complete list of the various methods available to you.

Top

5. And They Lived Happily Ever After…

By now you should have a pretty solid understanding of the way a linked list works, the way you can create one from scratch, and some of the ways you can take advantage of the one already built into your Java distro. These data structures are fairly basic, but their flexability makes them a popular choice for maintaining a collection of data that will change during runtime. The linked lists I have discussed here form a solid basis for other sorts of data structures that you will encounter in your travels, so if you still don’t understand, sit back and practice a little bit more. Don’t be afraid to do some more research and ask a few questions, and above all, keep hacking at it.

 Posted on : August 22, 2014
Tags:

You might also likeclose