Making a Linked List

Here is some old code of mine. There are few things that should be change but this is how you can write a linked list.

The Node Class

View a node object as an container.  This node contains some kind of data and two memory address of the next and prior nodes.

public class Node implements Cloneable {
    private T    data;
    private Node prior;
    private Node next;

    public Node(){
    	this.data = null; 	// Node data
    	this.prior   = null;	// Previous Node
        this.next    = null;	// Next Node
    }

    public Node(T data){
    	this.data = data;
    	this.prior   = null;
        this.next    = null;
    }

	public T get(){ return this.data; }
	public Node getPrior()  { return this.prior;  }
	public Node getNext()   { return this.next;   }

	public void set ( T data ){ this.data = data; }
	public void setPrior   ( Node node    ){ this.prior   = node;    }
	public void setNext    ( Node node    ){ this.next    = node;    }

	public Object clone(){
		Node copy = null;

		try{ copy = (Node) super.clone(); }
		catch(CloneNotSupportedException err){ return null; }
		return copy;
	}
	public String toString(){ return this.data.toString(); }

The Linked List Class

A linked list is a collection nodes. There are a couple of things to consider when looking over this code. First, the forward() and backward() are used to traverse the list and I would re-write them as an iterator. Plus I’m pretty sure backward() doesn’t work. Normally you only traverse a linked list in a single direction so you can still use forward() to make the linked list usable. Second, I made a few minor changes and I haven’t tried compiling them yet so reader beware.

public class LinkedList<T> {
 private Node<T> prior; //Prior node in the list
 private Node<T> current; //Current node in the list
 private Node<T> head; //Head node in the list
 private Node<T> tail; //Tail node in the list
 private long range; //Length of the list
 private long index; //Pointer variable

 // Constructor
 public LinkedList() {
 this.prior = null;
 this.current = null;
 this.head = null;
 this.range = 0;
 this.index = 0;
 }

// Clears the linked list
 public void clear(){
 this.prior = null;
 this.current = null;
 this.head = null;
 this.range = 0;
 this.index = 0;
 }

 // Reinitialize the linked list
 public void reset(){
 if ( isEmpty() == true )
 this.clear();
 else {
 this.current = this.head;
 this.index = 0;
 }
 }

 // Returns true if list is empty
 public boolean isEmpty(){ return (this.head == null); }

 // Moves forward in the list
 public void forward(){
 this.prior = this.current;
 this.current = this.current.getNext();
 this.index++;
 }

 // Moves backward in the list
 public void backward(){
 this.current = this.prior;
 this.prior = this.prior.getPrior();
 this.index--;
 }

 // Prints the list
 public void print(){
 this.reset();
 String str = "";
 while (this.current != null){
 str += (this.current.toString() + " @" + index + " -> ");
 this.forward();
 }
 str += "null" + "\n";
 System.out.print(str);
 }

 // Returns the string content inside current
 public String retrieve(){
 if ( this.current != null )
 return this.current.toString();
 else
 return null;
 }

 // Updates the content of current node
 public void update(T data){
 if ( this.current != null )
 this.current.setData(data);
 }
 // Adds a new node at the beginning of the list
 public void addFirst(T data){
 Node<T> node = new Node<T>(data);

 if ( !this.isEmpty() ){
 node.setNext( this.head );
 this.tail.setPrior(node);
 } else
 this.tail = node; // If isEmptpy = true

 this.range++;
 this.index++;
 this.head = node;
 this.current = this.head;
 }

// Adds a new node at the end of the list
 public void addLast(T data){
 Node<T> node = new Node<T>(data);

 if ( !this.isEmpty() ){
 node.setPrior( this.tail );
 this.tail.setNext(node);
 } else
 this.head = node; // If isEmptpy = true

 this.range++;
 this.index++;
 this.tail = node;
 this.current = this.tail;
 }

// Inserts new node after current node
 public void insertAfter(T data){
 Node<T> node = new Node<T>(data); //Creates around the given element
 this.range++;

 if ( isEmpty() == true ) //-List empty check
 this.addFirst(data);

 else if ( this.current == this.tail ) //-End of list check
 this.addLast(data);

 else {
 node.setNext(this.current.getNext() );
 node.setPrior(this.current);

 this.current.setNext(node);
 this.prior = this.current;
 this.current = node;
 this.index++;
 }
 }

