Sending emails with SMTP

In this post, I'm going to show you how to send an email from the command-line without needing any sort of email client. We're going to be using a protocol called SMTP, which stands for Simple Mail Transport Protocol. This is the protocol that millions of email servers all over the world use to send emails to one another. The protocol is made up of a number of text-based commands and it actually is pretty simple. :-P

For this demonstration, let's send an email to ourselves. That way, once we've sent the email, we can open our inbox and confirm that it was successfully sent. I'll be using my own email address, mike.angstadt@gmail.com, in this blog post, but you should use your own instead obviously.

Finding the SMTP server address

Before we can start sending our email, we need to know where to send it to! In other words, we need to get the address of the SMTP server that our email address belongs to. To do this, we need to perform an MX record lookup against the "host" part of our email address, which is located to the right of the "@" symbol (the part to the left is called the "user" or "mailbox"). In my case, the host is "gmail.com".

To perform an MX record lookup on Linux, type the command dig mx HOST where HOST is the host address.

To perform an MX record lookup on Windows, type the command nslookup. Then, type set type=MX followed by the host name.

Performing an MX record lookup will most likely return a list of SMTP servers. So, which one should you pick? Well, any one will work, but the one with the lowest MX preference indicator should be used. On Linux, this is the number directly to the left of the SMTP address. On Windows, this is the number labeled "MX preference". If you were writing an SMTP server yourself, you would sort this list of addresses by preference indicator and then send the email to the one with the lowest value. If that server happens to be down, then you would keep going down the list until you found a server that worked. If all servers have the same preference indicator, then you should choose one randomly. This helps to evenly spread the load amongst all servers and thus make the server admins happy.

If the MX record lookup does not return any SMTP servers, that means you can use the host part of the email address itself as the SMTP server address.

Sending the email

Now that we have the address of the SMTP server, we can go ahead and send the email. The standard SMTP port is 25, so let's open a telnet connection on that port. To do this, run the command telnet ADDRESS 25, where ADDRESS is the SMTP server address.

Warning: In my experience, some SMTP servers are not very friendly toward "human" SMTP connections--they will terminate the connection if it's idle for only a few seconds. Yahoo is one such example.

The first command that is sent is the EHLO command. This allows the SMTP client (us) to introduce itself to the server. It contains the email host address of the SMTP client. For example, if I was a Hotmail server, I might enter EHLO hotmail.com. This is optional though, so you can just enter EHLO if you want.

Next, we'll specify who the email is from. This is done using the MAIL command. The syntax for this command is MAIL FROM:<address@website.com>. The syntax is very specific--there must be NO space after the colon and the email address MUST be surrounded by < and > characters.

Then, we specify who the email should be sent to using the RCPT command. The snytax for this command is RCPT TO:<mike.angstadt@gmail.com>. If the email has multiple recipients, then this command can be entered multiple times. Just as with the MAIL command, there must be NO space after the colon and the email address MUST be surrounded by < and > characters.

Now, we're ready to send the actual body of the email. Send the DATA command to let the server know that we're ready send the acutal message.

Next, enter the email data. The email data consists of a series of headers, followed by a blank line, followed by the email text, followed by a line consisting of just a single dot (.). Each header goes on its own line and has the syntax HeaderName: HeaderValue. At the very least, you should have the headers "From", "To", and "Subject" because this is what email clients use to display the sender, recipients, and subject of an email. For example, I'm going to type the following:

From: <address@website.com>
To: <mike.angstadt@gmail.com>
Subject: My first SMTP email!

Dear Mike,
This is my first SMTP email.
.

Then, the SMTP server sends the email! You can enter more emails if you like or you can terminate the connection by sending the QUIT command.

The entire SMTP conversation.

Now, open up your email account and you should see a new email! However, it will likely be considered spam because the host in the "from" address does not match who it was really sent from. For example, nothing's stopping me from entering "barack.obama@whitehouse.gov" as the sender. But, obviously, it's not really from the President of the United States, so it would likely be marked as spam. So check your spam folder if you don't see it in your inbox.

Properties File Wrapper Class

