Author Archives: dan

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>();

Grammar Pointers and tips

I’ve learned a few things about grammar over the years, and I often forget them. I made this as a reminder of some grammar pointers and tips. Please bear in mind that I am not an expert on the English language, I just found these on my travels and have adopted them in my writing (where I remember!).

  1. Be tolerant.

  2. Be consistent.

  3. Don’t split infinitives.

  4. Don’t end sentences with a preposition.

  5. A list is a part of a sentence or it is not.

  6. It’s its own enemy.


 

Tip number 1: it’s not always a hard rule so be tolerant.

With grammar, it’s tempting to say “I’m right, you’re wrong,” and be righteously indignant should anyone choose to challenge your view. I think that a more tolerant approach is better. As an example:

In the tech industry, you may hear this a lot: “This data is huge”. Since “data” is the plural of “datum”, this should really be “These data are huge”. But that may not always be correct. If you choose the former, what you’re probably trying to say is that there are a lot of items in a set of data. If you say the latter, you may actually be understood to mean “each of the items in the data set is huge”. This is a case where going with the norm is probably sensible.

Tip number 2: be consistent in your grammar choices.

If you are going to be pedantic about grammar, you’d best be consistent. It’s all very well adopting your own style, but it should be something you own. If you insist on swimming upstream, you have to keep swimming upstream (thanks Dory).

Tip number 3: don’t split infinitives.

Wikipedia has a nice article on infinitives which explains what an infinitive is. I’ll explain it by way of example here. You’ve probably heard the famous saying from Star Trek: “to boldly go”. You may also have heard that it’s grammatically incorrect. The infinitive here is “to go”. By placing the adverb “boldly” in between “to” and “go”, we’re splitting the infinitive. It should really be “to go boldly”.

Tip number 4: don’t end sentences with a preposition.

A preposition indicates the position of an object: on, in, under, and so on. Though it’s not a hard rule (see tip number 1), it’s better not to end a sentence with a preposition. So instead of  “the box I sat on”, you can write “the box upon which I sat.” and instead of “the person I was talking with”, write “the person with whom I was talking”. Sometimes moving sentences around like this can result in a silly-sounding sentence, so use your discretion.

Tip number 5: a list is a sentence or it is not.

Often in email and technical writing, we use lists to get our message across more quickly. Personally, I love bulleted lists – they help me be more succinct and get to the point quicker. But lists are so often mistreated. The rule is simple: either you treat the list as part of a larger sentence or you treat the list as a set of individual sentences.

The following is an example of a list of items.

  • Each item in the list is a sentence, so start with a uppercase letter and end with a full-stop (or period if you’re American).
  • See, this item is also its own sentence.
  • Lastly, this is also a sentence.

Or you could do it this way:

  • where each item in the list is part of the larger sentence;
  • each item ends with a semi-colon;
  • the preceding sentence ends in a colon;
  • and there’s no need to start each item with an uppercase letter;
  • your penultimate list item should have “and” after the semicolon; and
  • you must finish the last item (and hence the bigger sentence) with a full-stop (or period if you’re American).

This is not the right way:

  • This looks like a sentence
  • But there is no punctuation
  • And there uppercase letters in the wrong place

Tip number 6: it’s its own enemy.

Usually, when you use an apostrophe, you use it in one of two situations:

  • to indicate ownership: for instance “Dan’s handwriting is terrible”; or
  • to indicate contraction: for instance “don’t try to make sense of that handwriting”.

Of course there are exceptions, and the definite article “it” is one exception.

  • Its means “it owns”. “Its car” means “the car belonging to it”.
  • It’s means “it is”. “It’s a car” means “It is a car”.

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 Javascript

Seeing as I’d implemented the linked list in Java (an OO language) and Python (an OO/procedural mix), I thought it would be fun to implement the linked list in Javascript. This was certainly a fulfilling experience. At the onset, JavaScript had always been very procedural – you write some code to do some DOM-like things like getting field values from HTML form elements. But I have some interesting findings. Javascript turns out to be a little more than procedural. Javascript is prototype-based. Classes simply don’t exist in Javascript (as they would in an OO language). In Javascript, there is no distinction between the Class (which is the blueprint for instances and contains behaviour and structure) and the Object (which is an instance of the Class). No – in Javascript, it’s all the same. A function is a higher-order element, which means that a function can be made into an object by instantiating the function. In this way, the function acts as a constructor, and the resulting object is an instance. The function can contain attributes and it can contain other functions. When an object has been instantiated, it is possible to modify the prototype of the object (and all subsequent instance of the object for a particular run). This means you can change the “Class” definition as you go.

