List 集合(实现类有ArrayList和LinkedList)它是单身住宿的,一次存储一个对象。它拥有 Collection 规定的所有方法的实现;同时它可以拥有自身独特的规定的方法。List集合的特点: 1.有索引:List 集合是有索引的 2.有序性:List 集合是有序的保证了装入集合时的顺序 3.重复性:List 集合允许存储重复的元素List 集合的三个典型实现: 1、List list1 = new ArrayList(); 底层数据结构是数组,查询快,增删慢;线程不安全,效率高。 2、List list3 = new LinkedList(); 底层数据结构是链表,查询慢,增删快;线程不安全,效率高。 3、List list2 = new Vector(); 底层数据结构是数组,查询快,增删慢;线程安全,效率低,这个集合几乎被淘汰。List 常用方法学习public class TestList { public static void main(String[] args) { List list = new ArrayList(); Collection list2 = new ArrayList(); //增加元素 list.add("1"); list.add("2"); list.add("3"); list.add("5"); list.add("4"); list.add("5"); //增加元素 list.remove("1"); //改变元素 list.set(4,"被修改了"); System.out.println(list);
//构造 List 的迭代器 Iterator it = list.iterator(); //通过迭代器遍历元素 while(it.hasNext()){ Object obj = it.next(); System.out.println(obj); }
// List 独有的 遍历方式 for(int i = 0 ; i < list.size() ; i++){ System.out.println(list.get(i)); }
/** List<E> subList(int fromIndex, int toIndex) 获取一个子集合 参数1 是开始截取的索引 参数2 是结束截取的索引 包含参数1 不包含参数2*/ List li = list.subList(2, list.size()); System.out.println(li); } }
int indexOf(Object o) 查看 o 第一次出现的索引位置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; }
int lastIndexOf(Object o ) 查看o 最后一次出现的索引位置public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }
ArrayList--底层是数组观察所有的构造器 发现都是在为 ElementData 赋值 由此得出 ElementData 就是底层实现,ElementData 本身是 Object[] ElementData。增加元素 每增加一个元素,就会判断数组是否需要扩容,拿现在size + 1 去判断,如果需要扩容,那就扩容1.5倍。 int newCapacity = oldCapacity + (oldCapacity >> 1);然后 elementData[size++] = 要添加的元素public boolean add(Object obj){ ensureCapacityInternal(size+1)//扩容 elementData[size++] = obj; return ture; }
删减元素 每移除一个元素,会先确定元素的位置,确定元素的值,然后把 要删除的位置之前的,之后的copy到新数组,新数组替换 elementData ,然后把最后一位size赋值为null size也要 --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; }
LinkedList--底层是链表LinkedList 存储的是什么 Node 对象:Node对象有 三个属性 item:要存储的对象 next:下一个元素对象 (last 的next 一般为 null) prev:上一个元素对象 (first 的prev 一般为 null)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++; } 首先增加到 last,先记录住当前 last 的对象,然后根据当前的 last(prev) 对象和要添加的元素(item) 和 null(next) 创建一个 newNode ,last 重新赋值 赋值为 newNode,添加元素之前的 last , 已经被记录了 ,并且参与了构建新对象 然后再把它的 next 指向新对象,然后 size++。E unlink(Node<E> x) { // assert x != null; 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; } 1. 根据索引找出要移除的对象 2. 记录 要移除的对象的 上一个指向(prev) 存储的值(value) 下一个指向(next) 3. prev 代表的对象 next 属性不再指向被移除的对象 改为指向 next代表的对象 4. next 代表的对象 它的 prev 属性不要指向被移除的对象 改为指向 prve代表的对象 同时要考虑 被移除对象可能是 first 或 last , 处理方式会有所不同LinkedList 的遍历 要得到第一个 Node对象,然后不停的寻找下一个对象即 next 属性,然后一直寻找到最后的,中间地址跳转频繁 :
|