Java集合之List 心已赠人 2022-04-12 14:07 243阅读 0赞 # 1.核心成员 # * ArrayList 底层结构为数组,可以进行随机访问,能被克隆,能进行序列化传输,线程不安全,Vector就是它的线程安全版本,多个方法带有synchronized关键字,只是效率有点低。由于能进行随机访问,可快速查询,增删较为费劲。 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable * LinkedList 底层结构为链表,在进行增删操作较为方便,查询时需从头遍历全表。 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable * Vector淘汰货,效率低下 # 2.ArrayList # 1. 变量 elementData用来存储ArrayList的数据,transient修饰符表示被修饰时该属性不能被序列化,size来表示集合内元素的个数。 transient Object[] elementData; private int size; 1. 构造器 //带有指定大小的构造器 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } //默认无参数构造器,容量为0 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //参数为集合的构造器 public ArrayList(Collection<? extends E> c) { //将集合内的内容Copy一份到新数组内 elementData = c.toArray(); if ((size = elementData.length) != 0) { if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this.elementData = EMPTY_ELEMENTDATA; } } 这里我们看一下,若用无参数构造器进行构造会给一个容量为0的ArrayList集合,本来想着自编译jar用debug方式来看JDK源码成员变量的值,结果并没有成功,想要试试可以试试—》[eclipse调试JDK观察成员变量][eclipse_JDK] 既然上面方法没有用,那就用反射吧!!,用反射来获取数组容量的大小。 那看来如果初始数组的容量为0的话,那add()会将数组的容量从0变为10. public class test { public static void main(String[] args) throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException { ArrayList<Integer> list = new ArrayList<>(); getCapacity(list); list.add(1); getCapacity(list); } public static void getCapacity(ArrayList list) throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException { Class<ArrayList> lc = ArrayList.class; Field field = lc.getDeclaredField("elementData"); field.setAccessible(true); Object[] object = (Object[]) field.get(list); System.out.println(object.length); } } 1. 添加方法 //在数组的末尾插入数据 public boolean add(E e) { //这个方法的作用:1.如果容量为0,则将容量设为10. // 2.如果空间不够了,则会进行扩容。 ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { //DEFAULT_CAPACITY = 10 //如果为容量为0的数组,则将minCapacity为10 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { //modCount指的是这个数组被修改的次数 modCount++; if (minCapacity - elementData.length > 0) grow(minCapacity); } //扩容操作 private void grow(int minCapacity) { int oldCapacity = elementData.length; //新容量为旧容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); //容量为0时,新容量大小会为10 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 也就是2的32次方-1再-8 if (newCapacity - MAX_ARRAY_SIZE > 0) //如果最小容量超出Integer的最大值,则返回Integer的最大值,否则返回MAX_ARRAY_SIZE newCapacity = hugeCapacity(minCapacity); //将原有数据copy到新容量的数组内 elementData = Arrays.copyOf(elementData, newCapacity); } 1. 删除,修改,查询 * 删除方法 public E remove(int index) { // 下标边界检查 rangeCheck(index); //修改次数 modCount++; //取值 E oldValue = elementData(index); //移动数组 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; //返回删除的值 return oldValue; } * 修改方法 public E set(int index, E element) { //边界检查 rangeCheck(index); //取值 E oldValue = elementData(index); //设置新值 elementData[index] = element; return oldValue; } * 查询方法 没什么好说的!! public E get(int index) { rangeCheck(index); return elementData(index); } # 3.LinkedList # 1.成员变量 transient int size = 0; //指向第一个节点的指针 transient Node<E> first; //指向最后一个节点的指针 transient Node<E> last; * Node的构造 具有三个变量,保存的数据,指向下一个节点的指针,指向前一个。从这里看出,LinkedList是个双向链表,可以双向遍历。 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 1. 构造器 //构建一个空的链表 public LinkedList() { } //根据集合的迭代顺序copy到链表中去 public LinkedList(Collection<? extends E> c) { this(); addAll(c); } 1. 添加方法 //在链表前端添加数据 public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { //申明一个节点保存第一个节点 final Node<E> f = first; //申明一个新的节点 final Node<E> newNode = new Node<>(null, e, f); //头节点指向新节点 first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; //modCount指的是集合的修改次数 modCount++; } //同理 public void addLast(E e) { linkLast(e); } public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } //指定下标添加数据 public void add(int index, E element) { //下标检查 checkPositionIndex(index); //索引位置等于列表的大小,则在链表后面添加元素 if (index == size) linkLast(element); else linkBefore(element, node(index)); } //遍历链表获得指定下标的节点 Node<E> node(int index) { if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } //在当前节点前添加新节点 void linkBefore(E e, Node<E> succ) { final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } 1. 查询,删除,修改 * 查询 LinkedList有保存头结点和尾节点的节点指针,So直接拿就可以了 public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } * 删除 删除有三种:removeFirst(),removeLast(),remove(Object o)。 //移除头结点 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } //将首节点的值获取返回,并将下节点的前指针设为null //若下一个节点为空,则将last设为空 private E unlinkFirst(Node<E> f) { final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } //移除尾节点 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } //将最后一个节点的值取出返回,并将前一节点的next设为null //若前节点为null,则将first设置null' private E unlinkLast(Node<E> l) { final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; } //移除指定数值的节点,遍历数组并删除该数组所在的节点 public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //将指定节点的数值取出并返回,并新申明两个Node来表示该节点的next和pre节点 //将前节点的next指向后节点,将后节点的pre指向前节点 //如果前节点为null,则first设为后节点,如果后节点为null,则将last设为前节点 E unlink(Node<E> x) { final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; } * 修改 //遍历链表,修改数据 public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } [eclipse_JDK]: https://blog.csdn.net/u010407050/article/details/76690478
还没有评论,来说两句吧...