网站开发有很多种吗,宁波网站建设团队排名,网页传奇游戏黑屏怎么解决,软件技术专业难学吗说一下单列集合#xff0c;java中的单列集合的顶级接口是Collection#xff0c;它有两个子接口#xff1a;List、Set#xff0c;本篇介绍一下List接口及其实现类的功能方法和基本实现原理。 List集合是有序集合#xff0c;这里的有序并不是指存入List集合的元素会被自动排… 说一下单列集合java中的单列集合的顶级接口是Collection它有两个子接口List、Set本篇介绍一下List接口及其实现类的功能方法和基本实现原理。 List集合是有序集合这里的有序并不是指存入List集合的元素会被自动排序而是指数据存储和数据读取的顺序是一样的就是说按着123的顺序依次添加元素后遍历集合时元素也会按着123的顺序进行打印。List集合不会对添加的元素进行排序并且允许存储相同的元素。实现List接口的实现类有ArrayList、LinkedList、Vector、Stack等接下来详细的介绍一下一般常用的几个List集合。 先说一下ArrayListArrayList集合的底层数据结构是数组其实ArrayList就是依靠数组进行存储数据但是这个数组可以进行扩容操作所以才显得List集合的容量大小可变正因为依赖数组所以ArrayList集合具有查询快、增删慢的特点另外ArrayList的底层实现并未用到同步机制所以是线程不安全的集合效率高。 ArrayList集合中的功能方法在这里就不做介绍了按着API测试即可挺简单的。这里说一下它的底层实现底层代码及分析如下
//实现了RandomAccess接口说明可以快速随机访问
//实现了Cloneable接口说明可以被克隆
//实现了Serializable接口说明可以被序列化
public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.Serializable
{
/**********************************************成员变量****************************************************************///capacity 默认容量private static final int DEFAULT_CAPACITY 10;//这个就是ArrayList底层维护的那个数组用于存储数据用//elementData 不参与序列化因为他本质上只是一个地址而并不是数据transient Object[] elementData;//就是声明一个空数组当实例化一个容量大小为0的ArrayList时就用EMPTY_ELEMENTDATA实例化elementDataprivate static final Object[] EMPTY_ELEMENTDATA {};//当使用空构造方法创建一个集合实例时elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATAprivate static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};//记录集合的大小private int size;//集合容量的最大值private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;/**********************************************构造方法****************************************************************///实例化一个容量为initialCapacity的集合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);}}//实例化一个空的集合public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}//根据一个集合来实例化一个集合顺序不变public ArrayList(Collection? extends E c) {elementData c.toArray();if ((size elementData.length) ! 0) {if (elementData.getClass() ! Object[].class)//类型不是Object[].class则复制一个elementData Arrays.copyOf(elementData, size, Object[].class);} else {this.elementData EMPTY_ELEMENTDATA;}}//类似于字符串的trim操作就是将当前集合的容量缩减为这个集合实际含有有效元素的长度大小//正因为这个方法才使得集合的大小就是元素的个数public void trimToSize() {//modCount 是AbstractList中的属性表示集合在结构上修改的次数。就是集合大小修改的次数//主要作用在于迭代集合元素时判断是否发生并发修改异常modCount;if (size elementData.length) {elementData (size 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}/**********************************************添加元素****************************************************************///在集合的尾部添加一个元素public boolean add(E e) {//扩容ensureCapacityInternal(size 1);elementData[size] e;//在尾部添加元素并将集合的大小加一return true;}//容量检查private void ensureCapacityInternal(int minCapacity) {//如果是刚进来初始化的话就将数组的长度设置成默认长度10if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity Math.max(DEFAULT_CAPACITY, minCapacity);}//如果集合容量已经比10大了则检查是否需要扩容ensureExplicitCapacity(minCapacity);}//容量检查private void ensureExplicitCapacity(int minCapacity) {modCount;// 如果 底层数组的长度要填加元素到数组的下标 则进行扩容if (minCapacity - elementData.length 0)//进行具体的扩容操作grow(minCapacity);}//扩容机制private void grow(int minCapacity) {// overflow-conscious code//先获取到当前数组的长度int oldCapacity elementData.length;//新数组的长度 原来数组的长度 原来数组长度的一半 也就是传说中的扩容1.5倍int newCapacity oldCapacity (oldCapacity 1);//如果扩容1.5倍后还是不足以添加新的元素则将新数组的容量设置成将要添加的数组下标if (newCapacity - minCapacity 0)newCapacity minCapacity;//判断一下新的数组大小是否比集合的最大容量要大 if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);// 创建一个新数组长度大小为newCapacity 然后将原来的数组中的元素复制到新数组中// 在外界看来就像是数组扩容了其实就是新创建了一个长度更大的数组而已elementData Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity 0) // overflowthrow new OutOfMemoryError();return (minCapacity MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}/**********************************************删除元素****************************************************************///删除下标index处的元素public E remove(int index) {rangeCheck(index);//下标合法性检查modCount;//获取都指定下标处的元素用于返回E oldValue elementData(index);int numMoved size - index - 1;if (numMoved 0)//调用c或c的方法将删除元素后的所有元素往前移一位System.arraycopy(elementData, index1, elementData, index, numMoved);elementData[--size] null;return oldValue;}//如果删除的元素下标集合容量报错private void rangeCheck(int index) {if (index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/**********************************获取指定元素在集合中第一次出现的下标*****************************************************/ public int indexOf(Object o) {if (o null) {for (int i 0; i size; i)if (elementData[i]null)return i;} else {//就是循环遍历底层数组只要碰到相同指定元素值的元素直接返回下标结束程序for (int i 0; i size; i)if (o.equals(elementData[i]))return i;}return -1;}/**********************************获取指定下标处的元素*****************************************************/ public E get(int index) {rangeCheck(index);//下标合法性校验//返回元素return elementData(index);}/**********************************序列化和反序列化*****************************************************/ //序列化private void writeObject(ObjectOutputStream s) throws java.io.IOException{int expectedModCount modCount;s.defaultWriteObject();s.writeInt(size);//将数组的每一个元素进行写入for (int i0; isize; i) {s.writeObject(elementData[i]);}}//反序列化private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {elementData EMPTY_ELEMENTDATA;s.defaultReadObject();s.readInt();if (size 0) {ensureCapacityInternal(size);Object[] a elementData;for (int i0; isize; i) {a[i] s.readObject();}}}/**********************************迭代集合*****************************************************/ public IteratorE iterator() {return new Itr();}//使用内部类实现Iterator接口的方式实现迭代器private class Itr implements IteratorE {// 下一个元素的下标int cursor;int lastRet -1;int expectedModCount modCount;//集合修改次数//是否还有下一个元素public boolean hasNext() {return cursor ! size;}//获取下一个节点元素public E next() {checkForComodification();int i cursor;if (i size)throw new NoSuchElementException();Object[] elementData ArrayList.this.elementData;if (i elementData.length)throw new ConcurrentModificationException();cursor i 1;return (E) elementData[lastRet i];}//判断是否发生并发修改异常使用迭代器遍历集合时不能修改集合然可以使用迭代器修改集合final void checkForComodification() {if (modCount ! expectedModCount)throw new ConcurrentModificationException();}}
} 再说一下另一个常用的集合LinkedList它的底层数据结构是链表依赖一个双向链表存储数据具有增删快、查询慢的特点代码分析如下
//双向链表
//实现了Deque接口说明具有双向队列的特性
//实现了Cloneable接口说明可以被克隆
//实现了Serializable接口说明可以被序列化
public class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, java.io.Serializable
{//用一个静态内部来声明节点private static class NodeE {E item;NodeE next;NodeE prev;Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}}//集合大小transient int size 0;//头结点transient NodeE first;//尾节点transient NodeE last;//构造一个集合public LinkedList() {}//根据已有集合构建一个LinkedList集合public LinkedList(Collection? extends E c) {this();addAll(c);}/**********************************************添加元素****************************************************************/ //直接用addAll(c)这个方法为例看public boolean addAll(Collection? extends E c) {return addAll(size, c);}//相当于添加多个结点public boolean addAll(int index, Collection? extends E c) {//index size//检查传入的集合大小是否合理checkPositionIndex(index);Object[] a c.toArray();//集合转成数组int numNew a.length;//获取数组长度if (numNew 0)//如果长度是0没有元素直接返回return false;//声明两个结点前驱结点pred 、 后继结点succNodeE pred, succ;if (index size) {//这里trueindex表示在哪里开始添加如果添加下标和链表大小相同则就是在末尾添加succ null;//后继节点为空pred last;//前驱节点指向链表中的最后一个结点} else {succ node(index);//获取到index位置的结点succ指向此节点也就是新建结点的后继结点指向index位置的结点pred succ.prev;//新建结点的前驱结点指向index位置结点的原来的前一个结点结点}for (Object o : a) {SuppressWarnings(unchecked) E e (E) o;NodeE newNode new Node(pred, e, null);//利用上面的前驱和后继结点创建一个结点添加到链表if (pred null)//前驱结点是null链表中没结点first newNode;//则初始化头节点elsepred.next newNode;//让pred的后继结点指向新添加的节点也就是index位置原先的前一个结点的后继结点指向新节点大白话就是在index位置和index-1位置直接新添加一个结点pred newNode;//然后让pred节点指向新添加的节点}if (succ null) {//如果后继结点是空初始化尾节点last pred;} else {pred.next succ;//pred的下一个节点指向succsucc.prev pred;//succ的上一个节点指向pred}size numNew;//链表中元素个数modCount;//链表改变标记1return true;}} /**********************************************获取元素****************************************************************/ //获取到index处的结点 public E get(int index) {checkElementIndex(index);return node(index).item;}//获取元素时需要挨个遍历所以查询效率低。 NodeE node(int index) {if (index (size 1)) {//如果结点所在的位置在链表的前半段则从前往后遍历//一直将指针指到index处获取到结点NodeE x first;for (int i 0; i index; i)x x.next;return x;} else {//结点所在的位置在链表的后半段则从后往前遍历NodeE x last;for (int i size - 1; i index; i--)x x.prev;return x;}}/**********************************************删除元素****************************************************************/ //确定删除元素的结点public E remove(int index) {checkElementIndex(index);return unlink(node(index));}//根据结点中的前驱结点和后继结点删除链表删除结点操作E unlink(NodeE x) {// assert x ! null;final E element x.item;final NodeE next x.next;final NodeE 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 int indexOf(Object o) {int index 0;if (o null) {for (NodeE x first; x ! null; x x.next) {if (x.item null)return index;index;}} else {for (NodeE x first; x ! null; x x.next) {if (o.equals(x.item))return index;index;}}return -1;}}再说一下这两个集合的遍历方式代码如下
1for循环ArrayListString list new ArrayList();list.add(1111);list.add(2222);list.add(3333);for (int i 0; i list.size(); i) {System.out.println(list.get(i));}
2迭代器ArrayListString list new ArrayList();list.add(1111);list.add(2222);list.add(3333);IteratorString iterator list.iterator();while(iterator.hasNext()) {System.out.println(iterator.next());}
3增强forArrayListString list new ArrayList();list.add(1111);list.add(2222);list.add(3333);for (String string : list) {System.out.println(string);}---------------------------------------------------------------------------1for循环LinkedListString list new LinkedList();list.add(1111);list.add(2222);list.add(3333);for (int i 0; i list.size(); i) {System.out.println(list.get(i));}2迭代器LinkedListString list new LinkedList();list.add(1111);list.add(2222);list.add(3333);IteratorString iterator list.iterator();while(iterator.hasNext()) {System.out.println(iterator.next());}3增强forLinkedListString list new LinkedList();list.add(1111);list.add(2222);list.add(3333);for (String string : list) {System.out.println(string);}
就先说一下这两个其实List集合底层封装的都是数组或者链表对数据结构有点了解的话很容易就理解了。
