linkedlist.java

Java code Bankline to allocated the source for next

/**
 * Title:         LinkedList.java
 * Description:   Contains classes for linked list
 *
 * (for Lab03 Q1, Q2 & Q3)
 */

import java.util.Iterator;

class ListNode {

	private Object data;
	private ListNode next;

	public ListNode(Object o) { data = o; next = null; }
	public ListNode(Object o, ListNode nextNode)
		{ data = o; next = nextNode; }

	public Object getData() { return data; }
	public void setData(Object o) { data = o; }

	public ListNode getNext() { return next; }
	public void setNext(ListNode next) { this.next = next; }

} // class ListNode

class EmptyListException extends RuntimeException {
	public EmptyListException ()
		{ super("List is empty"); }
} // class EmptyListException

public class LinkedList {

	protected ListNode head;
	protected ListNode tail;

	protected int length;		// the length of the list

	public LinkedList() {
		head = tail = null;
		length = 0;
	}

	public boolean isEmpty() { return head == null; }

	public void addToHead(Object item) {
		if (isEmpty())
			head = tail = new ListNode(item);
		else
			head = new ListNode(item, head);
		length++;
	}

	public void addToTail(Object item) {
		if (isEmpty())
			head = tail = new ListNode(item);
		else {
			tail.setNext(new ListNode(item));
			tail = tail.getNext();
		}
		length++;
	}

	public Object removeFromHead() throws EmptyListException {
		Object item = null;
		if (isEmpty())
			throw new EmptyListException();
		item = head.getData();
		if (head == tail)
			head = tail = null;
		else
			head = head.getNext();
		length--;
		return item;
	}

	public Object removeFromTail() throws EmptyListException {
		Object item = null;
		if (isEmpty())
			throw new EmptyListException();
		item = tail.getData();
		if (head == tail)
			head = tail = null;
		else {
			ListNode current = head;
			while (current.getNext() != tail)
				current = current.getNext();
			tail = current;
			current.setNext(null);
		}
		length--;
		return item;
	}

	public void print() {
		System.out.print("[ ");
		ListNode current = head;
		while (current != null) {
			System.out.print(current.getData() + " ");
			current = current.getNext();
		}
		System.out.print("]");
		System.out.print(" head: " + (head == null ? "null" : head.getData()));
		System.out.print(" tail: " + (tail == null ? "null" : tail.getData()));
	}

	public String toString() {
		String str = "[ ";
		ListNode current = head;
		while (current != null) {
			str = str + current.getData() + " ";
			current = current.getNext();
		}
		return str + " ]";
	}

	public int count() {
		/*
		ListNode current = head;
		int i = 0;
		while (current != null) {
			i++;
			current = current.getNext();
		}
		*/
		return length;
	}

	public Object remove(int n) {
		Object item = null;
		if (n <= length) { // make sure there is nth node to remove
			// special treatment for first and last nodes
			if (n == 1) return removeFromHead();
			if (n == length) return removeFromTail();
			// removal of nth node which has nodes in front and behind
			ListNode current = head;
			ListNode previous = null;
			for (int i = 1; i < n; i++) { // current will point to nth node
				previous = current;
				current = current.getNext();
			}
			// data to be returned
			item = current.getData();
			// remove the node by adjusting two pointers (object reference)
			previous.setNext(current.getNext());
		}
		length--;
		return item;
	}

	public void add(int n, Object item) {
		// special treatment for insert as first node
		if (n == 1) {
			addToHead(item);
			return;
		}
		// special treatment for insert as last node
		if (n > length) {
			addToTail(item);
			return;
		}
		// locate the n-1th node
		ListNode current = head;
		for (int i = 1; i < n-1; i++)	// current will point to n-1th node
			current = current.getNext();
		// create new node and insert at nth position
		current.setNext(new ListNode(item, current.getNext()));
		length++;
	}

	public Object get(int n) {
		// n is too big, no item can be returned
		if (length < n) return null;
		// locate the nth node
		ListNode current = head;
		for (int i = 1; i < n; i++)
			current = current.getNext();
		return current.getData();
	}


	// ADVANCED methods for ORDERED LIST