If you're a Java programmer, you know that a properties file is a text file that contains a series of key/value pairs and is often used to store the configuration settings of an application. Each key/value pair resides on its own line. The key comes first, followed by an equals sign, followed by the value. The convention is to organize the key/value pairs into a hierarchy by giving the keys "package-like" names. For example, if I want to store the username, password, and email address of an admin user, I might prepend all of the key names with "admin.", naming the keys "admin.username", "admin.password", and "admin.email". Property files in Java are read using the Properties class.

admin.username=jdoe
admin.password=secret
admin.email=jdoe@company.com
log.file=/home/user/logs/myapp.txt
state.AZ=Arizona
state.TX=Texas
state.MD=Maryland
colors=red,yellow,blue

One technique I like to use when reading properties files in Java is to create a wrapper class whose sole purpose is to read the data from the properties file. A method is created in this class for every key/value pair in the properties file. An advantage to this is that, if the programmer needs to access a property in multiple places throughout the application, the key name (a hard-coded String), need not be duplicated (and potentially misspelled) because it is centralized inside the wrapper class. The wrapper class can also perform extra manipulations on the values in order to "unmarshal" them into more programmer-friendly data structures (for example, converting a file path into a File object or a string of comma-delimited values into a List object).

As an example, let's create a properties wrapper class out of the properties file example shown above.

import java.util.*;
import java.io.*;

public class AppProperties {
  private final Properties props;

  public AppPropeties(Reader reader) throws IOException {
    props = new Properties();
    props.load(reader);
  }

  public String getAdminUsername(){
    return props.getProperty("admin.username");
  }

  public String getAdminPassword(){
    return props.getProperty("admin.password");
  }

  public String getAdminEmail(){
    return props.getProperty("admin.email");
  }

  public File getLogFile(){
    String value = props.getProperty("log.file");
    return (value == null) ? null : new File(value);
  }

  public String getStateName(String abbr){
    return props.getProperty("state." + abbr);
  }

  public List<String> getColors(){
    String value = props.getProperty("colors");
    if (value == null){
      return null;
    }
    String values[] = value.split(",");
    return Arrays.asList(values);
  }
}

The constructor takes a Reader object. This makes the class more flexible and easier to unit test, as it is not limited to reading the property data from a file (for example, a StringReader could be passed into it for unit testing purposes).

The "admin.*" properties each have their own method. For example, to retrieve the "admin.username" field, the getAdminUsername() method is called.

The "log.file" property is converted to a File object because this is what this value represents--a path to a file.

The "getStateName()" method for the "state.*" properties is more dynamic. It takes the state abbreviation as an argument and uses that to construct the key name. For example, if "TX" is passed into this method, the "state.TX" property will be accessed and "Texas" will be returned. Methods like this can be used if you need to retrieve property values based on input from the user.

Lastly, the getColors() method retrieves the value of the "colors" property, which is a comma-delimited string. It then parses the values out of this string and returns a List object.

Using a properties wrapper class like this can really neaten up your codebase. I've used this design pattern in multiple projects and have been happy with the results.

Encryption by hand

Audio recording of blog post:

The latest edition of 2600 Magazine has an interesting article about encryption. It explains a way to encrypt messages by hand, without the help of a computer. It's a two-step process: First, the message is converted into a series of numbers. And second, it is encrypted using a secret key.

This kind of encryption technique is thought to be used by spies to decrypt messages from number stations. Number stations came into existence shortly after World War II and still exist today. They are short-wave radio stations that are silent most of the time, but occasionally will broadcast a voice that reads off a series of numbers. These numbers are thought to be encrypted messages for spies in the field. The Conet Project has a great collection of freely-downloadable recordings from number stations.

In this blog post, I'll describe how perform this encryption technique.

Cypher

The message must first be converted into a series of numbers before encryption can occur. This is done using what's known as a simple substitution cipher, where each letter in the alphabet corresponds to a numeric code. An example of a very basic substitution cipher looks like this:

Each letter in this simple substitution cipher has a two-digit code.

This cipher assigns two-digit codes to each letter. The code 01 is assigned to the letter A, 02 to the letter B, and so on up to 26 for the letter Z.

