- Factories and the Recurring Need to Copy Objects
- Linked Java Structures
- Running the Supplied Code
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Linked Java Structures
Linked structures represent one of those areas of programming that strike terror into the hearts of many developers! This of course harks back to the bad old days when procedural languages (such as C and Pascal) were the only development option. One company I worked for even went so far as to issue a blanket ban on the use of pointers in any of its products! So great was the fear of overwriting pointers or accidentally de-referencing null pointers.
In Java, there really aren't such things as pointers in an explicit sense. However, when you want to use linked Java data structures, you get as close to pointers as is possible with this language. For this reason, pointers (or links) provide a powerful tool in the hands of those who understand them.
Continuing the analogy with documents, let's create a simple node type that represents an individual document as illustrated in Listing 10.
public class ALinkedNode
{
private String descriptor;
private int value;
private ALinkedNode linkToNext;
public ALinkedNode()
{
descriptor = null;
value = 0;
linkToNext = null;
}
public ALinkedNode(String newDescriptor, int newValue, ALinkedNode link)
{
descriptor = newDescriptor;
value = newValue;
linkToNext = link;
}
public void setDescriptor(String newDescriptor)
{
descriptor = newDescriptor;
}
public void setValue(int newValue)
{
value = newValue;
}
public void setLink(ALinkedNode newLink)
{
linkToNext = newLink;
}
public String getDescriptor()
{
return descriptor;
}
public int getValue()
{
return value;
}
public ALinkedNode getNext()
{
return linkToNext;
}
}
Listing 10 A Simple Linked Node Class
Every instance of the ALinkedNode class has the following private data members:
- String descriptor;
- int value;
- ALinkedNode linkToNext;
An instance of the ALinkedNode class could represent a single document, such as an invoice. Each object of ALinkedNode has a textual descriptor, a value data member, and a pointer to the next instance of ALinkedNode in the list.
So, the invoice document could point to another document that details the work associated with the invoice. In other words, it's once again a simple document management system modeled as a linked list. Let's now see a class that uses the linked node class; let's look at a linked list class in Listing 11.
public class ALinkedList
{
private ALinkedNode head;
public ALinkedList()
{
head = null;
}
public void addToTop(String descriptor, int value)
{
head = new ALinkedNode(descriptor, value, head);
}
public boolean deleteHeadNode()
{
if (head != null)
{
head = head.getNext();
return true;
}
else
return false;
}
public void displayList()
{
ALinkedNode position = head;
System.out.println("Start of linked list:");
while (position != null)
{
System.out.println(position.getDescriptor() + " "
+ position.getValue());
position = position.getNext();
}
System.out.println("End of linked list.");
}
public boolean isEmpty()
{
return (head == null);
}
public static void main(String[] args)
{
ALinkedList list = new ALinkedList();
list.addToTop("Invoice", 1);
list.addToTop("Receipt", 2);
list.addToTop("Statement", 3);
list.displayList();
list.deleteHeadNode();
while (list.deleteHeadNode())
;
list.displayList();
}
}
Listing 11 A Linked List Class
The code in Listing 11 is fairly straightforward. Each instance of ALinkedList contains a private data member called head that points to the beginning of the linked list. All manipulation of the list class (ALinkedList) makes use of the head data member. Perhaps, the most difficult use of head is in the method addToTop():
head = new ALinkedNode(descriptor, value, head);
This line instantiates a new object of the class AlinkedNode and assigns the current value of head to its linkToNext data member. It's instructive to consider the method deleteHeadNode(), which contains the code in Listing 12.
if (head != null)
{
head = head.getNext();
return true;
}
else
return false;
Listing 12 Reassignment of head
It's perhaps not entirely obvious from Listing 12, but the following line goes to the very heart of Java:
head = head.getNext();
What happens here is that the object head is updated so that it points to the next item in the list. This means that the original item pointed to by head goes out of scope. Once this happens, the object has (correctly) leaked out of your program (in C or C++, this situation is an error that is often extremely difficult to find)! The garbage collector will then at some point return the memory from this object. So, from your perspective the original entity pointed by head has disappeared.
The other methods in Listing 11 relate to the display of the linked list members and checking if the list if empty or not.