网站建设的简洁性做高效能的父母网站

当前位置： 首页 > news >正文

网站建设的简洁性,做高效能的父母网站,网站制作书生,微信营销模式有乐观学习#xff0c;乐观生活#xff0c;才能不断前进啊#xff01;#xff01;#xff01; 我的主页#xff1a;optimistic_chen 我的专栏#xff1a;c语言 #xff0c;Java 欢迎大家访问~ 创作不易#xff0c;大佬们点赞鼓励下吧~ 文章目录 前言链表#xff08;MyS… 乐观学习乐观生活才能不断前进啊 我的主页optimistic_chen 我的专栏c语言 Java 欢迎大家访问~ 创作不易大佬们点赞鼓励下吧~ 文章目录 前言链表MySingleList具体功能代码 LinkedList简介LinkedList的模拟实现LinkedList的使用LinkedList的构造LinkedList的方法LinkedList的遍历 ArrayList和LinkeddList的区别完结 前言 上篇博客详细写了ArrayList的相关问题包括上图极其重要我会在最近几篇博客中都有附上。 ArrayList的优点很明显底层逻辑是一个数组它通过下标去访问数据的速度非常快。但是在ArrayList任意位置插入或者删除元素时就需要将后序元素整体往前或者往后搬移时间复杂度为O(n)效率比较低 所以java集合框架中引入了LinkedList类即链表结构。 链表MySingleList 链表作为线性表的一种它与顺序表截然相反链表是一种物理存储结构 上 非连续存储结构 数据元素的逻辑顺序是通过链表中的引用 链接次序实现的 之前C语言了解过这方面的知识C语言—链表专题所以我们有一定的基础我相信链表对于大家一定是熟悉的存在。我们先由易入难先自己尝试一下单链表MySingleList的功能实现为接下来的 LinkedList(无头双向链表) 打下基础. 接口 public interface IList {public void addFirst(int data);public void addLast(int data);public void addIndex(int index,int data);public boolean contains(int key);public void remove(int key);public void removeAllKey(int key);public int size();public void clear();public void display(); } 具体功能代码 头插法 Overridepublic void addFirst(int data) {ListNode node new ListNode(data);node.nexthead;headnode;}尾插法 Overridepublic void addLast(int data) {ListNode node new ListNode(data);if(headnull){head node;return;}ListNode curhead;while(cur.next!null){cur cur.next;}cur.nextnode;}任意位置插入,第一个数据节点为0号下标 Overridepublic void addIndex(int index, int data) {int lensize();if(index0||indexlen){System.out.println(index位置不合法);return;}if(index0){addFirst(data);return;}if(indexlen){addLast(data);return;}ListNode curhead;while(index-1!0){curcur.next;index–;}ListNode nodenew ListNode(data);node.next cur.next;cur.nextnode;}查找是否包含关键字key是否在单链表当中 Overridepublic boolean contains(int key) {ListNode curhead;while(cur!null){if(cur.valkey){return true;}curcur.next;}return false;}删除第一次出现关键字为key的节点 Overridepublic void remove(int key) {if(headnull){return;}if(head.valkey){headhead.next;return;}ListNode curfindNodeOfKey(key);if(curnull){return;}ListNode del cur.next;cur.nextdel.next;}private ListNode findNodeOfKey(int key){ListNode curhead;while(cur.next!null) {if (cur.next.val key) {return cur;}cur cur.next;}return null;} 删除所有值为key的节点 Overridepublic void removeAllKey(int key) {if(headnull){return;}ListNode prevhead;ListNode curhead.next;while(cur!null){if(cur.valkey){prev.nextcur.next;cur cur.next;}else{prevcur;cur cur.next;}if(head.valkey){headhead.next;return;}}}得到单链表的长度 Overridepublic int size() {int len0;ListNode curhead;while(cur!null){len;curcur.next;}return len;}清空链表 Overridepublic void clear() {ListNode curhead;while(cur!null){ListNode curNcur.next;cur.nextnull;curcurN;}headnull;}LinkedList简介 LinkedList的底层是双向链表结构由于链表没有将元素存储在连续的空间中元素存储在单独的节点中然后通过引用将节点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。 总结 LinkedList实现了List接口LinkedList的底层使用了双向链表LinkedList没有实现RandomAccess接口因此LinkedList不支持随机访问LinkedList的任意位置插入和删除元素时效率比较高时间复杂度为O(1)LinkedList比较适合任意位置插入的场景 LinkedList的模拟实现 头插法 Overridepublic void addFirst(int data) {ListNode nodenew ListNode(data);if(headnull){headlastnode;}else{node.nexthead;head.prevnode;headnode;}}尾插法 Overridepublic void addLast(int data) {ListNode nodenew ListNode(data);if(headnull){headlastnode;}else{last.nextnode;node.prevlast;last last.next;}}任意位置插入,第一个数据节点为0号下标 Overridepublic void addIndex(int index, int data) {int lensize();if(index0||indexlen){return;}if(index0){addFirst(data);return;}if(indexlen){addLast(data);return;}ListNode curfindIndex(index);ListNode nodenew ListNode(data);node.nextcur;cur.prev.nextnode;node.prevcur.prev;cur.nextnode;} private ListNode findIndex(int index){ListNode curhead;while(index!0){cur cur.next;index–;}return cur;}查找是否包含关键字key是否在链表当中 Overridepublic boolean contains(int key) {ListNode curhead;int count0;while(cur!null){if(cur.valkey) {return true;}cur cur.next;}return false;} 删除第一次出现关键字为key的节点 Overridepublic void remove(int key) {ListNode curhead;while(cur!null){//开始删除if(cur.valkey){//有可能是头节点if(curhead){head head.next;if(head!null){head.prevnull;}}else{cur.prev.next cur.next;if(cur.nextnull){//有可能是尾节点last last.prev;}else{cur.next.prev cur.prev;}}return;}else{cur cur.next;}}}删除所有值为key的节点 Overridepublic void removeAllKey(int key) {ListNode curhead;while(cur!null){//开始删除if(cur.valkey){//有可能是头节点if(curhead){head head.next;if(head!null){head.prevnull;}}else{cur.prev.next cur.next;if(cur.nextnull){//有可能是尾节点last last.prev;}else{cur.next.prev cur.prev;}}}else{cur cur.next;}}}LinkedList的使用 前面我们自主实现了LinkedList的各种方法只是为了大家更好的理解和学习以后做题可能会运用到类似的想法或思路可以更加高效的完成题目平时也可以直接使用LinkedList下的方法。如下图
LinkedList的构造 public static void main(String[] args) {ListInteger list1new LinkedListInteger();LinkedListInteger list2 new LinkedListInteger();//使用ArrayList构造LinkedList ListString list3new ArrayList();ListString list4new LinkedList(list3);}为什么可以有的构造可以用List有的用LinkedList,甚至出现了ArrayList一切都是这张贯穿整个数据结构的图。
LinkedList的方法 public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1); // add(): 表示尾插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);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回ListInteger list2 list.subList(0, 3); System.out.println(list);System.out.println(list2);list.clear(); // 将list中元素清空System.out.println(list.size()); }LinkedList的遍历 之前ArrayList博客【Java数据结构】—List(ArrayList) 讲过线性表的遍历这次补充一下… public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1); // add(): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());// 使用反向迭代器—反向遍历ListIteratorInteger it list.listIterator(list.size());while (it.hasPrevious()){System.out.print(it.previous() );} }ArrayList和LinkeddList的区别 不同ArrayListLinkedList存储空间物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(n)头插空间不够时扩容不存在容量的概念运用场景元素高效存储频繁访问频繁任意位置的插入和删除 完结 好了到这里Java语法部分就已经结束了~ 如果这个系列博客对你有帮助的话可以点一个免费的赞并收藏起来哟~ 可以点点关注避免找不到我~ 我的主页optimistic_chen 我们下期不见不散~~Java 下期预告: 【Java数据结构】- - - List