From DojoWiki

For the July Meeting we had originally decided to review Heaps and Priority Queues

Instead, I took a step back and introduced Linked Lists.

The Java code I wrote follows (with a Launcher app to allow us to view the contents of the list).

package org.pghcodingdojo.collections;

import org.pghcodingdojo.collections.exceptions.TargetTooLargeException; 

public class Launcher {

	/**
	 * @param args
	 */
	public static void main(String[] args) throws TargetTooLargeException {
		LinkedList list = new LinkedList()  ;
		list.add("Amazing Grace, how sweet the sound");
		list.add("Was blind, but now I see");
		
		list.add("I once was lost, but now am found.") ; 
		String curString ;
		
		Iterator i = list.getIterator() ;
		do {
			curString = i.getValue() ; 
			if (curString.equals("Was blind, but now I see") ) {
				i.insert("XXX") ; 
			}

		} while (i.moveNext()) ; 
		
		i = list.getIterator() ;
		
		do {
			curString = i.getValue() ; 
			System.out.println(curString) ; 
		}while (i.moveNext()) ; 
		
		System.out.println("Last Node = " + list.getLast()) ; 
		list.popLast() ; 
		
		System.out.println("Last Node = " + list.getLast()) ; 

	}

}

package org.pghcodingdojo.collections;

import java.util.List;

import org.pghcodingdojo.collections.exceptions.TargetTooLargeException;

/**
 * @author akinsgre
 * 
 */
public class LinkedList {

	private Node firstNode;

	private Node currentNode;

	private Node tailNode;

	void add(Node node) {

		if (firstNode == null) {
			// create the first node in the list
			firstNode = node;
			tailNode = node;
		} else {
			tailNode.setNextNode(node);
			tailNode = node;
		}
	}

	public void add(String string) {

		Node node = new Node();
		node.setValue(string);
		this.add(node);
	}

	public Node getFirstNode() {
		return firstNode;
	}

	public String getLast() {
		if (tailNode == null)
			return null;
		return tailNode.getValue();
	}

	public void popLast() {
		currentNode = firstNode ; 
		while (currentNode.getNextNode() != tailNode) {
			currentNode = currentNode.getNextNode() ; 
		}
		tailNode = currentNode ; 
		currentNode.setNextNode(null) ; 
	}
	
	public Iterator getIterator() {
		Iterator i = new Iterator() ; 
		i.setNode(firstNode) ;
		return i ; 

	}


}

package org.pghcodingdojo.collections;

public class Iterator {
	private Node node ; 
	void setNode(Node node) {
		this.node = node ;
	}
	
	public boolean moveNext() {
		if ((this.node == null) || (this.node.getNextNode() == null))  return false ;
		this.setNode(this.node.getNextNode()) ;
		return true ;
	}
	
	public String getValue() {
		return this.node.getValue() ; 
	}
	
	public void insert(String value) {
		Node tempNode = this.node.getNextNode() ;
		Node newNode = new Node() ; 
		newNode.setValue(value) ; 
		this.node.setNextNode(newNode); 
		newNode.setNextNode(tempNode) ; 
	}
}

package org.pghcodingdojo.collections;

public class Node implements Comparable { 


	@Override
	public boolean equals(Object obj) {
		return value.equals(((Node) obj).getValue());
	}
	

	public int compareTo(Object that) {
		if (!(that instanceof Node)) throw new ClassCastException() ; 
		return this.value.compareTo(((Node)that).value) ; 
		
	}

	private String value;

	private Node nextNode;

	public Node getNextNode() {
		return nextNode;
	}

	public void setNextNode(Node nextNode) {
		this.nextNode = nextNode;
	}

	public String getValue() {
		return value;
	}

	public void setValue(String value) {
		this.value = value;
	}

	
}