java学习札记—自定义实现linkedList集合

java学习笔记—自定义实现linkedList集合

/*
 * 自定义实现linkedList集合结构
 */
public class MyLinkedList {
	private Node firstNode; // 永远指向第一个元素
	private Node lastNode; // 永远指向最后一个元素
	private int size; //集合的长度

	// 添加元素
	public boolean add(Node node) {
		if (null == node) {
			throw new IllegalArgumentException("不允许null的Node元素");
		}
		if (null == firstNode) {
			firstNode = node; // 集合中没有元素，就把该元素赋值给第一个元素
		} else {
			Node lastNode = getLast();
			//双向链表
			lastNode.setNext(node); //指向的下一个元素
			node.setPrev(lastNode); //指向的上一个元素
		}
		lastNode=node; //把新添加的元素赋值给最后一个元素
		size++; //每添加一次长度加1
		return true;
	}
	
	//在列表的首部添加元素
	public void addFirst(Node node){
		if(node == null){
			throw new IllegalArgumentException("不允许null的Node元素");
		}
		if(firstNode == null){
			lastNode=node; 
		}else{
			Node n=getFirst();
			n.setPrev(node);
			node.setNext(n);
		}
		firstNode=node;
		size++;
	}
	
	//在列表的末尾添加元素
	public void addLast(Node node){
		if(node == null){
			throw new IllegalArgumentException("不允许null的Node元素");
		}
		if(lastNode == null){
			firstNode=node; 
		}else{
			Node n=getLast();
			n.setNext(node);
			node.setPrev(n);
		}
		lastNode=node;
		size++;
	}
	
	//删除列表中第一个元素
	public void removeFirst(){
		Node node=firstNode.getNext();
		node.setPrev(null);
		firstNode=node;
		size--;
	}
	
	//删除列表中最后一个元素
	public void removeLast(){
		Node node=lastNode.getPrev();
		node.setNext(null);
		lastNode=node;
		size--;
	}
	
	//删除列表中指定的元素
	public void remove(int index){
		if(index < 0 || index >= size){
			throw new ArrayIndexOutOfBoundsException();
		}
		if (null == firstNode) {
			throw new IllegalStateException("集合中没有元素");
		}
		int i=0;
		Node node=firstNode;
		if(index == 0){
			node=node.getNext();
			node.setPrev(null);
			firstNode=node;
			size--;
			return;
		}
		if(index == (size-1)){
			node=lastNode.getPrev();
			node.setNext(null);
			lastNode=node;
			size--;
			return;
		}
		if(index<size/2){
			while(i!=index){
				node=node.getNext();
				i++;
			}
		}else{
			i=size-1;
			node=lastNode;
			while(i!=index){
				node=node.getPrev();
				i--;
			}
		}
		Node next=node.getNext();
		Node prev=node.getPrev();
		next.setPrev(prev);
		prev.setNext(next);
		size--;
	}
	
	/*
	 * 返回此列表中指定位置处的元素(二分法)
	 */
	public Node get(int index) {
		if(index < 0 || index >= size){
			throw new ArrayIndexOutOfBoundsException();
		}
		if (null == firstNode) {
			throw new IllegalStateException("集合中没有元素");
		}
		int i=0;
		Node node;
		if(index<size/2){
			node=firstNode;
			while(i!=index){
				node=node.getNext();
				i++;
			}
		}else{
			i=size-1;
			node=lastNode;
			while(i!=index){
				node=node.getPrev();
				i--;
			}
		}
		return node;
	}
	/*
	 * 返回此列表中指定位置处的元素(普通方法)
	 */
	public Node myGet(int index) {
		if(index < 0 || index >= size){
			throw new ArrayIndexOutOfBoundsException();
		}
		if (null == firstNode) {
			throw new IllegalStateException("集合中没有元素");
		}
		int i=0;
		Node node=firstNode;
		while(i!=index){
			node=node.getNext();
			i++;
		}
		return node;
	}

	/*
	 * 获取最后一个元素
	 */
	public Node getLast() {
		if (null == firstNode) {
			throw new IllegalStateException("集合中没有元素");
		}
		return lastNode;
	}
	
	/*
	 * 获取最后一个元素
	 */
	public Node getFirst() {
		if (null == firstNode) {
			throw new IllegalStateException("集合中没有元素");
		}
		return firstNode;
	}

	/*
	 * 获取集合长度
	 */
	public int size() {
		return size;
	}
}