Linked List

Linked list is a fundamental data structure, which uses reference stored in each node to iterate through subsequent nodes. A linked list has many types like singly linked list, doubly linked list and circular linked list. Following is a simple bare bone implementation of singly linked list:

The base interface:

public interface LinkedList {
 public boolean add(T t);
 public boolean remove(T t);
 public void removeAll();
 public int size();
 public boolean isEmpty();
}

Class representing each node:

public class LinkNode {
 private LinkNode nextNode = null;
 private T node = null;

 public LinkNode() {
  
 }
 
 public LinkNode(T node) {
  this.node = node;
 }
 
 public T getNode() {
  return node;
 }

 public void setNode(T node) {
  this.node = node;
 }
 
 public LinkNode getNextNode() {
  return nextNode;
 }

 public void setNextNode(LinkNode nextNode) {
  this.nextNode = nextNode;
 }
 
 public String toString() {
  return node.toString();
 }
 
 public int hashCode() {
  return node.hashCode();
 }
 
 public boolean equals(LinkNode t) {
  return node.equals(t.getNode());
 }
}

Implementation for a singly linked list:

public class SingleLinkedList implements LinkedList {
 LinkNode header = null;
 LinkNode lastNode = null;
 
 public SingleLinkedList() {
  
 }
 
 public boolean add(T t) {
  LinkNode newNode = new LinkNode(t);
  if(header == null) {
   header = newNode;
  }
  else {
   lastNode.setNextNode(newNode);
  }
  lastNode = newNode;
  return true;
 }
 
 public boolean remove(T t) {
  LinkNode tmp = header;
  LinkNode prev = null;
  
  while(tmp != null) {
   if(tmp.getNode().equals(t)) {
    if(prev == null) header = null;
    else if(tmp.getNextNode() != null) prev.setNextNode(tmp.getNextNode());
    return true;
   }
   prev = tmp;
   tmp = tmp.getNextNode();
  }
  return false;
 }
 
 public void removeAll() {
  header = null;
 }
 
 public boolean isEmpty() {
  return header == null;
 }
 
 public int size() {
  LinkNode tmp = header;
  int size = 0;
  while(tmp != null) {
   size++;
   tmp = tmp.getNextNode();
  }
  
  return size;
 }
 
 public String toString() {
  StringBuffer str = new StringBuffer("[");
  LinkNode tmp = header;
  while(tmp != null) {
   str.append(tmp.toString());
   tmp = tmp.getNextNode();
   if(tmp != null) str.append(", ");
  }
  str.append("]");
  return str.toString();
 }
}

Test class which uses the singly linked list implementation:

public class LinkedListTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  LinkedList list = new SingleLinkedList();
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.add("1");
  list.add("2");
  list.add("3");
  list.add("2");
  list.add("2");
  list.add("3");
  System.out.println(list.size());
  System.out.println(list);
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.remove("2");
  System.out.println(list.size());
  System.out.println(list);
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.removeAll();
  System.out.println("Is list empty? " + list.isEmpty());
 }

}

Reflecting on Annotations

          The easiest way to check for an annotation is by using the isAnnotationPresent() method

­          This lets us specify the annotation to check for, and get a true/false result

public void testAnnotnPresent(PrintStream out) throws Exception {

      Class c = Super.class;

boolean inProgr = c.isAnnotationPresent(InProgress.class);

if(inProgr) out.println(“Super is in progress”);

else out.println(“Super is not in progress”);

 

}

­          This also lets us take advantage of the Inherited annotation

­          Although the Sub is not marked as in progress, it inherits from Super, which is in progress

­          Once the method in question is located, that method can be queried for a specific annotation using getAnnotation()

Class c = AnnotationTester.class;

MethodElement element = c.getMethod(“calculateInterest”,

                                    float.class, float.class);

GroupTODO groupTodo = element.getAnnotation(GroutpTODO.class);

String assignedTo = groupTodo.assignedTo();

out.println(“TODO Item on Annotation Tester is assigned to: ” +

assignedTo);

­          We must have to know exactly what we’re looking for – this is one of the few drawbacks of getAnnotation()

­           

­          We can use getAnnotations(), if we’re trying to locate all annotations for a program element, or if we need to iterate through all annotations looking for a specific one

­          Following is a simple utility method that prints out all annotations for a supplied element

public void printAnnotations(AnnotatedElement e) {

      System.out.println(“Annotations for “ + e.toString());

      Annotation[] annotations = e.getAnnotations();

for(Annotation a : annotations) {

      System.out.println(a.annotationType().getName());

}

}

­          The getAnnotations() method prints both declared as well as inherited annotations

­          To get declared annotations alone, we need to use getDeclaredAnnotations() method

­          java.lang.reflect.AnnotatedElement is an interface that the reflection constructs like Method, Class etc. implement

­          It allows access to the annotation methods

