睡不着写算法（二）

循环链表

package algorithms;

/**
 * 链表
 * @author henry
 * @date 2010-06-04  1:06:22
 */
public class MyLinkedList {

	private static MyNode myNode;
	private static int size = 0;

	public MyLinkedList() {
		// TODO Auto-generated constructor stub
		myNode = new MyNode();
	}

	/**
	 * 插入链表
	 * @param obj
	 */
	public void put(Object obj) {
		if(size == 0) {
			myNode.header = myNode;
			myNode.put(obj);
			myNode.next = myNode;
			size++;
			return;
		}
		
		MyNode node = new MyNode();
		node.header = myNode.header;
		node.put(obj);
		node.next = myNode;
		
		myNode.header.next = node;
		myNode.header = node;
		size++;
	}

	/**
	 * 获取链表大小
	 * @return
	 */
	public int size() {
		return size;
	}

	/**
	 * 正向获取
	 * @param idx
	 * @return
	 */
	public Object get(int idx) {
		if(idx >= size) {
			throw new OutOfMemoryError();
		}
		MyNode mn = myNode;
		Object obj = null;
		for(int i = 0; i < size; i++) {
			if(i == idx) {
				obj = mn.get();
				break;
			}
			
			mn = mn.next;
		}
		
		return obj;
	}

	/**
	 * 正向删除
	 * @param idx
	 * @return
	 */
	public Object remove(int idx) {
		if(idx >= size) {
			throw new OutOfMemoryError();
		}
		MyNode mn = myNode;
		Object obj = null;
		if(idx == 0) {
			obj = mn.get();
			mn.next.header = mn.header;
			myNode = mn.next;
			mn = null;
			size--;
			
			return obj;
		}
		
		for(int i = 0; i < size; i++) {
			if(i == idx) {
				obj = mn.get();
				mn.header.next = mn.next;
				mn.next.header = mn.header;
				size--;
				mn = null;
				break;
			}
			mn = mn.next;
		}
		
		return obj;
	}
	
	/**
	 * 反向删除链表
	 * @param idx
	 * @return
	 */
	public Object reverse(int idx) {
		if(idx >= size) {
			throw new OutOfMemoryError();
		}
		MyNode mn = myNode.header;
		Object obj = null;
		
		if(idx == 0) {
			obj = mn.get();
			myNode.header = mn.header;
			mn.header.next = mn.header;
			mn = null;
			size--;
			return obj;
		}
		
		for(int i = 0; i < size; i++) {
			if(i == idx) {
				obj = mn.get();
				mn.header.next = mn.next;
				mn.next.header = mn.header;
				size--;
				mn = null;
				break;
			}
			mn = mn.header;
		}
		
		return obj;
	}
	
	/**
	 * 反向链表
	 * @param idx
	 * @return
	 */
	public Object getReverse(int idx) {
		if(idx >= size) {
			throw new OutOfMemoryError();
		}
		MyNode mn = myNode.header;
		Object obj = null;
		for(int i = 0; i < size; i++) {
			if(i == idx) {
				obj = mn.get();
				break;
			}
			
			mn = mn.header;
		}
		
		return obj;
		
	}

	private static class MyNode {

		private MyNode header;
		private Object obj;
		private MyNode next;

		public MyNode() {
			// TODO Auto-generated constructor stub
			header = null;
			obj = null;
			next = null;
		}

		public void put(Object o) {
			obj = o;
		}
		
		public Object get() {
			return this.obj;
		}
	}
	
	public static void main(String[] args) {
		MyLinkedList mll = new MyLinkedList();
		for(int i = 0; i < 10; i++) {
			mll.put(i + "");
		}
		
		for(int i = 0; i < mll.size(); i++) {
			String a = (String) mll.get(i);
			System.out.print(a + " ");
		}
		
		System.out.println();
		System.out.println("删除前的大小：" + mll.size());
		
		System.out.println(mll.remove(0));
		System.out.println(mll.size());
		
		for(int i = 0; i < mll.size(); i++) {
			String a = (String) mll.get(i);
			System.out.print(a + " ");
		}
		
		System.out.println();
		
		System.out.println(mll.reverse(5));
		System.out.println(mll.size());
		
		for(int i = 0; i < mll.size(); i++) {
			String a = (String) mll.getReverse(i);
			System.out.print(a + " ");
		}
	}
}