Category Archives: Java

Generics in Java

In some recent posts, I’ve created generic data structures in Java (see Linked List and Hashtable). When I say generic, I mean you could store any type of data in the data structure. That’s true since it uses an Object as its data type, and all classes extend Object. However, you might fall foul of some typing errors.

For example, let’s say create a LinkedList and add a String to it. Then you forget it’s supposed to be a list of Strings, and you add an object of type Car to it. Car and String are not the same and there may be issues down the line when you assume that your LinkedList contains only a single type, for example if you try iterate the list and call the getNumberOfDoors() method on a String object (that you thought was a Car object) – you’d get an exception of some sort.

Java has supported Generics for some time now, and I thought it was time to add support for Generics into my data structures. This means that it’s more type safe. When you create an object of type LinkedList, you tell it that you want it to hold Strings, and if you try add a Car, it will give you a compile-time error; so fewer run-time issues related to type assumptions.

In general, here are a few pointers about adding support for Generics to your own classes. The examples in my Github repository already have this.

– Tell your class that it’s generic. In the class declaration, use angle-brackets and letters of your choice to denote any type. You can indicate that you expect the type to have a certain super-type or implement a certain interface. In this case, I’d like all data added to be of the same type and to implement Comparable (and Comparable with generics is Comparable of course).

public class LinkedList<T extends Comparable<T>>
public class Hashtable<K extends Comparable<K>, V extends Comparable<V>>

– Your data variable(s) should be generic types. Use the same letter as you chose when declaring the class.

private ListNode<T> firstNode;

– Change your methods to accept/return generic types.

public void add(T inputData)

– Change any internal references to constructors to use generics.

ListNode<T> node = new ListNode<T>(inputData);

– Instantiate your class like any other generic data type.

LinkedList<String> list = new LinkedList<String>();
Hashtable<String, String> table = new Hashtable<String, String>();

The hashtable in Java

The hashtable is a nice little data structure. It’s useful for storing arbitrary objects in quick time and accessing them just as quickly. The hashtable relies on a hash function. The basic concept of a hash function is that, given some item to store, you can calculate an integer value. So, for example, we would map the value “HashMe” to 53. It’s not necessary to be able to convert back again (from 53 to “HashMe”, for example). The only real requirement is that the hash function must be able to make an integer out of any item you wish to store. This hash function is ultimately used to arrive at an array index. The hash table would have an array backing it, which would contain the data. This array would have a fixed size (actually, there would be some value in being able to “rebalance” an array once it got too full), and the hash value that is calculated for an item would be fit into this array’s bounds courtesy of the modulo function. So, we have the ability to place an item in an array position.

There is one thing to think about though. It is possible (actually probable, if your backing array is small) that two items being added to the hash table would have the same array position calculated for them. In this case, you have a choice. Either you can find the next open array position, or you can use another data structure to store all elements at the same array position. What’s that I hear you say? Could we use a linked list? Yes! I answer you with all my ferve and vigour (ferve may not be a word, but fervour didn’t sound right). Try the Linked List implementation at The Java Linked List. The former approach is called linear probing and the latter is called chaining. Something interesting to note is that if you use a linear probing approach, you would eventually run out of open spots in your backing array and would need to resort to chaining anyway.

The hash function can be anything (you could just set it to 1 for all items, but then it would just be a linked list, and has no value).

Note that items are stored in the table as key-value pairs. So when you add an item, it uses the key to get the hash and hence position.