­          The core reflection constructs all implement this interface –

o        Class

o        Constructor

o        Field

o        Method

o        Package

o        AccessibleObject

­          This allows all the above elements to be introspected for annotations

­          All these element types provide the following methods as a result of implementing AnnotatedType

o        public Annotation getAnnotation(Class annotationType)

o        public Annotation[] getAnnotations()

o        public Annotation[] getDeclaredAnnotations()

o        public boolean isAnnotationPresent(Class annotationType)

­          Since any Java program element can be treated as an AnnotatedType, we can always get at an element’s annotations using these methods

­           

­          Reflection on annotations only works for annotation types that have Runtime retention

­          Even if the annotation is retained at compilation, if the VM doesn’t load this retention at class-load time, then reflection can’t pick up the annotation

­          Deprecation does not have runtime retention – it has source retention

­          So it is undetectable through Java reflection

­           

Meta Annotations

­          As we can annotate classes, we can also annotate custom annotations

­          Meta-annotations or annotations on annotations are helpful in figuring out someone else’s intent for a customized annotations

­          There are four standard meta-annotations, all defined in the java.lang.annotation package

o        Target

Specifies which program elements can have annotations of the defined type

o        Retention

Indicates whether an annotation is tossed out by the compiler, or retained in the compiled class file

In cases where the annotation is retained, it also specifies whether it is read by the JVM at class load

o        Documented

Indicates that the defined annotation should be considered as part of the public API of the annotated program element

o        Inherited

It is intended for use on annotation types that are targeted as classes, indicating that the annotated type is an inherited one

­           

­          Target

­          It is used to specify which program elements are allowed as targets for the defined annotation

­          This prevents misuse of an annotation, and is a sanity check for an annotation

­          Target should be used in the lines directly preceding the annotation definition

@Target({ElementType.TYPE, ElementType.METHOD

   ElementType.CONSTRUCTOR, ElementType.ANNOTATION_TYPE})

public @interface TODO {

      ....

}

­          Target takes a single member whose type is an array of values, each of which should be an enumerated value from the java.lang.annotation.ElementType enum

­          This enum defines the various program elements allowed as targets of an annotation type

package java.lang.annotation;

 

public enum ElementType {

      TYPE,

      FIELD,

      METHOD,

      PARAMETER,

      CONSTRUCTIR,

      LOCAL_VARIABLE,

      ANNOTATION_TYPE,

      PACKAGE

}

­          To use Target we need to import both Target and ElementType

­          Following is the definition for the Target annotation

package java.lang.annotation;

 

@Documented

@Retention(RetentionPolicy.RUNTIME)

@Target(ElementType.ANNOTATION_TYPE)

public @interface Target {

      ElementType[] value();

}

­          As we can see in the above definition, Target meta-annotation is used on itself

­          In case of annotation types that work for all program elements, we don’t have to use Target at all

­           

­          Retention

­          The Retention meta-annotation defines how the Java compiler treats annotations

­          Annotations can be tossed out of a compiled class file by the compiler, or kept in the class file

­          Additionally, the JVM can ignore annotations – when they are retained in the class file, or read those annotations at the time a class is first loaded

­          All of these options are specified by Retention

­           

­          Like Target, we specify the retention of an annotation type just before the annotation definition

­          Also like Target, the argument to Retention must be a value from an enum support class – java.lang.annotation.RetentionPolicy

package java.lang.annotation;

 

public enum RetentionPolicy {

      SOURCE,  //annotation is discarded by compiler

      CLASS,   //stored in the class file, but ignored by the VM

      RUNTIME  //stored in the class file and read by the VM

}

­          The default retention policy, for all annotations, is RetentionPolicy.CLASS

­          This retains annotations, but doesn’t require the VM to read them when classes are loaded

­          A good example of using Retention occurs in the SuppressWarnings annotation

­          As that annotation type is purely used for compilation – ensuring warning of the specified type are suppressed, it does not need to be retained in a class’s byte code

@Retention(RetentionPolicy.SOURCE)

public @interface SuppressWarnings {

      ....

}

­           

­          Documented

­          Annotations are not normally visible in the codes’ Javadoc

­          This is where the Documented meta-annotation comes into play

­          We can use it to ensure that our annotations show up in generated Javadoc

­          We need to add a @Documented meta-annotation to any annotation type that we want to appear in Javadoc

import java.lang.annotation.Documented;

import java.lang.annotation.Retention ;

import java.lang.annotation.RetentionPolicy ;

 

@Documented

@Retention(RetentionPolicy.RUNTIME)

public @interface InProgress { }

­          Anytime we use the Documented annotation, we should pair it with a retention policy of RetentionPolicy.RUNTIME

­           

­          Inherited

­          Annotations applied to super class are not automatically inherited by the sub-class

­          For example in the following code, InProgress annotation is not inherited by the sub-class Sub

@InProgress