However, there is a more efficient way to encode each letter. A cipher called a straddling checkerboard takes advantage of the fact that certain letters in the alphabet are used more often than others. The numeric codes for these letters have only one digit, while the codes for all the other letters have two. This makes the cipher text shorter, which makes the message easier to encrypt and decrypt.

A "straddling checkerboard" is arranged so that the most frequently-used letters are only one digit long.

The image above shows the straddling checkerboard that we'll use. The most frequently used letters in the English language ("AEINORST") appear on the top line. The author chooses to arrange them in a way that makes them easy to memorize ("AT ONE SIR"). However, they can be arranged in any order, as long as the person decrypting your message uses the same arrangement. The rest of the alphabet appears in the rows below.

The dashes you see on the first row are called shift characters. You use them to "jump down" to another row in the table. For example, the number 2 in the first row is a shift character, which means that 2 will be used as a prefix for the characters that are in the row labeled 2 (the second row). The number 6 in the first row is also a shift character, meaning that 6 will act as a prefix for the characters that are in the row labeled 6 (the third row). For example, the word WOMBAT translates to 64 3 29 20 0 1.

But what if your secret message has numbers in it? Well, numbers are encoded in a special way. The # character in the table represents the number escape character, which encodes to 69. The number, when encoded, will start and end with 69. Also, each digit in the number is repeated three times. For example, 2012 becomes 69 222 000 111 222 69.

Encryption

Before the message can be encrypted, a secret key must be generated. The key is a series of random numbers and must be at least as long as the ciphered message itself. If the key is longer than the ciphered message, then "0"s are appended to the message.

So, let's encrypt the message OCEANS11 using the key 62206 45175 09174 12846. Note that, spaces are inserted for readability purposes and are not part of the message or the key.

  32150 47691 11111 69000 (plain text)
- 62206 45175 09174 12846 (key)
-------------------------
  70954 02526 12047 57264 (encrypted)

The plain text message contains 17 digits. Because my key is 20 digits, I append three zeroes to the plain text so that it matches the size of the key. Then, I subtract each digit in the key from each digit in the plain text. If the result is less than zero, I add 10. For example, in the first column, I calculate 3 - 6, which results in -3. Because this is less than zero, I add 10 to get 7 as the final answer. In the second column, the result of 2 - 2 is 0, which is not less than zero, so I leave that as my final answer.

Decryption

  70954 02526 12047 57264 (encrypted)
+ 62206 45175 09174 12846 (key)
-------------------------
  32150 47691 11111 69000 (plain text)

Decrypting a message involves adding each digit in the key to each digit in the encrypted text. If the result is greater than 10, then 10 is subtracted from the result. For example, in the first column, the result of 7 + 6 is 13. This is greater than 10, so I subtract 10 to get 3 as my final answer. In the second column, 0 + 2 is 2, which is not greater than 10, so I leave this as my final answer.

The Java Collections Framework - Maps

The Collections Framework is a group of classes that allow you to group objects together in various ways and perform operations against those groupings. It is contained within the core Java API, so you don't have to install anything extra to use it. Its features are so basic and powerful that pretty much every piece of software written in Java makes use of this framework in one way or another. The framework has been around since Java 1.2 (1998) and has been improved upon with every subsequent Java release. There are four major collection types: Lists, Sets, Queues, and Maps.

The four basic collection types (List, Set, and Queue all inherit from the Collection interface).

---

A map is a data structure that contains a collection of key/value pairs. After the key/value pair is added to the map, the key can then be used to retrieve its corresponding value. All of the keys in a map are unique, so if the key in a key/value pair already exists in the map, adding that key/value pair to the map will just replace the existing key's value.

Implementations

The Java Collections Framework contains three main implementations of the Map interface. Much like the Set implementations (which I described in a previous blog post), they differ in how they iterate over their data.

• HashMap - The most basic implementation. It iterates over its entries in no particular order.
• LinkedHashMap - This implemention iterates over its entries in either (1) the order in which the entries were added to the map, with the oldest entries coming first or (2) the access time of each entry, with the least recently accessed entry coming first. The order type can be specified in the constructor and it defaults to insertion order.
• TreeMap - This implementation iterates over its entries by the sorted order of its keys. This requires that the key class implement the Comparable interface, which defines how objects of the class are sorted. If the class does not implement this interface, then a Comparator object can be passed into the TreeMap constructor to define the sorting rules.

