采集网站如何收录住房和城乡建设部官网政务服务门户

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

采集网站如何收录,住房和城乡建设部官网政务服务门户,域名永久买入要多少钱,南昌网站外包上期内容我们讲述了顺序表#xff0c;知道了顺序表的底层是一段连续的空间进行存储(数组)#xff0c;在插入元素或者删除元素需要将顺序表中的元素整体移动#xff0c;时间复杂度是O(n)#xff0c;效率比较低。因此#xff0c;在Java的集合结构中又引入了链表来解决这一问…         上期内容我们讲述了顺序表知道了顺序表的底层是一段连续的空间进行存储(数组)在插入元素或者删除元素需要将顺序表中的元素整体移动时间复杂度是O(n)效率比较低。因此在Java的集合结构中又引入了链表来解决这一问题。 1、链表  链表是一种物理存储结构上非连续 存储结构数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。 下面通过图解来理解链表的结构 如上图所示是单向链表节点的两个元素其中value存储着节点的值next存储着下一个节点的地址。因此一个单向链表可以表示为下图所示 注意
1、从上图可以看出链式结构在逻辑上是连续的但在物理上即在计算机的内存里面不一定连续。 2、 现实中的节点一般是从堆上申请出来的。 3、从堆上申请的空间是按照一定策略来分配的两次申请的空间可能连续也可能不连续。 2、链表结构 链表组合起来的结构一共有8种通过以下情况进行排列组合 2.1 单向或者双向 单向 双向  双向链表在next域的基础上增加了prev域使得通过链表的一个节点不仅能访问后继元素也能访问前驱元素 。 2.2 带头或者不带头 带头 注意这里的头并没有实际的值主要用它链接后续的节点因此head指向第一个元素的地址。 不带头 2.3 循环或者非循环      循环 非循环 这里我们重点讲单向不带头非循环链表和双向不带头非循环链表。 3、无头单向非循环链表实现 3.1 节点的实现 链表的节点主要通过静态内部类进行实现。代码如下 static class ListNode{public int val;//节点的值域public ListNode next;//下一个节点的地址public ListNode() {}public ListNode(int val) {this.val val;}}public ListNode head;//表示当前链表的头结点 这里可能有人会有疑问为什么不把头结点的声明放入内部类中呢 其实从逻辑上想,不难想明白:头结点是属于整个链表的头结点而非结点的头结点。  3.2 creatNode方法 本方法用于初始化一个链表。 public void creatNode(){ListNode node1 new ListNode(12);ListNode node2 new ListNode(23);ListNode node3 new ListNode(34);ListNode node4 new ListNode(45);ListNode node5 new ListNode(56);node1.next node2;node2.next node3;node3.next node4;node4.next node5;this.head node1;} 3.3 头插法  故名思义就是在链表的头部插入。这里有个点需要注意先插入的数据会最后输出后插入的最先输出。 在头部插入一个元素我们需要先绑定元素后面的信息再让我们的头结点指向我们要插入的元素。代码如下 //头插法public void addFirst(int data){ListNode node new ListNode(data);//一般建议在插入的时候先绑定后面的节点信息node.next head;this.head node;} 3.4 尾插法  在尾部插入一个元素需要先绑定前面的元素的信息即让最后一个元素的next指向要插入的元素。 注意如果链表中没有元素则直接让头结点指向要插入的元素。 //尾插法public void addLast(int data){ListNode cur head;ListNode node new ListNode(data);if(cur null){//如果链表中没有元素那么让头结点指向nodehead node;return;}//当cur.next null的时候那么该节点就是尾巴节点//当cur null证明该链表已经被遍历完了while (cur.next ! null){cur cur.next;}cur.next node;} 3.5  任意位置插入,第一个数据节点为0号下标 在任意位置插入首先我们要判定下标是否合法若不合法则抛出异常。第二步如果插入的下标为0则直接调用前面写的头插法函数如果下标等于链表的长度则调用尾插法函数。第三步如果插入的地方是在中间则需要先找到要插入结点的前一个结点绑定后面的信息后再进行插入。 //任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){if(index 0 || index size()){throw new IndexErrorException(下标不合法);}if(index 0){addFirst(data);return;}else if (index size()){addLast(data);return;}//1、定义cur走index-1步//2、进行插入ListNode node new ListNode(data);ListNode cur head;int count 0;while(count ! index-1){cur cur.next;count;}node.next cur.next;cur.next node;} 3.6 查找关键字key是否在单链表当中 查找关键字key只需要遍历链表看结点的value是否等于key就ok了。 //查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur head;while (cur ! null){if(cur.val key){return true;}cur cur.next;}return false;} 3.7 删除第一次出现关键字key的元素  思路删除一个结点del我们需要记录被删除结点的前一个结点cur再让前一个结点的next域cur.next指向被删除结点的下一个结点(del.next)。需要注意的是在这个过程之前需要单独删除头结点。 //删除第一次出现关键字为key的节点public void remove(int key){if(head null){return;}//单独删除头结点if(head.val key){head head.next;return;}//找到删除节点的前一个结点ListNode cur head;while (cur.next ! null){ListNode del cur.next;if(del.val key){//此时cur指向的节点就是要删除节点的前一个节点//cur.next cur.next.nextcur.next del.next;return;//删除之后返回}cur cur.next;}if(curnull){System.out.println(没有你要删除的数字);}} 3.8  删除所有值为key的节点 删除所有值为key的结点需要用到双指针的思想ps因为需要不断地记录被删除结点的前一个结点 prev指针用来找到被删除元素的前一个元素cur指针则用来遍历链表和找到被删除元素。删除的过程就是直接让prev的next域直接指向cur指针的next域再让cur指针向后走若不是被删除的元素则直接让两个指针一起往后走。最后我们需要单独删除头结点。注意这里我们在最后才删除头结点是因为前面的cur和prev指针需要使用到头结点。 //删除所有值为key的节点 public void removeAllKey(int key){if(head null){return;}ListNode prev head;ListNode cur head.next;while (cur ! null){if(cur.val key){prev.next cur.next;cur cur.next;}else{prev cur;cur cur.next;}}//单独删除头结点if(head.val key){head head.next;}} 3.9 得到单链表长度 得到单链表的长度我们需要定义一个计数器然后遍历链表让count就行了。 //得到单链表的长度public int size(){int count 0;ListNode cur head;while(cur ! null){count;cur cur.next;}return count;} 3.10 清空链表 遍历链表将链表的每个结点置空即可。 //清空链表
public void clear() {ListNode cur head;while (cur ! null){cur null;cur cur.next;}} 3.11 打印链表 遍历链表打印每个结点的value域即可。 //打印链表public void display() {ListNode cur head;while (cur! null){//如果curnull证明把链表遍历完成了System.out.print(cur.val );cur cur.next;//cur每次都在向后走一步 }System.out.println();}