	public Object remove(String s) {	// remove() is overloaded

		//***** method 1: traverse the list with current & previous links
		ListNode current = head;
		ListNode previous = null;

		// locate s
		while (current != null) {
			if (((String)current.getData()).compareToIgnoreCase(s) < 0) {
				previous = current;
				current = current.getNext();
			}
			else {
				break;	// current points to a node with string >= s
			}
		} // while

		// Now, check if current is pointing to a node

		if (current == null) return null;	// No, just return null

		// Yes, check if current is pointing to the target string

		// The node is not s, return null
		if (!((String)current.getData()).equals(s)) return null;

		// target string found, let's remove the node
		if (previous == null) {	// current points to the 1st node
			return removeFromHead();
		}
		if (current == tail) {	// current points to the last node
			return removeFromTail();
		}
		// remove a node in between two nodes
		Object item = current.getData();
		previous.setNext(current.getNext());
		length--;	// make sure to decrement the length
		return item;
		//*** end of method 1 */

        /*
		//***** method 2: an alternative without using the previous link
		// locate string s
		int i = 0;	// position of node that may contain string s
		ListNode current = head;
		while (current != null) {
			i++;
			if (((String)current.getData()).compareToIgnoreCase(s) < 0)
				current = current.getNext();
			else
				break;	// current points to a node with string >= s
		}
		// current points to no node means that the list does not contain s
		if (current == null) return null;
		// current does points to a node
		if (((String)current.getData()).compareToIgnoreCase(s) == 0)
			// the node contains string s
			return remove(i);
		else
			// the node does not contain string s
			return null;
		//*** end of method 2 */

	} // remove(String s)


	public void insert(String s) {

		//***** method 1: traverse the list with current & previous links
		// check if the list is empty
		if (isEmpty()) {
			addToHead(s);
			return;
		}

		// traverse the list to locate the insertion point (current)
		ListNode current = head;
		ListNode previous = null;
		while (current != null) {
			if (((String)current.getData()).compareToIgnoreCase(s) < 0) {
				previous = current;
				current = current.getNext();
			}
			else {
				break;	// current points to a node with string >= s
			}
		} // while

		// Now, check if current is pointing to a node

		if (current == null) {	// No, passed end of list
			addToTail(s);
			return;
		}

		if (previous == null) {	// s should be the first node
			addToHead(s);
			return;
		}

		// Yes, insert s at current (after previous)
		previous.setNext(new ListNode(s, current));
		length++;
		//*** end of method 1 */

        /***** method 2: an alternative with previous link only
		// check special case of inserting at front
		if (head == null) {
			addToHead(s);
			return;
		}
		else if (s.compareToIgnoreCase((String)head.getData()) <= 0) {	// s <= getData()
			addToHead(s);
			return;
		}

		// locate where to insert
		ListNode previous = head;
		while (previous.getNext() != null) {
			if (((String)previous.getNext().getData()).compareToIgnoreCase(s) < 0) { // getData() < s
				previous = previous.getNext();	// advance to next node
			}
			else {
				break;
			}
		}
		// insertion point located
		if (previous.getNext() == null) {	// insert s to the tail
			addToTail(s);
			return;
		}
		// now, insert s after previous
		previous.setNext(new ListNode(s, previous.getNext()));
		length++;
		//*** end of method 2 */

        /***** method 3: an alternative without the previous link
		// locate the node >= s
		int i = 0;	// position of located node
		ListNode current = head;
		while (current != null) {
			i++;
			if (((String)current.getData()).compareToIgnoreCase(s) < 0)
				current = current.getNext();
			else
				break;	// current points to a node with string >= s
		}
		if (current == null)
			// string s is the largest
			addToTail(s);
		else
			// insert s at position i
			add(i, s);
		//*** end of method 3 */

		return;

	} // insert(String s)


	// MyIterator inner class
	class MyIterator implements Iterator {

		private ListNode current;

		public MyIterator() {
			current = head;
		}

		public boolean hasNext() {
			return current != null;
		}

		public Object next() {
			Object item = current.getData();
			current = current.getNext();
			return item;
		}

		public void remove() {	// remove is not available
			throw new UnsupportedOperationException();
		}

	} // class ListIterator


	// iterator method
	public Iterator iterator() {
		return new MyIterator();
	}


} // class LinkedList