Example

The following example demonstrates how to use a map in the Java Collections Framework. This map will hold the names of some of the states in the United States, with the state abbreviation acting as the key.

Map<String, String> states = new HashMap<String, String>();
states.put("AZ", "Azerbaijan");
states.put("TX", "Texas");
states.put("AZ", "Arizona");
states.put("CO", "Colorado");

System.out.println(states.get("AZ"));
System.out.println(states.get("ZZ"));
for (Map.Entry<String, String> entry : states.entrySet()){
  String abbr = entry.getKey();
  String name = entry.getValue();
  System.out.println(name + " (" + abbr + ")");
}

On line 1, a new instance of HashMap is created. The classes that will be used for the keys and values are specified using generics. In this case, both the key and value are Strings.

On lines 2-5, data is added to the map. On line 4, the key is the same as the key on line 2. This will cause the key's original value of "Azerbaijan" to be replaced with "Arizona".

Line 7 shows that the value for "AZ" was indeed replaced. It will print "Arizona". Line 8 will print "null" because the key "ZZ" does not exist in the map (the get() method returns null if the key does not exist).

On lines 9-13, each key/value pair in the map is iterated over and the abbreviation (key) and full name (value) of each state is printed out. The entrySet() method is used to do this. It returns a Set object that contains all of the map's key/value pairs. Because this is a HashMap, the map entries are returned in no particular order. Other map implementations would iterate over these entries differently:

• LinkedHashMap (insertion order): AZ, TX, CO
  The first entry to be added was "AZ", followed by "TX" and "CO". Replacing a key's value does not count as an insertion, which is why "AZ" comes before and not after "TX".
• LinkedHashMap (access order): TX, CO, AZ
  "AZ" comes last because it was most recently accessed (on line 7).
• TreeMap (sorted order): AZ, CO, TX
  Because the keys are Strings, they are sorted alphabetically.

The Java Collections Framework - Queues

The Collections Framework is a group of classes that allow you to group objects together in various ways and perform operations against those groupings. It is contained within the core Java API, so you don't have to install anything extra to use it. Its features are so basic and powerful that pretty much every piece of software written in Java makes use of this framework in one way or another. The framework has been around since Java 1.2 (1998) and has been improved upon with every subsequent Java release. There are four major collection types: Lists, Sets, Queues, and Maps.

The four basic collection types (List, Set, and Queue all inherit from the Collection interface).

---

A queue is an ordered collection of elements in which only the "top" element can be accessed. When the top element is removed, or popped, the next element is revealed. The order in which the queue's elements are arranged depends upon the type of queue. Also, note that the term push is used to refer to an element being added to a queue.

• A FIFO (first in, first out) queue orders its elements according to how recently they were added to the queue--elements that were pushed first will be popped first.
• A LIFO (last in, first out) queue, also known as a stack, is the opposite of a FIFO queue--elements that were pushed first are popped last.
• There's also a priority queue, in which each element has a priority associated with it. The elements with the highest priorities are popped first.

A dequeue (double-ended queue) allows the programmer to push and pop elements from the bottom of the queue as well as from the top.

"Exception vs. special return value" convension

The Java Collections Framework has a number of implementations for different types of queues (all inheriting from the Queue interface). They all follow a special convension: for each operation that you can perform on the queue, there are two methods. Each method does the same thing, but they differ in the way in which they handle edge cases. One method will throw an exception, while the other will return a special value. Here are some examples of these kinds of methods from the Queue interface.

• add() - pushes an element on the queue, throwing an IllegalStateException if the queue is full.
• offer() - pushes an element on the queue, returning false if the queue is full.
• remove() - pops the next element off the queue, throwing a NoSuchElementException if the queue is empty.
• poll() - pops the next element off the queue, returning null if the queue is empty.

Example

Here's an example of how to program a queue in Java. This program simulates a drive-thru window at a fast-food restaurant. Customers place their orders at the drive-thru window and then the kitchen makes their food. The kitchen makes the meals in the same order in which they were received, so it is a FIFO queue (if you are the first car in line, you will be the first to receive your order).

