廊坊网站群发关键词,4399小游戏在线玩网页版,线下推广app赚佣金,企业代码查询入口数据结构之常见的8种数据结构#xff1a;
-数组Array
-链表 Linked List
-堆 heap
-栈 stack
-队列 Queue
-树 Tree
-散列表 Hash
-图 Graph 数据结构-链表篇 Linklist定义#xff1a; -是一种线性表#xff0c;并不会按线性的顺序存储数据#xff0c;即逻辑上相邻…数据结构之常见的8种数据结构
-数组Array
-链表 Linked List
-堆 heap
-栈 stack
-队列 Queue
-树 Tree
-散列表 Hash
-图 Graph 数据结构-链表篇 Linklist定义 -是一种线性表并不会按线性的顺序存储数据即逻辑上相邻物理上不一定相邻的元素。通过指针域来寻找对应的元素。
Linklist优缺点
优点 -插入、删除速度快
-灵活分配结点空间
缺点 -查询速度慢
通过Linklist常用方法来深入底层原理 -addE e -addint index, E element -remove(Obeject o) -remove(int index) -ListIterator正向遍历 -反向遍历 总结 -插入、删除速度快是因为只要通过前后指针就能插入或者删除到链表中不需要移动其它元素插入头尾节点更快因为Node结构体中保存了头尾指针。
-查询速度慢是因为查询先通过右位移运算来判断对链表是前半部分遍历还是后半部分遍历剩下的半部分遍历则是一个个节点遍历头尾查询快因为保存了头尾指针。
数据结构--数组篇
数组的定义 -申请一块连续的内存空间来存储相同类型数据的集合
-数组存储的是对象的引用而非是对象本身
数组的优缺点 优点查询速度快O1复杂度因为它的存储是连续的内存空间查找元素首地址 每个元素所分配的空间*下标
从cpu的读取cpu在读取数组的时候可以借助缓存机制预读数组的数据cpu在读取内存的时候会把一块连续的内存空间读入当进行遍历时直接命中。而链表是跳跃式的地址在缓存中命中的概率低就要跑到内存中去读取数据缓存的速度远大于内存的读取速度。
缺点插入 、删除速度慢因为需要移动该元素后面的所有元素位置
数组的使用场景 -适合查询多插入、删除少的场景整体上来说
通过数组方法来深入底层原理 ArrayList方法中的常用方法 -addE e方法 流程图 removeint index方法 removeObject o方法 remove注意removeObject o方法使用了2个对null跟非null分别使用了跟equals做了等值比较找到元素对应的索引位置后再删除与removeint index方法步骤基本一样
Iterator遍历方法 迭代注意迭代过程中有2次的ConcurrentModification检验一次是2个记录修改次参数expectedModCount modCount等值校验。二次是 i elementData.length并发过程中多次调用next方法。
Iterator的remove方法 关于System.arraycopy,Array.copyof区别 -System.arraycopyObject src, int srcPos, Object dest, int destPos,int length
有5个参数
src 原数组
srcPos原数组开始元素拷贝的索引位置
dest目标数组
destPos在目标数组的索引位置开始拷贝
length拷贝的数组长度
-Arraycopyof 底层调用的也是Native方法的System.arraycopy 面试点提问几种删除方式有什么区别 重点关注expectedModCount modCount;ConcurrentModificationException
for循环删除跟Iterator删除方式有什么不同 Iterator方法 正序for循环则直接调用remove(Object)或者remove(index)方法修改了modCount的值但是并没有走checkForComodification()检验该方法只针对了实现了IteratorE的类想要正确删除元素请使用倒序删除
以上2个方法都可以直接删除元素不会报错正序for循环不保证结果正确性
可以用foreach加强循环删除么 a,foreach底层的实现原理就是通过Iterator迭代来实现的。所以会存在修改次数跟预期值修改值的比较判断。
b,而foreach循环在删除元素的时候走的是fastRemove方法 c,只增加了modCount d,并没有expectedModCount modCount赋值语句在下一次的循环就会报错 综上所述使用Iterator跟for循环是可以成功删除元素的foreach循环则不行。checkForComodification()检验该方法只针对了实现了IteratorE的类而Iterator跟foreach底层实现都是依赖这个接口。for循环则不依赖
注意上面的Demo只是说删除元素时会不会报错并不是说上面几种方式都能正确删除完全使用for循环保证正取删除元素可以使用倒序的方式或者使用Iterator方式推荐。
