A Different Form of Data Management

The Concept of Linked Lists

To this point, you have been using arrays as your go-to data structure. Arrays are a good fall back in the sense that you can put pretty much any data, whether primitive or object, into an element, and find it later at the index at which you placed it. Simply put, arrays are pretty good tools, with maybe a couple of issues. The first one is that arrays are limited to the capacity given to them. You can make arrays with adjustable capacities but that takes quite a bit of overhead when transferring from the old array to the new one, and can become a big problem when there are a million, or a billion, elements in the array.

The linked list offers a little more flexibility. You can keep adding new data quantities for as long as you have available memory, which is essentially limitless with Operating Systems these days. Each data quantity, which we will now call a node instead of an element, is created at the point of storing the data, and then it is added to the list in a process called linking. Like an array element, a node can be added, appended, or inserted at any location in a linked list. This will be discussed in the next topic. The bottom line is that this is a new paradigm; you need to think about your data as linked nodes instead of a set of large indexed elements.

The Concept of Dynamic Memory Access

As mentioned, an array is something you create or instantiate prior to its use. This is considered to be statically defined, meaning it is created once and never changes as the data structure. Even when arrays are resized, the original array is not actually resized but instead a new array is (statically) created to replace the old one. In the case of linked lists, and other data structures you will work with later on, a node is created at point of being used. This is considered dynamic memory allocation, or "on the fly" memory allocation that happens at the point in the code where it is requested. The first step in this process is to instantiate a node, shown here being assigned to a reference variable.

     nodeReference = new NodeClass( "Susan Sarenvo" );

There are a few things to discuss about this. First the variable nodeReference must be a reference of type NodeClass to be able to "refer to" or "point at" any NodeClass object. The nodeReference variable was declared as follows.

     NodeClass nodeReference;

It is critical for you to remember that any reference declared as a given class type can "refer to" or "point at" any object of that class type. So, as declared, the nodeReference can point at any NodeClass object. This will become very important very soon. As a result of this, for us to have a linked list, we must always start with a head reference which will refer to the first node in the list. The head reference will almost always be a member variable in whatever linked list class within which you are working. This means that somewhere in your linked list class, there will be the following code. Note that this might occur more than once depending on the actions your linked list is capable of. Since we always think of references as pointers to objects, you can think of the head reference this way.

Creating a head reference is pretty straightforward, as shown here.

     NodeClass headRef;

Note that the data type could be any kind of object. In this class, the class type NodeClass is used.

In most cases, a head reference will be set to null when the object is first constructed, so we can think of it this way.

The sideways 'T' will always be our way of representing null. null itself simply means the reference is pointing at a standard value that is NOT an object, and the way this is implemented should be pretty obvious.

     headRef = null;

It is very important that you recognize that reference variables do not "hold" data like primitive variables do. Instead they "hold" the address of where an object is located in memory. A reference is just a reference, aka a pointer (Don't tell anybody the pointer term was used; you aren't supposed to say "pointer" in Java - it's a long, boring story).

So with that in mind, how do you start a linked list? Well, you create a node, put data in it, and assign the head reference to the node. An example was provided above with a generic reference. Here it is again being assigned to the head reference, and becoming the first node in the linked list.

     headRef = new NodeClass( "Susan Sarenvo" );

The linked list would now look like the following.

Now that we have come this far, you need a little background support.

The Node Itself

In this case the NodeClass stores a String name. Nodes can store one or more items that are considered the data of the given node. However, a linked list node must also have a "next" link that can refer to the next node in the list, or to null if there is no subsequent node. Let's take a quick walk through what a node is, or could be.

   public class NodeClass
      {
       String nodeData;     
       NodeClass nextRef;

       /**
       * Initialization constructor for NodeClass
       * @param newData integer value to be placed in node
       */
       public NodeClass( String newData )
           {
            nodeData = newData;
            nextRef = null;
           }

       /**
        * Initialization constructor for NodeClass
        * @param copied NodeClass object to be copied into this node
        */
       private NodeClass( NodeClass copied )
          {
           nodeData = copied.nodeData;    
           nextRef = null;
          }
      }

• The first thing to note is that this is a public node class. That means it must be in a file by itself. It is also possible for this class to be private and maintained inside another public class that would likely be the linked list class


• The next thing to note is that there is usually some kind of initialization constructor and some kind of copy constructor. This is very common for nodes as that allows the data to be placed in the node at the same time the node is first instantiated, as you observed in the headRef assignment earlier


• The next thing to note is that, as mentioned previously, the node itself will always hold some form of data and some form of "next" link. In this case, the nextRef variable is a reference of type NodeClass so it can refer to other nodes of its own kind


• The last thing to note, at this point, is that in the constructor, the nextRef link will always be set to null

This is just the beginning but these observations are important.

And Now, Let's Link

The first node has been added to the linked list. That was easy, it was just assigned to the head reference. However, once the head reference has been linked to the first node, it must maintain its reference to the first node no matter how far down the list you go. Let's look at adding the next data item (node).

     headRef.nextRef = new NodeClass( "Roger Rolanda" );

That wasn't very hard. The linked list now looks like the following.

When the headRef used the dot operator to access the nextRef, which is a reference to a NodeClass, it connected the second node to the first node. Again note that every new node starts with its nextRef refering to null. And now we have a linked list of two nodes.

Now comes the conundrum. It might seem like the next thing to do would be to assign the head references' next reference's next reference to the next item, as shown here.

     headRef.nextRef.nextRef = new NodeClass( "Julie Jazamina" );

It should be noted that this does actually work. However, you can see where that would go. After the first thousand, or even hundred of these, your code would be, let's say, awkward at best, with all the nextRef dot operations. This has to be done differently. You know that you cannot change the head reference. It must always stay in position referring to the first node. This calls for using another reference, like the following.

     NodeClass wkgRef = headRef;

This variable is declared and assigned in the same statement but you should know that you could do this in two steps. But what has happened here? The wkgRef reference is now referring to the same thing as the head reference, shown here graphically.

And how does that help us? Well, we cannot change the headRef; it must always keep referring to the first node. However, we can change the wkgRef, and it is easy to do, as you can see here.

     wkgRef = wkgRef.nextRef;

Here you are telling the working reference to be assigned to the next reference of the object it is referring to. Stop and think about this as needed. It is referring to the first object (node), but you are asking it to now be assigned to the first object's/node's next reference. It will now refer to the next node, as shown here.

How's that for cool? Like any other NodeClass reference, the wkgRef can refer to or point at any NodeClass node so we now have a way to manage individual nodes across a list of any size. For example, we can write the following code.

     wkgRef.nextRef = new NodeClass( "Julie Jazamina" );

And we will get the following.

You should now see how you could use a loop to move wkgRef up to the next node, and then add another one, or sometimes just look at one to see if you can use the data stored there. There are no indices here, and there is only one way to access a linked list. That is to start with the head reference, and then increment your working reference across the list until you want to read or replace a node, search for one, or even insert or remove a node. Again, pretty cool.

Linked Lists, The Concept

This topic has supported your introduction to the concept of linked lists. In the next few topics, you will look at how to add and remove data from a linked list, and you will even view a couple of linked lists that don't look quite the same as this one. As always, there is only one way to learn how to program . . . and that is to program. As you are exposed to the different strategies for manipulating linked lists, you need to practice each and every one of them, multiple times. When you do this, you will find that thinking about linked lists is just as natural as thinking about arrays, you will be more comfortable and confident, and you will be able to develop your own linked lists. All good. Keep at it.