app展示网站模板html5,网页游戏排行版,淘宝客网站可以备案吗,中超联赛山东泰山直播目录
一#xff0c;双向链表
1.单向链表的缺点
2.什么是双向链表#xff1f;
3.自主实现双向链表
接口实现#xff1a;
二#xff0c;LinkedList
1.LinkedList的使用
1.1 什么是LinkedList#xff1f;
1.2 LinkedList的使用
1.LinkedList的构造
2.LinkedList的…目录
一双向链表
1.单向链表的缺点
2.什么是双向链表
3.自主实现双向链表
接口实现
二LinkedList
1.LinkedList的使用
1.1 什么是LinkedList
1.2 LinkedList的使用
1.LinkedList的构造
2.LinkedList的其它常用方法介绍
3.LinkedList的遍历
三ArrayList与LinkedList的区别 一双向链表
1.单向链表的缺点
再了解单向链表的实现以及使用过后我们发现单项链表存在存在缺点
1.如下图当cur访问下一个节点时无法再访问到上一个节点
2.尾插法的时间复杂度为O(N)
为应对该类问题于是就有了双向链表
2.什么是双向链表
定义双向链表由一系列的节点组成每个节点包含两个指针分别指向前一个节点和后一个节点。与单向链表不同双向链表可以从任意节点开始向前或向后遍历链表。
如下图所示 这是一个无头双向链表从中我们不难看出它与无头单向链表的区别
1.不仅有头节点通过next进行顺序访问还有尾节点通过prev进行逆序访问
2.额外有一个prev域访问上一个已访问过的节点
3.自主实现双向链表
接口实现
接口部分
public interface IList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index, int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();//打印单链表public void display();//清空单链表public void clear();}
接口重写部分
public class MyList implements IList{static class ListNode {public int val;//值public ListNode prev;//访问上一个域public ListNode next;//访问下一个域public ListNode(int val) {this.val val;}}public ListNode head;//头节点public ListNode last;//尾节点//头插法Overridepublic void addFirst(int data) {ListNode node new ListNode(data);if (this.head null) {this.head node;this.last node;} else {node.next this.head;this.head.prev node;this.head node;}}//尾插法Overridepublic void addLast(int data) {ListNode node new ListNode(data);if (this.head null) {this.head node;this.last node;} else {this.last.next node;node.prev this.last;this.last node;}}//任意位置插入,第一个数据节点为0号下标Overridepublic void addIndex(int index, int data) {ListNode node new ListNode(data);ListNode cur this.head;if (index 0 index size()) {if (index 0) {addFirst(data);return;}if (index size()) {addLast(data);return;}int count 1;while (cur ! null) {ListNode curNext cur.next;if (count index) {node.next curNext;curNext.prev node;cur.next node;node.prev cur;}count;cur cur.next;}} else {throw new IndexException(添加下标异常);}}//查找是否包含关键字key是否在单链表当中Overridepublic boolean contains(int key) {ListNode cur this.head;while (cur ! null) {if (cur.val key) {return true;}cur cur.next;}return false;}//删除第一次出现关键字为key的节点Overridepublic void remove(int key) {ListNode cur this.head;while (cur ! null) {ListNode curNext cur.next;if (cur.val key) {//删头节点if (cur.prev null) {//this.head.val null;this.head head.next;head.prev null;return;}//删尾节点if (cur.next null) {//this.last.val null;this.last last.prev;last.next null;return;}curNext.prev cur.prev;cur.prev.next curNext;return;}cur cur.next;}}Overridepublic void removeAllKey(int key) {ListNode cur this.head;while (cur ! null) {ListNode curNext cur.next;if (cur.val key) {//删头节点if (cur.prev null) {//this.head.val null;this.head head.next;head.prev null;} else if (cur.next null) {//this.last.val null;this.last last.prev;last.next null;} else {curNext.prev cur.prev;cur.prev.next curNext;}}cur cur.next;}}//得到单链表的长度Overridepublic int size() {ListNode cur this.head;int count 0;while (cur ! null) {count;cur cur.next;}return count;}//打印单链表Overridepublic void display() {ListNode cur this.head;if (head null) {System.out.println([ ]);} else {System.out.print([);while (cur ! null) {if (cur last) {System.out.print(cur.val);} else {System.out.print(cur.val );}cur cur.next;}System.out.println(]);}}//清空单链表Overridepublic void clear() {ListNode cur this.head;while (cur.next ! null) {ListNode curNext cur.next;//cur.val null;cur.prev null;cur.next null;}this.head null;this.last null;}
}
二LinkedList
LinkedList是一个双向链表以上双向链表便是模拟LinkedList
1.LinkedList的使用
1.1 什么是LinkedList
LinkedList的官方文档 LinkedList的底层是双向链表结构由于链表没有将元素存储在连续的空间中元素存储在单独的节点中然后通过引用将节点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。 在集合框架中LinkedList也实现了List接口 【说明】 1. LinkedList实现了List接口 2. LinkedList的底层使用了双向链表 3. LinkedList没有实现RandomAccess接口因此LinkedList不支持随机访问 4. LinkedList的任意位置插入和删除元素时效率比较高时间复杂度为O(1) 5. LinkedList比较适合任意位置插入的场景 1.2 LinkedList的使用 1.LinkedList的构造 方法 解释 LikedList() 无参构造 public LinkedList(Collection? extends E c) 使用其他集合容器中元素构造 List public static void main(String[] args) { // 构造一个空的LinkedList ListInteger list1 new LinkedList(); ListString list2 new java.util.ArrayList(); list2.add(JavaSE); list2.add(JavaWeb); list2.add(JavaEE); // 使用ArrayList构造LinkedList ListString list3 new LinkedList(list2); } 2.LinkedList的其它常用方法介绍 方法 解释 boolean add (E e) 尾插 e void add (int index, E element) 将 e 插入到 index 位置 boolean addAll (Collection? extends E c) 尾插 c 中的元素 E remove (int index) 删除 index 位置元素 boolean remove (Object o) 删除遇到的第一个 o E get (int index) 获取下标 index 位置元素 E set (int index, E element) 将下标 index 位置元素设置为 element void clear () 清空 boolean contains (Object o) 判断 o 是否在线性表中 int indexOf (Object o) 返回第一个 o 所在下标 int lastIndexOf (Object o) 返回最后一个 o 的下标 ListE subList (int fromIndex, int toIndex) 截取部分 list 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); // 在起始位置插入0 list.add(0, 0); // add(index, elem): 在index位置插入元素elem System.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否则返回false if(!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位置的元素设置为elem System.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()); } 3.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的区别 不同点 ArrayList LinkedList 存储空间上 物理上一定连续 逻辑上连续但物理上不一定连续 随机访问 支持 O(1) 不支持 O(N) 头插 需要搬移元素效率低 O(N) 只需修改引用的指向时间复杂度为 O(1) 插入 空间不够时需要扩容 没有容量的概念 应用场景 元素高效存储 频繁访问 任意位置插入和删除频繁 完。
