一 ArrayList
1. arraylist里面是通过数组实现的
- /**
- * The array buffer into which the elements of the ArrayList are stored.
- * The capacity of the ArrayList is the length of this array buffer.
- */
- private transient Object[] elementData;
- /**
- * The size of the ArrayList (the number of elements it contains).
- *
- * @serial
- */
- private int size;
2. arraylist初始化的时候可以指定大小,如果你知道大小,在创建的时候最好指定
- public ArrayList(int initialCapacity) {
- super();
- if (initialCapacity < 0)
- throw new IllegalArgumentException("Illegal Capacity: "+
- initialCapacity);
- this.elementData = new Object[initialCapacity];
- }
3. arraylist添加元素的时候,需要判断存放元素的数组是否需要扩容(扩容大小是原来大小的1/2+1)
- public boolean add(E e) {
- ensureCapacity(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
- public void ensureCapacity(int minCapacity) {
- modCount++;
- int oldCapacity = elementData.length;
- if (minCapacity > oldCapacity) {
- Object oldData[] = elementData;
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity)
- newCapacity = minCapacity;
- // minCapacity is usually close to size, so this is a win:
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
- }
4. arraylist 在指定位置添加元素或者移除指定位置元素,需要移动比较多的数据
- public void add(int index, E element) {
- if (index > size || index < 0)
- throw new IndexOutOfBoundsException(
- "Index: "+index+", Size: "+size);
- ensureCapacity(size+1); // Increments modCount!!
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- elementData[index] = element;
- size++;
- }
- public E remove(int index) {
- RangeCheck(index);
- modCount++;
- E oldValue = (E) elementData[index];
- int numMoved = size - index - 1;
- if (numMoved > 0)
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- elementData[--size] = null; // Let gc do its work
- return oldValue;
- }
二. LinkedList
1. linkedlist是通过链表实现的,一个节点是一个对象,包含了自己前一个节点的和后一个节点的地址
- private transient Entry<E> header = new Entry<E>(null, null, null);
- private transient int size = 0;
- private static class Entry<E> {
- E element;
- Entry<E> next;
- Entry<E> previous;
- Entry(E element, Entry<E> next, Entry<E> previous) {
- this.element = element;
- this.next = next;
- this.previous = previous;
- }
- }
2. 添加元素是通过移动链表指针
- public boolean add(E e) {
- addBefore(e, header);
- return true;
- }
- private Entry<E> addBefore(E e, Entry<E> entry) {
- Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
- newEntry.previous.next = newEntry;
- newEntry.next.previous = newEntry;
- size++;
- modCount++;
- return newEntry;
- }
3. 删除元素也是通过移动指针,所以理论上linkedlist比arraylist更适合添加和删除操作(不需要判断是否需要扩容,不需要移动大批的元素)
- public boolean remove(Object o) {
- if (o==null) {
- for (Entry<E> e = header.next; e != header; e = e.next) {
- if (e.element==null) {
- remove(e);
- return true;
- }
- }
- } else {
- for (Entry<E> e = header.next; e != header; e = e.next) {
- if (o.equals(e.element)) {
- remove(e);
- return true;
- }
- }
- }
- return false;
- }
- private E remove(Entry<E> e) {
- if (e == header)
- throw new NoSuchElementException();
- E result = e.element;
- e.previous.next = e.next;
- e.next.previous = e.previous;
- e.next = e.previous = null;
- e.element = null;
- size--;
- modCount++;
- return result;
- }
4. 获取元素需要遍历链表,比arraylist要慢
- public E get(int index) {
- return entry(index).element;
- }
- private Entry<E> entry(int index) {
- if (index < 0 || index >= size)
- throw new IndexOutOfBoundsException("Index: "+index+
- ", Size: "+size);
- Entry<E> e = header;
- if (index < (size >> 1)) {//size 右移一位表示除以2,其实就是看从前遍历快还是从后遍历快
- for (int i = 0; i <= index; i++)
- e = e.next;
- } else {
- for (int i = size; i > index; i--)
- e = e.previous;
- }
- return e;
- }
5. linkedlist 迭代器,支持向前向后迭代,在迭代过程中移除元素。如果要遍历linkedlist,建议使用迭代器,因为如果使用get方法效率没迭代器高。(从get方法的源码可以看出)
- private class ListItr implements ListIterator<E> {
- private Entry<E> lastReturned = header;
- private Entry<E> next;
- private int nextIndex;
- private int expectedModCount = modCount;
- ListItr(int index) { //支持从指定位置开始迭代
- if (index < 0 || index > size)
- throw new IndexOutOfBoundsException("Index: "+index+
- ", Size: "+size);
- if (index < (size >> 1)) {
- next = header.next;
- for (nextIndex=0; nextIndex<index; nextIndex++)
- next = next.next;
- } else {
- next = header;
- for (nextIndex=size; nextIndex>index; nextIndex--)
- next = next.previous;
- }
- }
- public boolean hasNext() {//是否有下一个
- return nextIndex != size;
- }
- public E next() { //下一个
- checkForComodification();
- if (nextIndex == size)
- throw new NoSuchElementException();
- lastReturned = next;
- next = next.next;
- nextIndex++;
- return lastReturned.element;
- }
- public boolean hasPrevious() { //是否有前一个
- return nextIndex != 0;
- }
- public E previous() { //前一个
- if (nextIndex == 0)
- throw new NoSuchElementException();
- lastReturned = next = next.previous;
- nextIndex--;
- checkForComodification();
- return lastReturned.element;
- }
- public int nextIndex() {
- return nextIndex;
- }
- public int previousIndex() {
- return nextIndex-1;
- }
- public void remove() { //删除元素
- checkForComodification();
- Entry<E> lastNext = lastReturned.next;
- try {
- LinkedList.this.remove(lastReturned);
- } catch (NoSuchElementException e) {
- throw new IllegalStateException();
- }
- if (next==lastReturned)
- next = lastNext;
- else
- nextIndex--;
- lastReturned = header;
- expectedModCount++;
- }
- public void set(E e) {
- if (lastReturned == header)
- throw new IllegalStateException();
- checkForComodification();
- lastReturned.element = e;
- }
- public void add(E e) {
- checkForComodification();
- lastReturned = header;
- addBefore(e, next);
- nextIndex++;
- expectedModCount++;
- }
- final void checkForComodification() {
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- }
- }
相关推荐
今天介绍一下Java的两个集合类,ArrayList和LinkedList,这两个集合的知识点几乎可以说面试必问的。感兴趣的朋友跟随小编一起看看吧
本文将对Java常见面试题进行总结和解析,旨在为准备面试的Java开发者提供全面而深入的学习参考。...建议读者结合实际代码示例和项目经验,深入理解和掌握这些知识点,并不断练习和总结,以提高自己的面试成
就是一些通用java集合知识点整理,ArrayList LinkedList,HashMap,HashTable ,ConcurrentHashMap,HashSet,LinkedHashSet类通过线程安全否: 底层: 初始值: 扩容 : 区别(对比优势) 图解
java面试笔试资料包括JAVA基础核心知识点深度学习Spring面试题等资料合集: JAVA核心知识点整理-282页 Java与哈希算法.docx Java中Lambda表达式的使用.docx JAVA多线程之线程间的通信方式.docx Java注解详解.docx ...
Java面试题10.ArrayList 和LinkedList的区别 Java面试题11.HashMap和HashTable的区别 Java面试题12.实现一个拷贝文件的工具类要使用字节流还是字符串 Java面试题13.线程的的实现方式?怎么启动线程?怎么区分线程? ...
哈希值 LinkedHashSet TreeSet 自然排序Comparable 比较器排序Comparator Set集合 并发修改异常 LinkedList集合 ArrayList集合 List集合 Collection集合概述 冒泡排序 Object 异常 Math 包装类 Calendar类 ...
开篇词讲怎样才能做好性能调优02讲如何制定性能调优策略04讲...索引的失效与优化36讲什么时候需要分表分库37讲电商系统表设计优化案例分析39讲答疑课堂:MySQL中InnoDB的知识点串讲加餐讲推荐几款常用的性能测试工具
Java后端面试知识点总结,涉及JVM • 熟悉JVM内存区域,常用引用类型,垃圾回收机制、算法以及常见的GC垃圾收集器(Serial、ParNew、Parallel Scavenge、Serial Old、Parallel Old、CMS、G1) • 熟悉常用IO模型(BIO、...
本课程从零开始,以通俗易懂的方式讲解Java技术,手把手教你掌握每一个知识点。 真正做到零基础入门学习,适合初学者的教程! 课程内容包括: 1.集合简介 2.存储结构 3.集合相关API 4.List:ArrayList、...
【基础】Java序列化与反序列化 27 为什么需要序列化与反序列化 28 如何实现Java序列化与反序列化 28 【基础】String s = new String("xyz");创建了几个字符串对象 30 【基础】接口是否可继承(extends)接口?抽象类...
目录1. 集合的概念2.... 集合的遍历5.1 迭代器5.2 增强for循环(jdk1.5+)* 附加知识点1.数据结构1.1 栈1.2 队列1.3 数组1.4 链表1.5 树1.5.1 二叉树1.5.2 红黑树2. 关于泛型2.1 概念2.2 定义和使用2.3 泛
学习ArrayList与LinkedList类,理解封装数组和链表两种方式定义集合类。 可以使用迭代器Iterator遍历集合的元素。 [*]理解泛型概念,声明和使用带有范型的集合。 第11章 集合 4...
Java 知识点,继续完善中。 多数是一些 Java 基础知识、底层原理、算法详解。也有上层应用设计,其中不乏一些大厂面试真题。 如果对你有帮助请点下 Star,有疑问欢迎提 ,有好的想法请提 。 常用集合 ArrayList/...
java知识点 Hashmap 源码级掌握,扩容,红⿊树,最⼩树化容量,hash冲突解决,有些⾯试官会提出发⾃灵魂的审问,⽐如为什么是红⿊树, 别的树不可以吗;为什么8的时候树化,4不可以吗,等等 concureentHashMap,段锁...
1、说说Glide中的with方法2、什么是线程安全?保障线程安全有哪些手段?3、说说TCP的三次挥手、四次挥手4、谈谈垃圾回收...16、ArrayList和LinkedList有何区别?17、Java的四种引用及应用场景?18、 String, StringB
2. Java基础知识点 2.1 Java泛型 2.2 Java反射 2.3 Java注解 2.4 Java类加载机制 2.5 Java异常分类 2.6 Java的内存模型 二,Java多线程并发 1.线程的基本知识 1.1并发知识 1.2 Java线程创建的姿势 1.3 Java线程终止...
以下是总结java面试中常见的知识点以及碰到的坑等,经历有限,需待练级! 一、java基础 实例方法和静态方法有什么不一样? Java中的异常有哪几类?分别怎么使用? 常用的集合类有哪些?比如List如何排序? ArrayList...
7.4.2 ArrayList和Vector实现类 264 7.4.3 固定长度的List 266 7.5 Queue接口 266 7.5.1 LinkedList实现类 266 7.5.2 PriorityQueue实现类 269 7.6 Map 270 7.6.1 HashMap和Hashtable实现类 271 7.6.2 ...
100%的面试都会问collection接口和map接口下面的知识,要在源码层次掌握,例如ArrayList与LinkedList自动增长的实现有何区别(驴妈妈问到过)参考链接: java.lang包!60%概率考察到!基本的数据类
remove方法对LinkedList类的使用3.3.5 关于ListIterator接口3.4 ArrayList类的实现3.4.1 基本类3.4.2 迭代器、Java嵌套类和内部类3.5 LinkedList类的实现3.6 栈ADT3.6.1 栈模型3.6.2 栈的实现3.6.3 应用3.7 队列...