Javascript also has a notation for expressing objects as literals (which is quite nifty and very easy to read).

For my implementation of the linked list in Javascript, I created a function called LinkedListNode, which contained node data (data and next) and a function called LinkedList, which contained the first and last node and size, as well as functions to add, remove, check position, check size and get a string representation.

I’ve only implemented this for strings, and I’ve only tested it in Mozilla Firefox for Mac OS X. If you have a different setup, and it doesn’t work for you, I’d love to hear from you!

The code and unit tests are available in my GitHub repository. I also created my own Unit Testing framework for this one (it’s called UnitTestFramework.js).

Part 1: The LinkedListNode object
The list node is simply the data and a reference to the next node. The values for these properties are set to null when the object is instantiated.

function LinkedListNode() {
  this.data = null;
  this.next = null;
}

Part 2: The LinkedList object
The linked list class has a first and last node reference and a size.

function LinkedList() {
  this.firstNode = null;
  this.lastNode = null;
  this.size = 0;
}

Part 3: The add() function
The add method replaces the lastNode reference with the node being added and makes the old last node reference the new node as the next node in the list.

this.add = function(data) {

    var newNode = new LinkedListNode();
    newNode.data = data;

    if (this.firstNode == null) {
      this.firstNode = newNode;
      this.lastNode = newNode;
    }
    else {
      this.lastNode.next = newNode;
      this.lastNode = newNode;
    }

    this.size++;
  }

Part 4: The remove() function
The remove method iterates the list looking for the node to delete. We actually look ahead in the list because we need to loop around the deleted node by having the previous node point to the following node as its next node.

