湛江专业建站推广机构,网站建设流程包括哪些内容,wordpress怎么写接口,陕西网站推广公司1. 链表 1.1 结构组成 链表是一种物理存储结构上非连续存储结构#xff0c;数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。 链表的结构如下图所示#xff0c;是由很多个节点相互通过引用来连接而成的#xff1b;每一个节点由两部分组成#xff0c;分别数据域…1. 链表 1.1 结构组成 链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。 链表的结构如下图所示是由很多个节点相互通过引用来连接而成的每一个节点由两部分组成分别数据域存放当前节点的数据和next域用来存放连接下一个节点的引用 下图是链表的结构每一个节点都有一个地址方便前一个节点的next域来存放。多个节点通过引用连接成整个链表。 实际在内存中每个节点的地址是随机的只不过用这个节点的next,找到了下一个节点的地址由此实现链接。
1.2 链表分类 主要通过链表方向是否循环是否带箭头主要分为以下六个特色 下面是一些不同种类的链表图解 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 将以上六种单一种类进行组合可以构成一下8种链表 虽然有这么多的链表的结构但是我们重点掌握两种: 无头单向非循环链表结构简单一般不会单独用来存数据 无头双向链表在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2.无头单向非循环链表的实现
2.1 自定义MyArrayList类 建立一个Ilist接口在里面构造mysinglelist链表要实现的抽象方法
public interface IList {//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display();
} 无头单向非循环链表的节点是由两个属性value域和next域构成的同时也要在自定义MyArrayList类里面使用内部类创建链表节点类之后再链表类里面创建一个头结点来代表当前链表的引用同时实现我们之前创建的接口接下来重写接口里面的方法让其能够具体化
public class MySingleList implements IList {//创建链表节点//节点的内部类static class ListNode{public int value;public ListNode next;//表示下一个节点的引用public ListNode(int value){this.value value;}}public ListNode head;Overridepublic void addFirst(int data) {}Overridepublic void addLast(int data) {}Overridepublic void addIndex(int index, int data) {}Overridepublic boolean contains(int key) {return false;}Overridepublic void remove(int key) {}Overridepublic void removeAllKey(int key) {}Overridepublic int size() {return 0;}Overridepublic void clear() {}Overridepublic void display() {}
}
} 下面代码主要是创建多个节点
public void createList() {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;}
2.2 遍历链表 思路 1、当前节点是怎么走到下一个节点的 2、当遍历链表时如何判断当前链表的所有节点都遍历完 首先建立一个当前节点cur通过cur来指向next域里面的节点地址并访问和输出操作来完成整个链表的遍历让cur的next域指向存放下一个节点的地址并访问以此类推逐步完成整个链表的遍历问题一如果cur指向的下一个节点的next域里存放的不是地址而是空指针则当前的链表被遍历即将结束问题二 下面是重写的遍历链表具体的方法 Overridepublic void display() {ListNode cur head;while (cur ! null){System.out.print(cur.value-);cur cur.next;}System.out.println( );} public static void main(String[] args) {MySingleList list new MySingleList();list.createList();list.display();} 下面代码的执行结果 2.3 得到单链表的长度 对整个链表进行遍历使用计数器进行记录遍历的次数最后将计数器的值返回即可下图代码是该方法的具体实现 Overridepublic int size() {int count 0;ListNode cur head;while (cur ! null){count;cur cur.next;}return count;}
public static void main(String[] args) {MySingleList list new MySingleList();list.createList();list.display();System.out.println(list.size());} 下面代码的执行结果 2.4 查找是否包含关键字 对链表进行遍历然后将关键字key和链表数值进行比较如果存在key关键字则返回true反之则返回false 方法具体实现的代码如下 Overridepublic boolean contains(int key) {ListNode cur this.head;while (cur ! null){if ( cur.valuekey){return true;}cur cur.next;}return false;} 测试代码和执行结果如下
public static void main(String[] args) {MySingleList list new MySingleList();list.createList();list.display();System.out.println(list.contains(45));} 2.5头插法 思路 1、将之前第一个节点的地址存储到我们新添加的节点的next域里面 2、将新添加的节点赋给head作为新链表的头节点链表图解如下图所示 具体实现头插法的方法如下
Overridepublic void addFirst(int data) {ListNode node new ListNode(data);if (this.head null){this.head node;}else {node.next this.head;this.head node;} 测试代码及结果
public static void main(String[] args) {MySingleList list new MySingleList();list.createList();list.display();list.addFirst(1);list.addFirst(0);list.display();} 2.6尾插法 思路 1、首先对该链表进行遍历当遍历到最后一个节点时将新添加的节点的地址给最后一个节点的next域。 2、如果该链表为空直接将该新增节点设为头节点 链表图解 具体实现方法带吗如下 Overridepublic void addLast(int data) {ListNode node new ListNode(data);ListNode cur this.head;if (this.head null){this.head node;}else {//一直找最后一个节点while (cur.next ! null){cur cur.next;}cur.next node;}}测试代码及结果
public static void main(String[] args) {MySingleList list new MySingleList();list.createList();list.display();list.addLast(9);list.addLast(10);list.display();} 分析总结头插法的时间复杂度为o1尾插法的时间复杂度为oN
2.7任意位置插入 思路 1、需要插入的位置必须为合法如果不合法我们会抛出一个异常进行提醒所以首先自定义一个异常
public class ListIndexOutOfException extends RuntimeException{public ListIndexOutOfException(String msg){super(msg);}
} 2、任意位置插入首先分几种情况插在开头插在结尾插在中间 2.1 当插在链表开头和结尾时可以使用头插法和尾差法 2.2 当插在其他的位置时首先让cur走到index前面一个节点的位置此处创建一个方法这时候就需要考虑将下一个节点加在index的位置时如何处理建立连接的顺序其次注意建立连接的时候一定要先建立添加节点和后节点的连接其次在确立添加节点和前一个节点的位置链表图解如下 具体实现方法代码如下 Overridepublic void addIndex(int index, int data) {if(index 0 || index size()) {//抛自定义的异常throw new ListIndexOutOfException(你当前输入的索引有问题);}if(index 0) {addFirst(data);return;}if(index size()) {addLast(data);return;}ListNode cur searchPrev(index);//node之前的一个节点ListNode node new ListNode(data);node.next cur.next;cur.next node;}private ListNode searchPrev(int index) {//该方法是找到添加节点node在index时//index之前的节点的索引ListNode cur this.head;int count 0;while (count ! index-1 ) {cur cur.next;count;}return cur;} 测试代码及结果如下 public static void main(String[] args) {MySingleList list new MySingleList();list.createList();list.display();list.addIndex(2,2);list.addIndex(3,3);list.display();} 2.8删除第一次出现关键字为key的节点 思路大体分为以下四种情况 1.链表为空链表一个节点也没有 2.我们所需要删除数据所在的节点在第一个 3.遍历完所有的链表节点发现没有要删除的数据 4.有要删除的数据且不是第一个节点 具体实现方法代码如下
public void remove(int key) {if(this.head null) {//一个节点都没有 无法删除return;}if(this.head.value key) {this.head this.head.next;return;}//1. 找到前驱ListNode cur findPrev(key);//2、判断返回值是否为空if(cur null) {System.out.println(没有你要删除的数字);return;}//3、删除ListNode del cur.next;cur.next del.next;}private ListNode findPrev(int key) {//找到要删除节点的前一个节点ListNode cur this.head;while (cur.next ! null) {if(cur.next.value key) {return cur;}cur cur.next;}return null;} 测试代码及结果如下
public static void main(String[] args) {MySingleList list new MySingleList();list.createList();list.display();list.addIndex(2,2);list.addIndex(3,3);list.remove(100);list.display();} 2.9回收链表 将头节点置为空即可代码和结果如下所示 Overridepublic void clear() {this.head null;} ps本次的内容就到这里了如果你喜欢的话就请一键三连哦
