package com.zkn.newlearn.collection;
/**
 * 
 * @author zkn 2016-06-25
 *  LinkedList的內(nèi)部數(shù)據(jù)結(jié)構(gòu)是雙向鏈表，
 *  所以定義一個內(nèi)部類与涡，用來表示一個節(jié)點(diǎn)峭梳，
 *  這個節(jié)點(diǎn)包括三個屬性，
 *      1虱而、一個用來表示當(dāng)前元素
 *      2筏餐、一個用來表示上一個元素
 *      3、一個用來表示下一個元素
 *  還需要兩個屬性節(jié)點(diǎn)用來保存鏈表的頭和尾
 */
public class ImitateLinkedListTest02<E> {
    /**
     * 表示頭部
     */
    private Node<E> first;
    /**
     * 表示尾部
     */
    private Node<E> last;
    /**
     * size的大小
     */
    private int size;
    /**
     * 元素的個數(shù)
     */
    public int size(){
        
        return size;
    }
    /**
     * add的方法
     * @param e
     */
    public void add(E e){
        //說明這個時候還沒有進(jìn)行過add操作牡拇，即鏈表中沒有元素
        if(last == null){
            //創(chuàng)建一個新的節(jié)點(diǎn)
            //對于第一個節(jié)點(diǎn)魁瞪，它的上一個元素為不存在所以為null，下一個元素同樣為null
            Node<E> newNode = new Node<E>(e,null,null);
            //在這個鏈表中惠呼，第一個元素為當(dāng)前要插入的節(jié)點(diǎn)导俘，最后一個元素同樣為當(dāng)前要插入的節(jié)點(diǎn)
            first = newNode;
            last = newNode;
        }else{
            //對于鏈表中已經(jīng)存在元素節(jié)點(diǎn)的情況
            //創(chuàng)建出來一個新的節(jié)點(diǎn)
            //對于這種鏈表中已經(jīng)有幾點(diǎn)存在的情況，它的上一個節(jié)點(diǎn)為最后一個元素剔蹋，下一個節(jié)點(diǎn)為null
            Node<E> newNode = new Node<E>(e,last,null);
            //當(dāng)前的最后一個元素的下一個節(jié)點(diǎn)應(yīng)該指向當(dāng)前要插入的這個節(jié)點(diǎn)旅薄。
            //當(dāng)前最后一個元素的下一個節(jié)點(diǎn)指向當(dāng)前要插入的節(jié)點(diǎn)，當(dāng)前要插入的節(jié)點(diǎn)的上一個元素指向當(dāng)前的最后一個元素
            //這樣正好構(gòu)成了一個雙向鏈表
            last.next = newNode;
            //最后泣崩，要把最后一個元素節(jié)點(diǎn)變?yōu)楫?dāng)前插入的元素節(jié)點(diǎn)
            last = newNode;
        }
        size++;
    }
    /**
     * 根據(jù)元素位置取元素的值
     * 從這個例子中就可以看出來少梁，為什么LinkedList獲取元素比較慢洛口，因為每次取出元素都有進(jìn)行一次循環(huán)！？Α５谘妗！
     * @param size
     * @return
     */
    public E get(int index){
        checkSize(index);
        //獲取元素的值
        //如果索引小于當(dāng)前元素個數(shù)的一半妨马，就從頭部開始循環(huán)挺举，否則從尾部開始循環(huán)
        if(index < (size >> 1)){
            //把頭給節(jié)點(diǎn)，便于下面遞歸循環(huán)
            Node<E> node = first;
            for(int i=0;i<index;i++){
                //循環(huán)遞歸
                node = node.next;
            }
            //返回節(jié)點(diǎn)中的元素
            return node.item;
        }else{
            //把尾給節(jié)點(diǎn)身笤，便于下面遞歸循環(huán)
            Node<E> node = last;
            for(int i=size-1;i>index;i--){
                node = node.prev;
            }
            return node.item;
        }
    }
    /**
     * 獲取第一個元素
     * @return
     */
    public E getFirst(){
        
        if(first == null)
            return null;
        return first.item;
    }
    /**
     * 獲取最后一個元素
     * @return
     */
    public E getLast(){
        
        if(last == null)
            return null;
        return last.item;
    }
    /**
     * 移除對象
     * @return
     */
    public boolean remove(Object obj){
        
        //分兩種情況來處理
        //如果obj == null
        if(obj == null){
            for(Node<E> x = first;x != null;x = x.next){
                if(x.item == null){
                    removeElement(x);
                    return true;
                }
            }
        }else{
            for(Node<E> x = first;x != null;x = x.next){
                if(obj.equals(x.item)){
                    removeElement(x);
                    return true;
                }
            }
        }
        return false;
    }
    
    private E removeElement(Node<E> node) {
        E itemElement = node.item;
        //用來保存prev節(jié)點(diǎn)豹悬，防止后面 當(dāng)node節(jié)點(diǎn)是最后一個節(jié)點(diǎn)的時候， node.prev=null液荸，last為null
        Node<E> prevNode = node.prev;
        //說明node為first節(jié)點(diǎn)
        if(node.prev == null){
            //first節(jié)點(diǎn)的時候需要把node.next變?yōu)閒irst
            first = node.next;
        }else{
            //如果node不是first節(jié)點(diǎn)瞻佛，則把他的上個節(jié)點(diǎn)的指向變成當(dāng)前node的下一個節(jié)點(diǎn)
            //然后把這個節(jié)點(diǎn)的上個節(jié)點(diǎn)的變?yōu)閚ull 相當(dāng)于打斷節(jié)點(diǎn)的左面
            node.prev.next = node.next;
            node.prev = null;
        } 
        //如果node為last節(jié)點(diǎn)
        if(node.next == null){
            //說明node的上一個節(jié)點(diǎn)為last節(jié)點(diǎn)
            last = prevNode;
        }else{
            //說明如果node不是last幾點(diǎn)，則把node節(jié)點(diǎn)的指向的下一個元素的上一個節(jié)點(diǎn)變?yōu)楫?dāng)前node的上一個節(jié)點(diǎn)
            //然后把當(dāng)前node節(jié)點(diǎn)的next變?yōu)閚ull 相當(dāng)于打斷節(jié)點(diǎn)的右面
            node.next.prev = prevNode;
            node.next = null;
        }
        node.item = null;
        size --;
        return itemElement;
    }
    /**
     * 檢查元素是否合法
     * @param size2
     */
    private void checkSize(int index) {
        if(index >= size || index < 0){
            throw new IllegalArgumentException("輸入的參數(shù)不合法娇钱，請輸入合法的參數(shù)");
        }
    }
    /**
     * 雙向鏈表的節(jié)點(diǎn)
     * @author zkn
     *
     * @param <E>
     */
    private static class Node<E>{
        //當(dāng)前元素
        E item;
        //上一個
        Node<E> prev;
        //下一個
        Node<E> next;
        
        public Node(E item, Node<E> prev, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }
    
    public static void main(String[] args){
        
        ImitateLinkedListTest02<String> linkedList = new ImitateLinkedListTest02<String>();
        linkedList.add("張三");
        linkedList.add("李四");
        linkedList.add("馬六");
        linkedList.add("王五");
        
        linkedList.remove("馬六1");
        
        System.out.println(linkedList.size());
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        for(int i=0;i<linkedList.size;i++){
            System.out.print(linkedList.get(i)+"->");
        }
        System.out.println("");
    }
}