I use a BlockingQueue, which extends the Queue interface. It provides the ability to block the method call if you try to pop from an empty queue or push to a full queue. I use the take() method to pop the next element off the queue. If the queue is empty, then it waits until an element is pushed onto the queue before executing the next line of code.

The BlockingQueue imlpementation I use is the ArrayBlockingQueue, which requires that a max queue size be defined. In the case of my drive-thru simulator, this is the maximum number of cars that can fit into the driveway. I use the offer() method to push orders onto the queue. If this method returns false then it means that the driveway is full of cars (the queue is full). The would-be customer then has to drive away and find someplace else to get their food (nothing is pushed to the queue).

import java.text.MessageFormat;
import java.util.*

/**
 * Drive-thru simulator for a fast-food restaurant.
 * @author Mike Angstadt - http://www.mangst.com
 */
public class DriveThru {
  private static Random rand = new Random();

  public static void main(String args[]) throws InterruptedException {
    //the number of cars that can fit in the driveway
    int drivewaySize = 5;

    //the food orders are placed in a FIFO queue with a max capacity
    BlockingQueue<String> orders = new ArrayBlockingQueue<String>(drivewaySize);

    //the drive-thru window takes orders from the customers and pushes those orders onto the queue
    DriveThruWindow driveThruWindow = new DriveThruWindow(orders);
    driveThruWindow.start();

    //the kitchen pops the orders off the queue
    Kitchen kitchen = new Kitchen(orders);
    kitchen.start();
  }

  private static class Kitchen extends Thread {
    private BlockingQueue<String> orders;

    public Kitchen(BlockingQueue<String> orders) {
      this.orders = orders;
    }

    @Override
    public void run() {
      int orderNum = 0;
      while (true) {
        try {
          //get the next order
          //if the queue is empty, then wait until an element is pushed onto it
          String order = orders.take();

          //make the food
          System.out.println("Order " + orderNum + ": Making order \"" + order + "\"...");
          Thread.sleep(rand.nextInt(9000) + 1000); //sleep for 1-10 seconds
          System.out.println("Order " + orderNum + ": Order \"" + order + "\" finished.");
          orderNum++;
        } catch (InterruptedException e) {
          break;
        }
      }
    }
  }

  private static class DriveThruWindow extends Thread {
    private List<MenuItem> menu = new ArrayList<MenuItem>();
    private int orderNum = 0;
    private BlockingQueue<String> orders;

    public DriveThruWindow(BlockingQueue<String> orders) {
      this.orders = orders;

      //create the menu
      MenuItem menuItem = new MenuItem("Quarter-pounder", new String[] { "cheese", "tomatoes", "onions", "pickles" }, "{0} with {1}");
      menu.add(menuItem);
      menuItem = new MenuItem("coke", new String[] { "Small", "Medium", "Large" }, "{1} {0}");
      menu.add(menuItem);
      menuItem = new MenuItem("chicken nuggets", new String[] { "6", "10", "20" }, "{1}-piece {0}");
      menu.add(menuItem);
      menuItem = new MenuItem("Apple pie");
      menu.add(menuItem);
    }

    @Override
    public void run() {
      while (true) {
        //wait for the next car
        try {
          Thread.sleep(rand.nextInt(6000) + 1000); //sleep for 1-7 seconds
        } catch (InterruptedException e) {
          break;
        }

        //get the customer's order
        int index = rand.nextInt(menu.size());
        String order = menu.get(index).generate();

        //push the order onto the queue
        boolean inserted = orders.offer(order);
        if (inserted) {
          System.out.println("Order " + orderNum + ": Car placed order for \"" + order + "\".");
          orderNum++;
        } else {
          System.out.println("Driveway full...customer lost!");
        }
      }
    }
  }

  private static class MenuItem {
    private final String name;
    private final String[] modifiers;
    private final String format;

    public MenuItem(String name) {
      this(name, null, null);
    }

    public MenuItem(String name, String[] modifiers, String format) {
      this.name = name;
      this.modifiers = modifiers;
      this.format = format;
    }

    public String generate() {
      if (format == null) {
        return name;
      } else {
        int modifier = rand.nextInt(modifiers.length);
        return MessageFormat.format(format, name, modifiers[modifier]);
      }
    }
  }
}