 // Inserts new node before current node
 public void insertBefore(T data){
 Node<T> node = new Node<T>(data); //Creates around the given element
 this.range++;

if ( isEmpty() == true ) //-List empty check
 this.addLast(data);

 else if ( this.current == this.head ) //-Start of list check
 this.addFirst(data);

 else{
 this.prior.setNext(node);
 node.setPrior(this.prior);

 node.setNext(this.current);
 this.current.setPrior(node);
 this.index++;
 }
 }

 // Removes the current node
 public void remove(){
 this.range--;
 if ( this.current == this.head ){
 this.head = this.head.getNext();
 this.current = this.head;

} else if ( this.current == this.tail ){
 this.prior.setNext(null);
 this.tail = this.prior;
 this.current = this.tail;

} else if( this.current != null ){
 this.prior.setNext( this.current.getNext() );
 this.current = this.prior;

 }
 }

 // Finds node position of a given data
 public boolean seekPattern(T pattern){
 boolean found = false;
 this.reset(); //Resets to the initial first node;

 while( found == false ){

 if (this.current.toString().equals(pattern.toString() ) == true)
 found = true;

 else if ( this.current != null )
 found = true;

 else
 this.forward();
 } //- !while

return found;
 }

// Finds nodes position by index position
 public boolean seekIndex(long i){
 boolean found = false;
 this.reset();

 while(!found && this.current != null){
 if (this.index == i)
 found = true;
 else
 this.forward();
 } //- !while

 return found;

}

//Node Setters
 public void setPriorNode (Node<T> node) { this.prior = node;}
 public void setCurrentNode(Node<T> node) { this.current = node;}
 public void setHeadNode (Node<T> node) { this.head = node;}
 public void setTailNode (Node<T> node) { this.tail = node;}

//Node Getters
 public Node<T> getPriorNode() { return this.prior; }
 public Node<T> getCurrentNode(){ return this.current; }
 public Node<T> getHeadNode() { return this.head; }
 public Node<T> getTailNode() { return this.tail; }

//!Node setters & getters
 public void setRange(long range) { this.range = range; }
 public void setIndex(long index) { this.index = index; }
 public long getRange() { return this.range; }
 public long getIndex() {return this.index; }

}

The Debugger Class
This is a sample class I used to test the my linked list class.

public class Debugger{
 private static LinkedList<String> linkList = new LinkedList<String>();

 public static void main(String[] args) {

//Uncomment out the function you want to test

//testPopulation();
 //testRemove();
 //testFindIndex();
 //testUpdate();
 }

 public static void testPopulation(){
 linkList.clear();
 System.out.println("List population test:");

 linkList.insertAfter("Dan");
 linkList.addFirst("Bit Diddler");
 linkList.insertBefore("Rex");
 linkList.insertAfter("Asdf");
 linkList.insertBefore("Jkl;");
 linkList.addLast("QuickBrownFox");
 linkList.print();
 //Output: Rex @0 -> Jkl; @1 -> Asdf @2 -> Bit Diddler @3 -> Dan @4 -> QuickBrownFox @5 -> null
 }

 public static void testUpdate(){
 System.out.println("List node update test:");

linkList.addFirst("Bit Diddler");
 linkList.seekPattern("Bit Diddler");
 linkList.update("Dan");
 linkList.print();

 //Output: Dan @0 -> null
 }

 public static void testRemove(){
 linkList.clear();
 System.out.println("List node removal & search by pattern test:");

linkList.addFirst("Dan");
 linkList.addFirst("Bit Diddler");
 linkList.seekPattern("Bit Diddler");
 System.out.println( "found" + linkList.retrieve() );
 linkList.remove("Bit Diddler");
 linkList.print();
 //Output: Dan @0 -> null
 }

 public static void testFindIndex(){
 linkList.clear();
 System.out.println("List search by index test:");

linkList.addFirst("Dan");
 boolean found = linkList.seekIndex(0);
 System.out.println( linkList.retrieve() );

found = linkList.seekIndex(-1000); //Outside the scope of the list
 System.out.println("-1000 = " + found);

found = linkList.seekIndex(1000); //Outside the scope of the list
 System.out.println("1000 = " + found);

 //-------------------------
 // 0 =  Dan
 // -1000 = false
 // 1000 = false
 //--------------------------
 }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s