linkedset.java

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

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