public class Super {

      ....

}

 

public class Sub extends Super {

      ....

}

­          We need to used Inherited in the definition of the InProgress annotation type to fix this problem

@Documented

@Inherited

@Retention(RetentionPolicy.RUNTIME)

public @interface InProgress { }

­          The above definition will make any sub-class of a class annotated with the InProgress annotation inherit the annotation

­          Annotations marked as Inherited only apply to sub-classes, so implementing a method with annotations will not result in the annotations being inherited

­          If we override a method from a super class, we don’t inherit that specific method’s annotations

­          Only the annotations on the super class itself are inherited, and those and those by the sub-class as a whole

­           

Annotations

 

­          Annotations provide a well-defined metadata mechanism

­          Metadata typically makes statements about source code that is interpreted at some point - usually by a code or data analysis tool

­          Annotations are modifiers that can be applied to package and type declarations, constructors, methods, fields, parameters and even variables

­          They take the form of name=value pairs, and we can use Java's built-in types, as well as define custom annotation types of our own.

­          Annotation type is a specific name of an annotation, along with any default values and related information

­          An annotation then uses an annotation type to associate some piece of information with a Java program element – methods, classes, variables etc.

­          So a class might only use one annotation type – like Override, and yet have ten or fifteen annotations – if it used Override ten or fifteen times

­          In short, annotation type refers to the definition of the annotation, while annotation refers to the actual usage of the definition.

­           

­          Annotations are checked by the Java compiler – we cannot misspell an annotation name or a member name of the annotation

­          The compiler will complain about the misspelling

­           

­          Standard annotation type

­          There are three standard annotations - all three are defined in the java.lang package:

o        @Override - used to indicate that a method overrides a method in its superclass

@Override

public String toString() {

      return super.toString() + “[modified by subclass]”;

}

o        @Deprecated - indicates that use of a method or element type is discouraged

@Deprecated

Public class Betamax { ... }

o        @SuppressWarnings - turns off compiler warnings for classes,  methods, or field and variable initializers

@SupressWarnings(“unchecked”)

public void method1() { …. }

­           

­          In addition to the three standard annotation types, there are three categories of annotations

o        Marker annotations – they are used with annotation types that define no members

They simply provide information contained within the name of the annotation itself - @MarkerAnnotation

An annotation whose members all have default values can also be used as a marker, since no information must be passed in

o        Single-value annotations – they have just a single member, named value. The format of a single-value annotation is - @SingleValueAnnotation(“some value”)

o        Full annotations – it isn’t really a category, it just uses the full range of annotation syntax

Here parentheses follow the annotation name, and all members are assigned values

        @Reviews({ //curly braces indicate an array of values

@Review(grade=”EXCELLENT”, reviewer=”df”),

@Review(grade=”SATISFACTORY”, reviewer=”eg”)})

­          There are no semicolons at the end of annotation lines

­           

­          Custom annotation type

­          Java allows us to define our own annotations with the @interface keyword

­          Annotation types are, at their basic level, Java interfaces

­          They look similar to a normal Java interface definition, but we use the @interface keyword instead of interface, which tells the compiler that we’re writing an annotation type instead of a normal interface

­          Following is a simple marker annotation type

package com.myapp;

public @interface InProgress { }

­          We can use this on any method or class

@com.myapp.InProgress

public void calculateInterest(float amount, float rate) {

}

­           

­          Following is a simple single-value annotation

package com.myapp;

public @interface TODO {

      String value();

}

­          Here value is not just a member declaration, but also a method declaration

­          We are actually defining a method called value(), and the compiler then automatically creates a member variable with the same name

­          Also, since the annotation types function like interfaces, the methods are all implicitly abstract, and have no bodies

­          This annotation can be used as follows

@TODO(value=”test”)

public void method1() { }

­          Or we can use the shorthand method that is applicable to single-value annotations

@TODO(“test”)

public void method1() { }

­           

­          Following is an annotation with multiple members

package com.myapp;

 

import java.util.Date;

 

public @interface GroupTODO {

      public enum Severity {CRITICAL, IMPORTANT, TRIVIAL};

     

      Severity severity() default Severity.IMPORTANT;

      Strint item();

String assignedTo();

String dateAssigned();

}

­          Any data type including enums can be used as a member of an annotation type

­          In the above example the member severity has a default value

­          The above annotation type can be used as follows

@GroupTODO( severity=GroupTODO.Severity.CRITICAL,

            item=”Calculate interest per month”,

            assignedTo=”Fred”,

            dateAssigned=”12/23/2008”)

public void calculateInterest(float amount, float rate) {

}

­           

­          The @interface keyword implicitly indicates an extension of java.lang.annotation.Annotation

­          So we can’t compile an annotation type that explicitly tries to extend anything else

­          However, we can extend and implement annotation types, although these extensions and implementations are not treated as annotation types

­