package cn.zhazong710.test;

public class Node {
	
	Node previous;  //上一个节点
	Node next;      //下一个节点
	Object element; //元素数据
	
	public Node(Node previous,Node next,Object element) {
		super();
		this.previous = previous;
		this.next = next;
		this.element = element;
	}

	public Node(Object element) {
		super();
		this.element = element;
	}
}

package cn.zhazong710.test;

public class ZZLinkedList<E> {
	
	private Node first;
	private Node last;
	
	private int size;
	
	public void add(int index,E element) {  //指定位置增加元素
		
		checkRange(index);
		
		Node newNode = new Node(element);
		Node temp = getNode(index);
		
		if(temp!=null) {
			
			Node up = temp.previous;
			
			up.next = newNode;
			newNode.previous = up;
			
			newNode.next = temp;
			temp.previous = newNode;
			
		}
		
	}
	
	public void remove(int index) {  //删除指定元素
		
		checkRange(index);
		
		Node temp = getNode(index);
		
		if(temp!=null) {
			
			Node up = temp.previous;
			Node down = temp.next;
			
			if(up!=null) {
				up.next = down;
			}
			
			if(down!=null) {
				down.previous = up;
			}
			//第一个元素被删除
			if(index==0) {
				first = down;
			}
			//第二个元素被删除
			if(index==size-1) {
				last = up;
			}
			
			size--;
		}
		
	}
	
	public E get(int index) {  //索引查找
		
		checkRange(index);
		
		Node temp = getNode(index);
		
		return temp!=null?(E)temp.element:null;
	}
	
	private void checkRange(int index) {  //检查长度合法性
		if(index<0||index>size-1) {
			throw new RuntimeException("索引数字不合法"+index);
		}
	}
	
	private Node getNode(int index) {  //折半查找
		
		checkRange(index);
		
		Node temp = null;
		
		if(index<=(size>>1)) {  //size>>1相当于除以2
			temp = first;
			for(int i=0;i<index;i++) {
				temp = temp.next;
			}
		}else {
			temp = last;
			for(int i=size-1;i>index;i--) {
				temp = temp.previous;
			}
		}
		
		return temp;
	}
	
	public void add(E element) {  //最后增加一个元素
		
		Node node = new Node(element);
		
		if(first==null) {
			
			first = node;
			last = node;
			
		}else {
			
			node.previous = last;
			node.next = null;
			
			last.next = node;
			last = node;
			
		}	
		size++;
	}
	
	@Override
	public String toString() {
		
		StringBuilder sb = new StringBuilder("[");
		Node temp = first;
		while(temp!=null){
			sb.append(temp.element+",");
			temp = temp.next;
		}
		sb.setCharAt(sb.length()-1,']');
		return sb.toString();
	}
	
	public static void main(String[] args) {
		
		ZZLinkedList<String> list = new ZZLinkedList<>();
		
		list.add("a");
		list.add("b");
		list.add("c");
		list.add("d");
		list.add("e");
		list.add("f");
		list.add("g");
		
		System.out.println(list);
		
	}
	
}