帝国怎么做网站,南开大学 网站开发技术 刘冲,h5编辑器有哪些软件,wordpress接入安卓目录
前言
ArrayList的缺陷
链表
链表的概念及结构
链表的种类
1.单向或双向
2.带头或不带头
3.循环或不循环
LinkedList的使用
什么是LinkedList
LinkedList的使用
LinkedList的构造
LinkedList的其他常用方法介绍
LinkedList的遍历
ArrayList和LinkedList的…目录
前言
ArrayList的缺陷
链表
链表的概念及结构
链表的种类
1.单向或双向
2.带头或不带头
3.循环或不循环
LinkedList的使用
什么是LinkedList
LinkedList的使用
LinkedList的构造
LinkedList的其他常用方法介绍
LinkedList的遍历
ArrayList和LinkedList的区别
链表的缺陷 前言
图文详解java链表顺序表和链表的比较多种链表的形式链表的使用链表的方法
ArrayList的缺陷
ArrayList顺序表
由于其底层是一段连续空间当在ArrayList任意位置插入或者删除元素时就需要将后序元素整体往前或者往后 搬移时间复杂度为O(n)效率比较低因此ArrayList不适合做任意位置插入和删除比较多的场景。因此java 集合中又引入了LinkedList即链表结构。
链表
链表的概念及结构
链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。 由上图可见链表不同于数组删除和添加元素只需要把next的值改变即可
这样时间复杂度只为O(1)
例如 注意: 1.从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续 2.现实中的结点一般都是从堆上申请出来的 3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续
链表的种类
1.单向或双向 2.带头或不带头 3.循环或不循环 虽然有这么多的链表的结构但是我们重点掌握两种:
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如 哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
无头双向链表在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
LinkedList的使用
什么是LinkedList
LinkedList的底层是双向链表结构(链表后面介绍)由于链表没有将元素存储在连续的空间中元素存储在单独的节 点中然后通过引用将节点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。
LinkedList的使用
LinkedList的构造 public static void main(String[] args) {// 构造一个空的LinkedListListInteger list1 new LinkedList();ListString list2 new java.util.ArrayList();list2.add(JavaSE);list2.add(JavaWeb);list2.add(JavaEE);// 使用ArrayList构造LinkedListListString list3 new LinkedList(list2);
}LinkedList的其他常用方法介绍 public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);list.remove(); // remove(): 删除第一个元素内部调用的是removeFirst()list.removeFirst(); // removeFirst(): 删除第一个元素list.removeLast(); // removeLast(): 删除最后元素list.remove(1); // remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在如果存在返回true否则返回falseif(!list.contains(1)){list.add(0, 1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置int elem list.get(0); // get(index): 获取指定位置元素list.set(0, 100); // set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回ListInteger copy list.subList(0, 3); System.out.println(list);System.out.println(copy);list.clear(); // 将list中元素清空System.out.println(list.size());
}LinkedList的遍历
public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());// foreach遍历for (int e:list) {System.out.print(e );}System.out.println();// 使用迭代器遍历---正向遍历ListIteratorInteger it list.listIterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();// 使用反向迭代器---反向遍历ListIteratorInteger rit list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() );}System.out.println();
}
ArrayList和LinkedList的区别 链表的缺陷
我们知道链表的删除和添加效率比顺序表高得多但是没有取代顺序表这是因为链表也有缺陷
如上图链表对于访问来说非常的乏力顺序表底层是数组可以直接用下标来访问时间复杂度为O(1)而链表则需要从头开始访问一个个计数然后访问到需要的元素时间复杂度为O(n)
所以顺序表和链表都有其存在的意义我们要视情况而选择合适的来使用
