ArrayList和LinkedList

（1）LinkedList

LinkedList底层结构实现和ArrayList底层数据结构实现有着本质上的区别 ArrayList底层实现主要依赖数组，而LinkedList底层实现则是依赖链表。

/**

• LinkedList的实现是双向链表，因此需要定义首节点和尾结点。

• 并且需要保存链表中元素的个数。此外，还需要提供无参构造方法，

• 在构造方法内初始化一个空链表。 */ public class MyLinkedList { private Node first; private Node last; private int size;

  /**

在尾部添加节点

@param o

@return */

public boolean add(Object o){

????????if(size == 0){

????????????????Node newNode = new Node(null,o,null);

????????????????first = newNode; last = newNode;

????????}else{

????????????????//实例化新节点

????????????????Node newNode = new Node(last,o,null);

????????????????last.next = newNode; last = newNode;

????????} size++;

????????return true;

}

/**
 * 在指定索引处添加节点
 * @param index
 * @param o
 * @return
 */
public boolean add(int index,Object o){
 ?  if(index<0 || index>size){
 ? ? ?  throw new IndexOutOfBoundsException("越界！");
 ?  }
 ?  if(index == 0){
 ? ? ?  //获取指定索引处的节点
 ? ? ?  Node newNode = getNode(index);
 ? ? ?  //获取首节点的前置节点
 ? ? ?  Node pre = first.pre;
 ? ? ?  //首节点的前置节点指向新节点
 ? ? ?  pre.next = newNode;
 ? ? ?  //将新节点作为首节点
 ? ? ?  first = newNode;
 ? ? ?  size++;
 ?  }
 ?  if(index == size){
 ? ? ?  //直接将对象添加到尾部
 ? ? ?  add(o);
 ?  }
 ?  //获取索引的节点
 ?  Node indexNode = getNode(index);
 ?  //获取索引节点的前置节点
 ?  Node preNode = indexNode.pre;
 ?  //实例化新节点 per指向索引节点的前置节点，next指向索引节点的后置节点
 ?  Node newNode = new Node(preNode,o,indexNode);
 ?  //索引节点前置节点的next指向新节点
 ?  preNode.next = newNode;
 ?  //索引节点的pre指向新节点
 ?  indexNode.pre = newNode;
 ?  size++;
 ?  return true;
}
?
/**
 * 删除对应索引处的节点
 * @param index
 * @return
 */
public Object remove(int index){
 ?  if(index<0 || index>=size){
 ? ? ?  throw new IndexOutOfBoundsException("越界");
 ?  }
 ?  //初始化返回的值
 ?  Object o = null;
 ?  //删除首节点
 ?  if(index ==0) {
 ? ? ?  //获取首节点的节点值
 ? ? ?  o = first.date;
 ? ? ?  //获取首节点的后置节点
 ? ? ?  Node node = first.next;
 ? ? ?  //首节点的next为null
 ? ? ?  first.next = null;
 ? ? ?  //将首节点的后置节点作为首节点
 ? ? ?  first = node;
 ?  }
 ?  //删除尾节点
 ?  else if(index == size-1){
 ? ? ?  o = last.date;
 ? ? ?  //获取尾节点的前置节点
 ? ? ?  Node perNode = last.pre;
 ? ? ?  //尾节点的前置节点的next置为null
 ? ? ?  perNode.next = null;
 ? ? ?  //将索引节点的尾节点作为尾节点
 ? ? ?  last = perNode;
 ?  }else{
 ? ? ?  //删除中间节点
 ? ? ?  //获取索引处节点
 ? ? ?  Node indexNode = getNode(index);
 ? ? ?  o = indexNode.date;
 ? ? ?  //获取索引节点的前置节点
 ? ? ?  Node preNode = indexNode.pre;
 ? ? ?  //获取索引节点的后置节点
 ? ? ?  Node nextNode = indexNode.next;
 ? ? ?  //将索引节点的前置节点指向索引节点的后置节点
 ? ? ?  preNode.next = nextNode;
 ? ? ?  //将索引节点的后置节点指向索引节点的前置节点
 ? ? ?  nextNode.pre = preNode;
 ? ? ?  //将索引节点的pre置为null
 ? ? ?  indexNode.pre = null;
 ? ? ?  //将索引节点的next置为null
 ? ? ?  indexNode.next = null;
 ?  }
 ?  size--;
 ?  return o;
}
?
/**
 * 修改索引处节点的元素值
 * @param index
 * @param o
 * @return
 */
public Object set(int index,Object o){
 ?  if(index<0||index>=size){
 ? ? ?  throw new IndexOutOfBoundsException("越界！");
 ?  }
 ?  //获取对应索引处的节点
 ?  Node indexNode = getNode(index);
 ?  //获取要删除节点的值
 ?  Object oldValue = indexNode.date;
 ?  //将要修改的值赋值给目标节点
 ?  indexNode.date = o;
 ?  return oldValue;
}
?
/**
 * 获取双向链表的容量
 * @return
 */
public int size(){
 ?  return size;
}
?
/**
 * 获取对应索引处节点的元素值
 * @param index
 * @return
 */
public Object get(int index){
 ?  return getNode(index).date;
}
?
/**
 * 获取对应索引处的Node对象
 * @param index
 * @return
 */
public Node getNode(int index){
 ?  if(index<0 || index>=size){
 ? ? ?  throw new  IndexOutOfBoundsException("越界");
 ?  }
 ?  //获取首节点
 ?  Node current = first;
 ?  for (int i = 0; i < index&&current!=null; i++) {
 ? ? ?  //获取下一个节点
 ? ? ?  current = current.next;
 ?  }
 ?  return current;
}
?
/**
 * 定义链表数据节点
 */
private class Node{
 ?  private Node pre;
 ?  private Object date;
 ?  private Node next;
?
 ?  public Node(Node pre,Object o,Node next){
 ? ? ?  this.pre = pre;
 ? ? ?  this.date = o;
 ? ? ?  this.next = next;
 ?  }
}

}