The Java Collections Framework - Sets

The Collections Framework is a group of classes that allow you to group objects together in various ways and perform operations against those groupings. It is contained within the core Java API, so you don't have to install anything extra to use it. Its features are so basic and powerful that pretty much every piece of software written in Java makes use of this framework in one way or another. The framework has been around since Java 1.2 (1998) and has been improved upon with every subsequent Java release. There are four major collection types: Lists, Sets, Queues, and Maps.

The four basic collection types (List, Set, and Queue all inherit from the Collection interface).

---

Another type of collection in the Java Collections Framework is the set. A set is a collection of elements where duplicates are not allowed. If the programmer tries to add a duplicate element, the set will see that the element already exists and nothing will be added. Sets also do not allow random access like lists do. The only way to retrieve elements from a set is to iterate over all the elements using an Iterator or a foreach loop (so, for example, you cannot directly get the "fourth" element of a set).

Buckets

Sets are really fast when it comes to determining whether an element exists in the set or not. The way sets do this is by making heavy use of the Object.equals() and Object.hashCode() methods. When an object is added to the set, the set uses the object's hash to find a bucket to store the object in. Later, when the set is asked if it contains a given object, the set uses the hash of the given object to find a bucket, and then iterates over each element in that bucket. It calls the equals method on each element in the bucket to determine if the given object is the same as any of the elements in the bucket. This is a lot faster than a list because a list has to iterate over every single element in order to determine if it contains an object. Sets just have to iterate over the elements in a single bucket, which contains only a fraction of the total number of elements in the set.

Importance of hashCode()

However, the efficiency of the set's search operation relies heavily on the quality of the object's hashCode() implementation. If the implementation is good, then the set will spread all of its elements evenly amongst all buckets. However, if the implementation is not good, then the elements will not be spread evenly amongst all buckets. This will cause some buckets to be larger than others, which means they will take longer to search over and decrease the overall performance of the set.

Probably the worst possible hashCode() implementation you could create is one that returns a hard-coded value. It's a completely valid implementation, but it will cause all elements to be stored in a single bucket, making the set's search performance no better than that of a list.

public class BlogPost {
  private String content;
  private Date created;
  private List<String> comments;

  @Override
  public int hashCode(){
    //the worst-possible implementation
    //DO NOT USE!!
    return 1;
  }
}

What you want to do is create a hashCode() implementation that will generate a wide range of values. Luckily, if you use Eclipse (or probably any other IDE), you can have one generated for you. In Eclipse, right-click on the code and go to "Source > Generate hashCode() and equals()". It will prompt you for what class fields you want to include in the hash calculation and then generate the proper code automatically.

public class BlogPost {
  private String content;
  private Date created;
  private List<String> comments;

  @Override
  public int hashCode() {
    //the implementation generated by Eclipse (much better)
    final int prime = 31;
    int result = 1;
    result = prime * result + ((comments == null) ? 0 : comments.hashCode());
    result = prime * result + ((content == null) ? 0 : content.hashCode());
    result = prime * result + ((created == null) ? 0 : created.hashCode());
    return result;
  }
}

Relationship between hashCode() and equals()

Note that Java expects the equals() and hashCode() methods to follow certain rules (read this three times to let it sink in):

1. If two objects are equal, then they must have the same hash.
2. But if two objects have the same hash, they are not necessarily equal.

It is your responsibility as a programmer to follow these rules. If you do not, then sets (as well as other collection types from the Collections Framework) will not function correctly. The code that Eclipse generates complies with these rules.

Example

Here's a short code example of how to use a set in Java.

Set<String> users = new HashSet<String>();
users.add("Mark");
users.add("Steve");
users.add("Mark");
users.add("Kelly");
System.out.println(users.contains("mark"));
System.out.println(users.contains("Mark"));
for (String user : users){
  System.out.println(user);
}

On line 1, I create the Set object. I'm assigning the object to a variable of type Set instead of type HashSet so that I can more easily change implementations if I ever need to in the future.

On lines 2-5, I add elements to the set. On line 4, I try adding a duplicate element, but nothing will be added because sets do not allow duplicate elements. No exception will be thrown or anything--the add() method will just return "false" instead of "true".