this.remove = function(data) {
    var currentNode = this.firstNode;

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

        var wasDeleted = false;

        /* Are we deleting the first node? */
        if (data == currentNode.data) {

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

          currentNode.data = null;
          currentNode = currentNode.next;
          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 */
            var nextNode = currentNode.next;
            if (nextNode != null) {
                if (data == nextNode.data) {

                    /* Found the right one, loop around the node */
                    var nextNextNode = nextNode.next;
                    currentNode.next = nextNextNode;

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

            currentNode = currentNode.next;
        }

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

Part 5: The helper function(s)
The getSize(), indexOf() and toString() functions are provided to make things more useful.

this.getSize = function() {
    return this.size;
  }

  this.indexOf = function(data) {
    var currentNode = this.firstNode;
    var position = 0;
    var found = false;

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

            if (data == currentNode.data) {
              found = true;
                break;
            }

            currentNode = currentNode.next;
        }

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

        return position;
  }

  this.toString = function() {
      var currentNode = this.firstNode;

      result = '{';

      for (i = 0; currentNode != null; i++) {
        if (i > 0) {
          result += ',';
        }
        var dataObject = currentNode.data;

        result += (dataObject == null ? '' : dataObject);
          currentNode = currentNode.next;
      }
      result += '}';

      return result;
  }


					

The linked list in Python

This was my first attempt at a Python script. Actually, I lie. I’ve tried before, but lost interest after a little bit. Not sure why, because Python is fun, fun, fun! I did have to think a little bit before getting into it, but once I got going, it was smooth sailing. As with my Java Linked List, I used a Unit Testing framework, thanks to Python’sunittest package. It’s easy peasy. Oh, and of course, I used Eclipse with the great PyDev plugin for Python scripting.

One of the things that caught my eye with the Python linked list is that I did not need to declare the member variables for the class. I can simply set them, and the class magically knows about them. That’s pretty cool. In addition, what I would call a coding style of indentation has semantic meaning in Python: instead of blocks being enclosed in braces, they’re indented. Otherwise, no massive issues to report.

So, as you would expect, the linked list implementation has O(1) insert (because we insert at the end of the list) and O(n) delete (because we need to iterate the entire list to find the right node to delete). The other operations I’ve provided are add, remove, get_size, index_of, contains and to_string.

Note: I’ve only tested this implementation with strings. Python doesn’t have the same capability as Java with something like the equals() method. The rules for object comparison may make containing objects of arbitrary types in the list a little tricky. An excerpt from the Python documentation: “Most other types compare unequal unless they are the same object; the choice whether one object is considered smaller or larger than another one is made arbitrarily but consistently within one execution of a program.

The code and unit tests are available in my GitHub repository.

Part 1: The LinkedListNode class
The list node is simply the data and a reference to the next node. It’s stored in its own source file and is a class. The member variables holding the data and next are initialised in the __init__ method.

class LinkedListNode:

    def __init__(self, inData, inNext):
        """Construct a new Linked List Node"""
        self.data = inData
        self.next = inNext

Part 2: The LinkedList class
The linked list class has a first and last node reference and a size. We import the LinkedListNode class from its source file.

from com.danielacton.datastructures.LinkedListNode import LinkedListNode

class LinkedList:

    def __init__(self):
        """Construct a new LinkedList. The first node and last node are the same. Size is 0"""
        self.firstNode = LinkedListNode(None, None)
        self.lastNode = self.firstNode
        self.size = 0

Part 3: The add() method(s)
The add method replaces the lastNode reference with the node being added and makes the old last node reference the new node as the next node in the list. There are 2 add methods, one to add a single node and one to add multiple nodes (with a Python list being used to pass values to add in the latter method).

def add(self, data):
        """Add a node to the list"""
        node = LinkedListNode(data, None)
        node.data = data;

        if self.firstNode.data == None:
            self.firstNode = node
            self.lastNode = node
        else:
            self.lastNode.next = node
            self.lastNode = node

        self.size += 1

    def add_many(self, list_of_data):
        """Add a list of nodes to the linked list"""
        for x in list_of_data:
            self.add(x)

Part 4: The remove() method(s)
The remove method iterates the list looking for the node to delete. We actually look ahead in the list because we need to loop around the deleted node by having the previous node point to the following node as its next node. There are 2 remove methods, one to remove a single node and one to remove multiple nodes (with a Python list being used to pass values to remove in the latter method).

def remove(self, data):
        """Remove a node from the list"""
        currentNode = self.firstNode
        wasDeleted = False

        if self.size == 0:
            pass

        # The first node is being removed
        if data == currentNode.data:
            # This is the case where we have only one node in the list
            if currentNode.next == None:
                self.firstNode = LinkedListNode(None, None)
                self.lastNode = self.firstNode
                self.size = self.size - 1
                return

            # Here there are more than one nodes in the list
            currentNode = currentNode.next
            self.firstNode = currentNode
            self.size = self.size - 1
            return;

        while True:

            if currentNode == None:
                wasDeleted = False
                break

            # Check if the data of the next is what we're looking for
            nextNode = currentNode.next
            if nextNode != None:
                if data == nextNode.data:
                    # Found the right one, loop around the node
                    nextNextNode = nextNode.next
                    currentNode.next = nextNextNode

                    nextNode = None
                    wasDeleted = True
                    break

            currentNode = currentNode.next

        if wasDeleted:
            self.size = self.size - 1;

    def remove_many(self, list_of_data):
        """Remove a list of nodes from the linked list"""
        for x in list_of_data:
            self.remove(x)

Part 5: The helper method(s)
The to_string(), contains(), index_of and get_size() methods are provided to make things more useful.

def to_string(self):
        """Get a string representation of the list"""
        result = ""
        currentNode = self.firstNode
        i = 0

        result = result + "{"

        while currentNode != None:
            if i > 0:
                result = result + ","

            dataObj = currentNode.data

            if dataObj != None:
                result = result + dataObj

            currentNode = currentNode.next

            i = i + 1

        result = result + "}"
        return result

    def contains(self, data):
        """Check whether a node is in the list or not"""
        currentNode = self.firstNode

        while currentNode != None:
            if currentNode.data == data:
                return True
            else:
                currentNode = currentNode.next

        return False

    def index_of(self, data):
        """Find the position of a node in the list"""
        currentNode = self.firstNode
        pos = 0

        while currentNode != None:
            if (currentNode.data == data):
                return pos
            else:
                currentNode = currentNode.next
                pos = pos + 1

        return -1    

    def get_size(self):
        """Get the size of the list"""
        return self.size

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;
      }