/**

• 测试类 */ public class Test { public static void main(String[] args) { MyLinkedList list = new MyLinkedList(); list.add("111"); list.add("222"); list.add("333"); list.add("444"); list.set(1,"777"); list.set(2,"888"); list.remove(0); list.remove(1); System.out.println("-------------"); for (int i = 0; i <list.size(); i++) { System.out.println(list.get(i)); } } }

（2） ArrayList和LinkedList的区别

    1、ArrayList和LinkedList都实现了List接口
    2、ArrayList和LinkedList都是非线程安全的，因此在多线程环境下可能会出现出现不同步的情况
    3、ArrayList底层实现是数组，LinkedList底层实现是双向链表
    4、ArrayList因为底层实现是数组，并且支持随机访问因此查找效率高，但是ArrayList在新增元素时会扩容以及复制数组元素，并且删除时也会进行数组复制，所以增删效率低。而LinkedList不支持随机访问，获取元素时必须从首节点开始从前往后遍历查找，因此查找效率低。但是增加和删除时最多涉及到两个节点的操作，因此增删效率高。

（3） Queue

    Queue 队列通常是指"先进先出"（FIFO）的容器。队列的头部保存在队列中存放时间最长的元素，队列的尾部保存在队列中存放时间最短的元素。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。
    
    boolean add(Object e)∶将指定元素加入此队列的尾部。
    Object element()∶获取队列头部的元素，但是不删除该元素。
    boolean offer(Object e)∶将指定元素加入此队列的尾部。当使用有容量限制的队列时，此方法通常比 add(Object e)方法更好。
    Object peek()∶获取队列头部的元素，但是不删除该元素。如果此队列为空，则返回 null。
    Object poll()∶获取队列头部的元素，并删除该元素。如果此队列为空，则返回 null。
    Object remove()∶获取队列头部的元素，并删除该元素。

public class QueueDemo {

????????public static void main(String[] args) {

????????????????Queue<String> queue= new LinkedList<>();

????????????????//添加元素

????????????????queue.offer("111");

????????????????queue.offer("222");

????????????????queue.offer("333");

????????????????queue.offer("444");

????????????????//添加失败时会抛出异常

????????????????queue.add("555");

????????????????//删除失败时会抛出异常

????????????????queue.remove("555");

????????????????for(String q:queue){

????????????????????????System.out.println(q);

????????????????}

????????????????System.out.println("-----------");

????????????????//返回第一个元素，并在列表中删除

????????????????queue.poll();

????????????????for(String q:queue){

????????????????????????System.out.println(q);

????????????????}

????????????????System.out.println("-----------");

????????????????//返回第一个元素

????????????????System.out.println(queue.element());

????????????????System.out.println("-----------");

????????????????//返回第一个元素

????????????????System.out.println(queue.peek());

? ? ? ? ? ? ? ? System.out.println("-----------");

????????????}

}