linkedlist.java

java 实现常用数据结构（链表

/**
 *
 *
 *
 */
 
 package dreamer.util;
 
 class ListNode<T>
 {
 	protected T data;
 	protected ListNode previous;
 	protected ListNode next;
 }
 
 public class LinkedList<T> implements List<T>
 {
 	private ListNode head;
 	private ListNode tail;
 	private int len;
 	
 	public LinkedList()
 	{
 		head = new ListNode();
 		tail = new ListNode();
 		head.next = tail;
 		tail.previous = head;
 		len = 0;
 	}
 	
 	public boolean add(T elem)
 	{
 		ListNode node = new ListNode();
 		node.data = elem;
 		tail.previous.next = node;
 		node.previous = tail.previous;
 		node.next = tail;
 		tail.previous = node;
 		len++;
 		return true;
 	}
 	
 	public void add(int index,T elem)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		int i = -1;
 		ListNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			if(i==index)
 			{
 				ListNode node = new ListNode();
 				node.data = elem;
 				cursor.previous.next = node;
 				node.previous = cursor.previous;
 				node.next = cursor;
 				cursor.previous = node;
 				len++;
 				return;
 			}
 			cursor = cursor.next;
 		}
 	}
 	
 	public T remove(int index)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		int i = -1;
 		ListNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			if(i==index)
 			{
 				T elem = (T)cursor.data;
 				cursor.previous.next = cursor.next;
 				cursor.next.previous = cursor.previous;
 				len--;
 				return elem;
 			}
 			cursor = cursor.next;
 		}
 		return null;
 	}
 	
 	public boolean remove(T elem)throws IndexSlopOverException
 	{
 		if(len==0)
 			throw new IndexSlopOverException();
 		ListNode cursor = head.next;
 		final int LENGTH = len;
 		while(cursor!=tail)
 		{
 			if(cursor.data.equals(elem))
 			{
 				cursor.previous.next = cursor.next;
 				cursor.next.previous = cursor.previous;
 				len--;
 			}
 			cursor = cursor.next;
 		}
 		if(len==LENGTH)
 			return false;
 		return true;
 			
 	}
 	
 	public void set(int index,T elem)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		int i = -1;
 		ListNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			if(i==index)
 			{
 				cursor.data = elem;
 				return;
 			}
 			cursor = cursor.next;
 		}
 	}
 	
 	public T get(int index)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		int i = -1;
 		ListNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			if(i==index)
 			{
 				T elem = (T)cursor.data;
 				return elem;
 			}
 			cursor = cursor.next;
 		}
 		return null;
 	}
 	
 	public boolean contains(T elem)
 	{
 		if(indexOf(elem)==-1)
 			return false;
 		return true;
 	}
 	
 	public int indexOf(T elem)
 	{
 		int i = -1;
 		ListNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			if(cursor.data.equals(elem))
 				return i;
 			cursor = cursor.next;
 		}
 		return -1;
 	}
 	
 	public int size()
 	{
 		return len;
 	}
 	
 	public Object [] toArray()
 	{
 		if(len==0)
 			return null;
 		Object [] array = new Object[len];
 		int i = -1;
 		ListNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			array[i] = cursor.data;
 			cursor = cursor.next;			
 		}
 		return array;
 	}
 	
 	public boolean isEmpty()
 	{
 		if(len==0)
 			return true;
 		return false;
 	}
 	
 	public void clear()
 	{
 		ListNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			ListNode next = cursor.next;
 			cursor.previous = null; 			
 			cursor.next = null;
 			cursor = next;
 		}
 		head.next = tail;
 		tail.previous = head;
 		len = 0;
 	}
 }