Vector，LinkedList

LinkedList

1. LinkedList底层实现了双向链表和双端队列特点

2. 可以添加任意元素（元素可以重复），包括null

3. 线程不安全，没有实现同步

LinkedList的底层操作机制

1. LinkedList底层维护了一个双向链表

2. LinkedList中维护了两个属性first和last分别指向首节点和尾节点

3. 每个节点（Node）对象，里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表

4. 所以LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高

5. package com.jshedu.List_;/* @author 韩顺平* @version 1.0*/
   public class LinkedList01 {public static void main(String[] args) {//模拟一个简单的双向链表Node jack = new Node("jack");Node tom = new Node("tom");Node hsp = new Node("老韩");//连接三个结点，形成双向链表//jack -> tom -> hspjack.next = tom;tom.next = hsp;//hsp -> tom -> jackhsp.pre = tom;tom.pre = jack;Node first = jack;//让first引用指向jack,就是双向链表的头结点Node last = hsp; //让last引用指向hsp,就是双向链表的尾结点//演示，从头到尾进行遍历System.out.println("===从头到尾进行遍历===");while (true) {if(first == null) {break;}//输出first 信息System.out.println(first);first = first.next;}//演示，从尾到头的遍历System.out.println("====从尾到头的遍历====");while (true) {if(last == null) {break;}//输出last 信息System.out.println(last);last = last.pre;}//演示链表的添加对象/数据，是多么的方便//要求，是在 tom --------- 老韩直接，插入一个对象 smith//1. 先创建一个 Node 结点，name 就是 smithNode smith = new Node("smith");//下面就把 smith 加入到双向链表了smith.next = hsp;smith.pre = tom;hsp.pre = smith;tom.next = smith;//让first 再次指向jackfirst = jack;//让first引用指向jack,就是双向链表的头结点System.out.println("===从头到尾进行遍历===");while (true) {if(first == null) {break;}//输出first 信息System.out.println(first);first = first.next;}last = hsp; //让last 重新指向最后一个结点//演示，从尾到头的遍历System.out.println("====从尾到头的遍历====");while (true) {if(last == null) {break;}//输出last 信息System.out.println(last);last = last.pre;}}
   }//定义一个Node 类，Node 对象 表示双向链表的一个结点
   class Node {public Object item; //真正存放数据public Node next; //指向后一个结点public Node pre; //指向前一个结点public Node(Object name) {this.item = name;}public String toString() {return "Node name=" + item;}
   }

   链表的演示

LinkedList底层原码

package com.jshedu.List_;import java.util.Iterator;
import java.util.LinkedList;/* @author 韩顺平* @version 1.0*/
@SuppressWarnings({"all"})
public class LinkedListCRUD {public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add(1);linkedList.add(2);linkedList.add(3);System.out.println("linkedList=" + linkedList);//演示一个删除结点的linkedList.remove(); // 这里默认删除的是第一个结点//linkedList.remove(2);System.out.println("linkedList=" + linkedList);//修改某个结点对象linkedList.set(1, 999);System.out.println("linkedList=" + linkedList);//得到某个结点对象//get(1) 是得到双向链表的第二个对象Object o = linkedList.get(1);System.out.println(o);//999//因为LinkedList 是 实现了List接口, 遍历方式System.out.println("===LinkeList遍历迭代器====");Iterator iterator = linkedList.iterator();while (iterator.hasNext()) {Object next =  iterator.next();System.out.println("next=" + next);}System.out.println("===LinkeList遍历增强for====");for (Object o1 : linkedList) {System.out.println("o1=" + o1);}System.out.println("===LinkeList遍历普通for====");for (int i = 0; i < linkedList.size(); i++) {System.out.println(linkedList.get(i));}//老韩源码阅读./* 1. LinkedList linkedList = new LinkedList();public LinkedList() {}2. 这时 linkeList 的属性 first = null  last = null3. 执行 添加public boolean add(E e) {linkLast(e);return true;}4.将新的结点，加入到双向链表的最后void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);//Node(prev,item,next)参数//把l赋给了prev，就是这个新结点通过prev指向前一个结点last = newNode;//这个原先last指向最后一个结点，增加一个结点，把后一个结点的地址赋给了lastif (l == null)first = newNode;elsel.next = newNode;//原先结点的next指向它后一个结点size++;modCount++;}*//*老韩读源码 linkedList.remove(); // 这里默认删除的是第一个结点1. 执行 removeFirstpublic E remove() {return removeFirst();}2. 执行public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}*/}
}

注意first是指向第一个元素，last指向最后一个元素，每个结点内部有三个属性，prev,next,item。不要弄混了，当只有一个元素时，first和last指向同一个结点

ArrayList和LinkedList的比较

1. 	底层结构	增删的效率	改查的效率
   ArrayList	可变数组	较低 数组扩容	较高
   LinkedList	双向链表	较高，通过链表追加	较低

2. 如何选择ArrayList和LinkedList

   1. 如果我们改查的操作多，选择ArrayList

   2. 如果增删的操作多，选择LinkedList

   3. 一般在程序中80%-90%都是查询，因此大部分情况选择ArrayList。

   4. 根据业务来进行选择用哪个