How would I make a color Gradient with linear interpolation along with Linked list?

Question

I am currently trying to make a rainbow trail that follows your mouse. i used Linkedlist to plot the points of my mouse so the trail follows along. The trail itself looks perfect its only the colors in the trail that don't look right. I'm wanting them to fade into each other. Someone told me to use linear interpolation and after looking into it for awhile it seems like it would work i just don't know how to implement it.

this is the code i have so far:

import impsoft.bots.ColorBot;
import impsoft.scripting.ibot.interfaces.AutoPaint;
import impsoft.scripting.types.ColorScript;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.util.Deque;
import java.util.LinkedList;

import impsoft.scripting.ibot.structs.XY;
import impsoft.scripting.types.ColorSkeltonScriptable;
import impsoft.scripting.types.parallel.scriptjobs.ScriptJob;


public class MouseTrail extends ColorScript implements AutoPaint {
     public MouseTrail(ColorBot c) {
      super(c);

     }
    public void script() throws InterruptedException {
     while(true) {
         mt.setSize(500);
         mt.exec();

      sleep(100);
     }
    }

    public static String name = "Mouse trail test";
    public static String author = "Llaver";
    public static String description = "test for mouse trail";
    public static double version = 1.00;


public class MouseTrail2 extends ScriptJob implements AutoPaint {


    private int size;
    private final ColorSkeltonScriptable cs;
    private final Deque<XY> trail = new LinkedList<XY>();
    private final Color[] rainbow = new Color[]{
            Color.RED, Color.YELLOW, Color.GREEN, Color.CYAN, Color.BLUE, Color.magenta
        };

    public MouseTrail2(ColorSkeltonScriptable cs) {
        super(cs);
        this.cs = cs;
    }

    public void setSize(int s) {
        size = s;
        s = 200;
    }

    public void runV() {
        try {
            while (true) {

                synchronized (trail) {
                    if (trail.size() >= size) {
                        trail.pop();
                    }
                    trail.offer(cs.getCurrentMouseXY());
                }
                sleep(1);
            }

        } catch (InterruptedException e) {
        }
    }

    @Override
    public void paint(Graphics g) {
        final Graphics2D g2d = (Graphics2D) g;
        g2d.setStroke(new BasicStroke(3, BasicStroke.CAP_BUTT, BasicStroke.JOIN_ROUND));
        g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
        synchronized (trail) {
                float perc;
                int idx;
                for(int i = 1 ; i < trail.size() - 1 ; i++){
        XY current = ((LinkedList<XY>) trail).get(i);
        XY next = ((LinkedList<XY>) trail).get(i - 1);
        perc = ((float)i / trail.size()) * 100f;
       idx = Math.round((perc * (float)rainbow.length) / 100f);
       if(idx >= rainbow.length)idx -= 1;       
       g2d.setColor(rainbow[idx]);
        g.drawLine(current.x, current.y, next.x, next.y);
    }
            }
        }

    }


@Override
public void paint(Graphics arg0) {  
}
private MouseTrail2 mt = new MouseTrail2(this);

}

some pics:

this is what i have right now:

http://img11.imageshack.us/img11/3031/mousetrailhavenow.png

this is what im trying to get:

http://img594.imageshack.us/img594/7381/mousetrailtryingtoget.png

does that possibly make this a little more clear?