The Java implementation I’ve done here has a few core operations (we use an array as backing, and we use a linked list for chaining to overcome collisions):

  • add: adding an element to a hashtable is of O(1) complexity, because it’s a case of calculating the hash and then putting the element in the array (or adding it to the linked list, which is also O(1)
  • remove: removing an element is also of O(1) complexity because the location of the element is done by hashing, and then just traversing the list at that position in the table.
  • hash: this calculates the array position for an element. It basically uses the element’s toString() method (all Java Objects have one) and adds up the ASCII values of the characters in the string. For characters between a and f, we use the hex value instead.
  • contains: this operation gets the hash of the element and then looks in the appropriate array element. If there is one, the linked list in that array position is traversed.
  • getNumElements: this operation shows how many elements are in the array
  • toString: returns a string representation of the hashtable

So, the hashtable implementation I have produced here is in Java. I’ll explain the parts of importance. The full source is available in my GitHub repository.

Part 1: The hash table node class
As I mentioned, the hash table is a set of nodes referenced by key. The hash table node, then, contains only 2 things: an Object containing the key and an Object containing the data to store. I chose to make the HashtableNode class a private inner class because I don’t need classes outside of the Hashtable class accessing the HashtableNode class. The HashtableNode class is basically a Java Bean which contains a constructor, an Object representing the key referencing the data and an Object containing the data stored in the node, and getters and setters for these member variables. In addition, because we’ll be storing the nodes in a linked list because of the chaining to manage collisions, there is an equals() method. A utility toString() method is also provided.

Something to note is that the equals() method only checks the equality of the key to determine whether two instances are the same. The reason for this is that in a Hashtable, there is no duplication of keys — if a key/value pair already exists in the Hashtable, it is not added again.

public class Hashtable {
  private class HashtableNode {
    private Object key;
    private Object data;

    public HashtableNode() {
      this.key = null;
      this.data = null;
    }

    public HashtableNode(Object inKey, Object inData) {
      this.key = inKey;
      this.data = inData;
    }

    public Object getData() {
      return data;
    }

    public void setData(Object data) {
      this.data = data;
    }

    public Object getKey() {
      return key;
    }
    public void setKey(Object key) {
      this.key = key;
    }

    /* Equality can be based on key alone because there can't be
     * 2 nodes with the same key in the table */
    public boolean equals(Object obj) {
      if (obj instanceof HashtableNode) {
        HashtableNode node = (HashtableNode)obj;
        return this.key.equals(node.getKey());
      }
      else {
        return false;
      }
    }

    public String toString() {
      return "Key: ["+this.key+"] data: ["+this.data+"]";
    }
  }
}

Part 2: The backing table
The backing table I’ve used is an array of fixed size. The tableSize member variable in this implementation is fixed, although you could have a dynamically calculated backing array size, which grows when needed to avoid excessive chaining. There is a difference between the number of elements in the hash table and the size of the hash table – there could be 20 positions in the backing array, but only 1 of them has any data in it. The backing array in this implementation is an array of Java Objects (actually, it will end up being an array of LinkedLists).

private final int tableSize = 20;
  private int numElements;
  private Object [] table;

Part 3: The hash method

In my implementation, I’ve chosen to have use Java’s toString() method that exists for any Object. If a class does not define a toString() method, it will use the one defined in java.lang.Object. This method returns things like “com.danielacton.datastructures.LinkedList@12345″, which is fine, because it’s a string. So we’re guaranteed to have a string from our element to store. The hash method adds up the ASCII values of the characters in the string. For characters between a and f, we use the hex value instead. Once we’ve got a number, we find the modulus of the number with the table size so that we can fit into the backing array.

private int hash(Object key) {

    /* Start with a base, just so that it's not 0 for empty strings */
    int result = 42;

    String inputString = key.toString().toLowerCase();

    char [] characters = inputString.toCharArray();
    for (int i = 0; i < characters.length; i++) {
      char currentChar = characters[i];

      if (currentChar == 'a' || currentChar == 'b' || currentChar == 'c' ||
        currentChar == 'e' || currentChar == 'e' || currentChar == 'f') {
          result += Integer.parseInt(""+currentChar, 16);
      }

      int j = (int)currentChar;
      result += j;
    }

    return (result % this.tableSize);
  }


Part 4: The add method(s)

To add an element to the hash table, we find the position in the backing array using the hash() method on the key. Then, if there is a linked list already in that position, we append to it by creating a new HashtableNode object and setting the key and data provided and adding that to the list. If there is no linked list in that position, we create one and then add the HashtableNode to it. There are 2 add methods: one that adds a single element and one that adds multiple elements by calling the single add method many times.


public void add(Object key, Object data) {
    if (data == null || key == null) {
      System.err.println("ERROR: Either the key or the data are null");
      return;
    }

    /* Don't add duplicate keys */
    if (this.contains(key)) {
      return;
    }

    /* Find out where in our array should the item go */
    int position = this.hash(key);

    /* If nothing exists in the position, create a new linked list there */
    if (this.table[position] == null) {
      this.table[position] = new LinkedList();
    }

    /* Add to the linked list in the appropriate position*/
    ((LinkedList)this.table[position]).add(new HashtableNode(key, data));
    this.numElements++;
  }

  public void add(Object [] keys, Object [] inputData) {
    for (int i = 0; i < inputData.length; i++) {
      this.add(keys[i], inputData[i]);
    }
  }




Part 5: The remove method(s)

To remove an element from the hash table, we find the position in the backing array using the hash() method on the key provided. Then, if there is a linked list already in that position, we remove the element from it. If there is no linked list in that position, the element does not exist in the hash table so we do nothing. There are 2 remove methods: one that removes a single element and one that removes multiple elements by calling the single remove method many times.


public void remove(Object key) {
    int hashVal = this.hash(key);

    if (this.table[hashVal] != null) {
      HashtableNode node = new HashtableNode();
      node.setKey(key);

      if (((LinkedList)this.table[hashVal]).indexOf(node) > -1) {
        ((LinkedList)this.table[hashVal]).remove(node);
        this.numElements--;
      }
    }
  }

  public void remove(Object [] keys) {
    for (int i = 0; i < keys.length; i++) {
      this.remove(keys[i]);
    }
  }


Part 6: The helper methods

There are a few helper methods I’ve included. contains tells if an element exists in the hash table. toString gives a string representation of the hash table. numElements shows how many elements are in the hash table.


public String toString() {
    StringBuffer buffer = new StringBuffer();

    buffer.append(System.getProperty("line.separator"));
    buffer.append("{");
    buffer.append(System.getProperty("line.separator"));

    for (int i = 0; i < this.table.length; i++) {
      if (this.table[i] != null) {
        buffer.append("\t"+(LinkedList)this.table[i]);
        buffer.append(System.getProperty("line.separator"));
      }
    }

    buffer.append("}");

    return buffer.toString();
  }

  public int getNumElements() {
    return this.numElements;
  }

  public boolean contains(Object key) {
    boolean result = false;
    int hash = this.hash(key);

    if (this.table[hash] != null) {
      HashtableNode node = new HashtableNode();
      node.setKey(key);
      if (((LinkedList)this.table[hash]).indexOf(node) > -1) {
        result = true;
      }
    }

    return result;
  }


 


					

		
		
	


	

				

			
						

				The linked list in Java
			

								


				

			
I have always liked the linked list so I decided to put together linked list implementations in my favourite programming languages. This post is about a linked list implementation in Java. I am not claiming it is the most efficient or best (or even most correct) implementation, but it conveys the basic ideas.


In general, a linked list consists of a set of nodes. Each node has some data and a link to the next node. When the link to the next node points to nothing, you’ve reached the end of the list. Simple, innit? We keep 2 references: one to the start of the list and one to the end of the list. This way, adding a node is quick.


The basic linked list I’ve written contains these operations:


    

  • add: Add an item (or array of items) to the end of the list. Adding an item to this list in this simple implementation is O(1) in Big O notation because we keep a reference to the last node in the list and simply append to it.
    • 

  • remove: Remove an item (or array of items) from the list. Items are located by equality. Complexity for removal is O(n) because the the list is iterated from the first element to the last, testing each item for equality.
    • 

  • indexOf: Indicates the position of an item in the list, returning -1 if not found. Again, O(n) because of the list being iterated.
    • 

  • size: Shows the number of items in the list. O(n) because of iteration.
    • 

  • toString: Gives a string representation of the list.
    • 

  • elementAt: Gives the position in the list of an element.
    • 



So, the linked list implementation I have produced here is in Java. I’ll explain the parts of importance. The full source is available in my GitHub repository.


Part 1: The list node


As I mentioned, the linked list is a sequence of nodes that are linked together. The list node, then, contains only 2 things: an Object containing the data item and a list node representing the next node in the list. I chose to make the ListNode class a private inner class because I don’t need classes outside of the LinkedList class accessing the ListNode class. The ListNode class is basically a Java Bean which contains a constructor, an Object representing the data stored in the node and a ListNode representing the next node in the list, and getters and setters for these member variables.


public class LinkedList {

          private class ListNode {

          private Object data;
          private ListNode next;
  
          public ListNode() {
            this.data = null;
            this.next = null;
          }

          public ListNode(Object inputData) {
            this.data = inputData;
            this.next = null;
          }

          public Object getData() {
            return data;
          }

          public void setData(Object data) {
            this.data = data;
          }

          public ListNode getNext() {
            return next;
          }

          public void setNext(ListNode next) {
            this.next = next;
          }
        }
      }




Part 2: The add() method(s)


To add a node to the list, it’s as simple as creating a new node, setting the next node of the old last node to the new node and setting the new last node to the new node. There are 2 add methods: one adds a single item and the other adds an array of items by calling the method that adds a single item multiple times.


public void add(Object inputData) {
        ListNode node = new ListNode(inputData);

        /* Make sure we cater for the case where the list is empty */
        if (this.firstNode.getData() == null) {
          this.firstNode = node;
          this.lastNode = node;
        }
        else {
          this.lastNode.setNext(node);
          this.lastNode = node;
        }

        this.size++;
      }

      public void add(Object [] inputArray) {
        for (int i = 0; i < inputArray.length; i++) {
            this.add(inputArray[i]);
        }
      }


Part 3: The remove() method(s)


In order to remove an item from the list, we start at the beginning of the list and go to the next node in the list, checking the data in each node against what we are looking for, until we find a node that contains data that matches what is being searched for (or the end of the list is reached in which case nothing is done). We have to look ahead in the list though, because we really need to find the node before the matching node because we need to make sure that the previous node of the matching node now points to the next node of the matching node (effectively removing the matching node from the list). Think of it as bypass surgery for linked lists. Incidentally, this would be a lot easier with a Double linked list which has a pointer to next and previous. Perhaps I’ll implement it soon.

There are 2 remove methods: one removes a single item and the other removes an array of items by calling the method that removes a single item multiple times.


public void remove(Object inputData) {
        ListNode currentNode = this.firstNode;

        if (this.size == 0) {
          return;
        }

        boolean wasDeleted = false;

        /* Are we deleting the first node? */
        if (inputData.equals(currentNode.getData())) {

          /* Only one node in list, be careful! */
          if (currentNode.getNext() == null) {
            this.firstNode.setData(null);
            this.firstNode = new ListNode();
            this.lastNode = this.firstNode;
            this.size--;
            return;
          }

          currentNode.setData(null);
          currentNode = currentNode.getNext();
          this.firstNode = currentNode;
          this.size--;
          return;
        }

        while (true) {
          /* If end of list, stop */
          if (currentNode == null) {
            wasDeleted = false;
            break;
          }

          /* Check if the data of the next is what we're looking for */
          ListNode nextNode = currentNode.getNext();
          if (nextNode != null) {
            if (inputData.equals(nextNode.getData())) {

              /* Found the right one, loop around the node */
              ListNode nextNextNode = nextNode.getNext();
              currentNode.setNext(nextNextNode);

              nextNode = null;
              wasDeleted = true;
              break;
            }
          }

          currentNode = currentNode.getNext();
        }

        if (wasDeleted) {
          this.size--;
        }
      }

      public void remove(Object [] inputArray) {
        for (int i = 0; i < inputArray.length; i++) {
          this.remove(inputArray[i]);
        }
      }


Part 4: The helper method(s)


A linked list wouldn’t be much use if we didn’t have a way of checking its size, seeing what it contained and searching for items in the list.

Luckily we’ve kept track of size with adds and removes.


public int size() {
        return this.size;
      }


Printing the list is a case of iterating the list and printing the data items as we go.


public String toString() {
        ListNode currentNode = this.firstNode;
        StringBuffer buffer = new StringBuffer();

        buffer.append("{");
        for (int i = 0; currentNode != null; i++) {
          if (i > 0) {
            buffer.append(",");
          }
          Object dataObject = currentNode.getData();

          buffer.append(dataObject == null ? "" : dataObject);
          currentNode = currentNode.getNext();
        }
        buffer.append("}");
        return buffer.toString();
      }


Searching for contents is a case of iterating the list and checking the data item for equality (and counting items) as we go.


public Object elementAt(int inputPosition) {

        if (inputPosition >= this.size || inputPosition < 0) {
          return null;
        }

        ListNode currentNode = this.firstNode;

        for (int position = 0; position < inputPosition ; position++) {
            currentNode = currentNode.getNext();
        }

        return currentNode.getData();
      }

      public int indexOf(Object inputData) {
        ListNode currentNode = this.firstNode;
        int position = 0;
        boolean found = false;

        for (; ; position++) {
          if (currentNode == null) {
            break;
          }

          if (inputData.equals(currentNode.getData())) {
            found = true;
            break;
          }

          currentNode = currentNode.getNext();
        }

        if (!found) {
          position = -1;
        }
        
        return position;
      }