Line 6 will print "false" because the String "mark" is not the same as the string "Mark". Line 7 will print "true".

On lines 8-10, I iterate over the entire set, printing each user name. This is the only way to retrieve elements from a set.

Set Implementations

There are three implementations of the Set interface. They differ in the way in which they iterate over their elements.

• HashSet - The most basic set implementation, iterates over elements in no particular order.
• LinkedHashSet - Iterates over elements in the order in which they were added to the set.
• TreeSet - Iterates over elements in their sorted order. The way in which the elements are sorted can be defined by having the elements implement the Comparable interface, or by passing in an implementation of the Comparator interface to the TreeSet constructor.

The Java Collections Framework - Lists

The Collections Framework is a group of classes that allow you to group objects together in various ways and perform operations against those groupings. It is contained within the core Java API, so you don't have to install anything extra to use it. Its features are so basic and powerful that pretty much every piece of software written in Java makes use of this framework in one way or another. The framework has been around since Java 1.2 (1998) and has been improved upon with every subsequent Java release. There are four major collection "types": Lists, Sets, Queues, and Maps.

The four basic collection types (List, Set, and Queue all inherit from the Collection interface).

---

In this blog post, I'll discuss the List type. Lists are defined as being an ordered collection of elements where duplicate elements are allowed. Probably the most used list implementation (and probably the most used class in the entire Collections Framework) is the ArrayList class. This class is meant to behave just like an array, with the added ability of being able to add, insert, and remove elements (which cannot be done with normal arrays).

List<String> names = new ArrayList<String>();
names.add("Mark");
names.add("Steve");
names.add("Jill");
names.remove(1);
names.remove("Jill");
names.add(0, "Zach");
Collections.sort(names);
System.out.println(names);

On line 1, I create a new instance of an ArrayList. Using generics, I specify that the list will only contain String objects (generics support was added to the Collections Framework in Java 1.5). If I try to add anything other than a String to my ArrayList, a compilation error will be thrown.

Also notice how I'm assigning my ArrayList object to a variable of type List instead of type ArrayList. List is an interface that ArrayList implements. The reason for doing this is that there are multiple implementations of the List interface. By assigning my ArrayList to a variable of type List, I'm making my code more flexible so that it's not tied to a specific List implementation. The only thing the code cares about is that the List variable satisfies the definition of what a "list" is supposed to be within the Collections Framework (an ordered collection where duplicates are allowed). It is good practice to apply this technique throughout the Collections Framework to maximize code flexibility.

On lines 2-4, I populate my list by adding some elements to it. The add() method appends the element to the end of the list.

On line 5, I remove an element by specifying the element index (Lists are 0-based just like normal arrays, so "0" corresponds to the first element, "1" to the second, etc). This will remove the "Steve" element. Then, on line 6, I remove an element by passing in a String object. When an element is removed in this way, it iterates over each element in the list, using the object's equals() method to determine which element to remove. If it doesn't find any such element, nothing is removed.

On line 6 of the code sample, I insert an element into the List at a specific index. The index I specify is "0", which means it will be inserted at the beginning of the list.

Then, on line 7, I sort the list so that the names are ordered alphabetically. This method requires that the class of the elements in the list implement the Comparable interface, which defines how two objects of that class are compared against each other when they are sorted. The String class already implements this interface, defining that Strings be sorted alphabetically. If you want to sort the list differently, you can pass your own implementation of the Comparator interface as a second argument of the sort() method. For example, to sort the strings by length, you could write:

Collections.sort(names, new Comparator<String>(){
  @Override
  public int compareTo(String element1, String element2){
    //sort Strings by length
    if (element1.length() < element2.length(){
      return -1; //"element1" should come before "element2"
    } else if (element1.length() > element2.length()){
      return 1; //"element1" should come after "element2"
    } else {
      return 0; //"element1" and "element2" are equal
    }
  }
});

Finally, on line 8, I print the list out so I can see what it looks like. Passing an object into the System.out.println() method will print the return value of that object's toString() method. The list's toString() method generates a string representation of the list by calling the toString() method of every list element. It surrounds the entire list in brackets and separates each element with a comma.

[Mark, Zach]