Java之手写LinkedList(上)

/**
* @author dcc
*/
public class MyLinkedList<T> {
   /**
    * 链表元素的长度
    */
   private int size;
   /**
    * 链表的第一个节点
    */
   private Node<T> first;

   /**
    * 链表的最后一个节点
    */
   private Node<T> last;

   /**
    *向链表末尾添加一个新节点，该节点中的数据是参数t指定的对象
    * @param t
    * @return
    */
   public boolean add(T t){
      /**
       * 每次在添加的时候就创建一个节点
       */
       final Node<T> node = new Node<>(t);
      /**
       * 当第一次添加的时候就将节点赋值给first,表示第一个节点的引用
       */
      if(this.first == null){
          //第一个节点
          this.first = node;
          //第一次第一个节点和最后一个节点相同
          this.last = this.first;
      }else {
          /**
           *  因为每次add的时候都会add到最后一个节点上，
           *  那么这个时候last需要赋值给previousNode
           *  这个时候previousNode节点就变成倒数第二个节点了
           *  也就是说新的node节点变成last节点了
           *  并且previousNode变成了last节点的上一个节点了
           *  这样就证明LinkedList添加操作效率就比ArrayList操作效率高多了。
           */
          Node<T> previousNode = this.last;
          this.last = node;
          this.last.prev = previousNode;
          previousNode.next = this.last;
      }
      this.size++;
      return true;
   }

   /**
    * 这个内部类就是每次添加的节点
    * @param
    */
   private class Node<T>{
       /**
        * 要添加的数据
        */
       private T data;
       /**
        * 下个节点的引用
        */
       private Node<T> next;
       /**
        * 上一个节点引用
        */
       private Node<T> prev;

       /**
        * 每次构造的时候index加1
        * @param t
        */
       private Node(T t) {
           this.data = t;
       }
   }
}

//测试添加
MyLinkedList<String> list = new MyLinkedList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");

/**
* 获取数组长度
* @return
*/
public int size(){
  return this.size;
}

MyLinkedList<String> list = new MyLinkedList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
System.out.println(list.size());

结果：4

/**
* 得到指定位置的节点,
* @param index
* @return
*/
public T get(int index) {
   /**
    * size==0表示链表中没有数据,直接抛出异常
    * index>=size或者index<0，表示index索引已经越界，直接抛出异常
    */
   if (size == 0 || index >= size || index < 0) {
       throw new ArrayIndexOutOfBoundsException("下标越界!!!");
   }
   /**
    * 以上条件都不满足，那么就开始递归查询
    * 为什么大家都说LinkedList的get效率低呢？
    * 主要是因为get的时候需要逐个遍历来匹配获取数据，这样效率就低很多 了。
    * ArrayList是直接操作数组的，get也是直接在数组里面根据索引获取的。
    *
    * 因为linkedList是没有index属性的，所以需要定义一个临时索引
    * 因为需要逐个递归需要和索引比配上才能找到对应的元素
    */
   int tempIndex = 0;
   return first.get(index,tempIndex);
}

/**
* 获取index索引的节点
* @param index
* @return
*/
private T get(int index,int tempIndex) {
   /**
    * 匹配就直接返回了
    */
   if (index == tempIndex) {
       return this.data;
   }
   /**
    * 如果传入索引和临时索引不匹配将递归到下一个节点在进行匹配
    * 以此类推
    */
   return this.next.get(index,++tempIndex);
}

/**
* 向链表表头添加一个新节点，该节点中的数据是参数element指定的对象
* @param t
*/
public void addFirist(T t) {
   /**
    * 首先将first的引用保存在一个临时变量oldFirst中
    */
   Node oldFirst = this.first;
   /**
    * 将这个节点存放在first节点上
    */
   this.first = new Node<>(t);
   /**
    * 在这里需要将oldFirst节点也就是老的first节点，添加到新的first节点上
    */
   this.first.next = oldFirst;
   /**
    * 然后将first的引用赋值给oldFirst.prev就好了
    */
   oldFirst.prev = this.first;
   this.size++;
}