做外贸的专业网站,开发者选项怎么打开,推荐六款适合做小说阅读站及小说下载站的wordpress 模板,wordpress换字体#x1f525;博客主页#xff1a; 小扳_-CSDN博客 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 双链表的说明 1.1 双链表 - 创建 1.2 双链表 - 根据索引查找节点 1.3 双链表 - 根据索引插入节点 1.4 双链表 - 头插节点 1.5 双链表 - 尾插 1.6 双链表 - 根据索引来… 博客主页 小扳_-CSDN博客 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 双链表的说明 1.1 双链表 - 创建 1.2 双链表 - 根据索引查找节点 1.3 双链表 - 根据索引插入节点 1.4 双链表 - 头插节点 1.5 双链表 - 尾插 1.6 双链表 - 根据索引来删除节点 1.7 头删节点 1.8 尾删节点 1.9 实现迭代器循环 2.0 双链表完整的实现代码 3.0 环形双链表的说明 3.1 环形双链表 - 创建 3.2 环形双链表 - 头插节点 3.3 环形双链表 - 尾插节点 3.4 环形双链表 - 头删节点 3.5 环形双链表 - 尾删节点 3.6 环形链表 - 根据值来删除节点 4.0 环形双链表完整的实现代码 1.0 双链表的说明 双链表是一种数据结构其中每个节点包含两个指针一个指向前一个节点一个指向后一个节点。双链表可以在任意位置插入或删除节点而不需要像单链表那样遍历整个链表来找到需要操作的位置。双链表可以用于实现栈、队列、以及其他需要快速插入和删除操作的数据结构。由于每个节点包含两个指针双链表的内存占用量通常比单链表更大。 1.1 双链表 - 创建 把双链表封装成一个类类中还需要封装一个节点类 Node该节点类的成员有指向前一个节点的变量 Node prev值 value 指向后一个节点的变量 Node next 。
代码如下 public class MyDoubleLists{private final Node hand;private final Node tail;private static class Node {public Node prev;public Node next;public int value;public Node(Node prev, int value, Node next) {this.prev prev;this.next next;this.value value;}}public MyDoubleLists() {hand new Node(null,0,null);tail new Node(hand,-1,null);hand.next tail;tail.prev hand;}} 注意外部类中还需要定义头节点尾节点再利用外部类的构造器中就可以完成对头尾节点的初始化了。内部类中的节点类建议用静态来修饰。 1.2 双链表 - 根据索引查找节点 由于这个方法可以为其他几个方法提供服务因此把这个方法独立出来。实现思路为开始的节点应为 hand循环终止条件为p tail 当指向尾节点的那一刻就该结束循环了。还要加一个变量 i -1 每一次循环结束要进行 i ,当 i index 时找到了该索引的节点返回该节点即可若循环结束还是没找到就得返回 null 。
代码如下 //根据索引查找节点private Node findNode(int index) {int i -1;for (Node p hand; p !tail ; p p.next,i){if (i index) {return p;}}return null;} 这个方法一般不会对外开发因此加上 private 来修饰当 i -1 时返回的时头节点所以一开始的节点为 hand 。对外是索引从 0 开始才会存储值的对于头节点存储什么值是不关心的。 1.3 双链表 - 根据索引插入节点 根据索引插入节点提前需要准备好该节点的前一个节点 prev、该节点的后一个节点 next 。通过以上已经实现的方法来找到插入位置的前一个结点prev findNode(index - 1)后一个节点也就可以找到了next prev.next。
代码如下 //根据索引插入节点public void insert(int index, int value) {Node p findNode(index - 1);if (p null){throw new RuntimeException(用索引访问失败);}Node prev p;Node next prev.next;Node insertNode new Node(prev, value,next);prev.next insertNode;next.prev insertNode;} prev.next 指向新的节点next.prev 指向上一个节点。新的节点的头节点的引用为 prev尾节点为 next 。 1.4 双链表 - 头插节点 其实这个方法就比较简单了这个就是根据索引 0 来插入节点的就是一个索引等于0的特例所以可以直接调用已经实现的 insert(0int value) 方法。
代码如下 //头插节点public void addFirst(int value) {insert(0,value);} 1.5 双链表 - 尾插 对尾部的操作是双链表的一个很大的优势对尾部的查询、增加节点、删除节点效率都很快因为对尾节点是有记录的就不用从头开始来查找尾部节点了直接可以得到。 实现方法的思路为需要找到插入的前一个节点插入的后一个节点肯定是尾节点所以可以通过 prev tail.prev来找到插入的前一个节点。
代码如下 //尾插节点public void addLast(int value) {Node lats tail;Node prev lats.prev;Node addNode new Node(prev,value,lats);prev.next addNode;lats.prev addNode;} 新的节点的前一个节点为 prev 后节点为 tailprev.next 与 tail.prev 就要更改为指向新的节点了。 1.6 双链表 - 根据索引来删除节点 先通过已经实现的 findNode() 方法来找到该索引的节点还有找到删除该节点的前一个节点与后一个节点。
代码如下 //根据索引来删除节点public void remove(int index) {Node prev findNode(index - 1);if (prev null) {throw new RuntimeException(用索引来删除数据失败);}Node remove prev.next;if (remove tail) {throw new RuntimeException(用索引来删除数据失败);}Node next remove.next;prev.next next;next.prev next;} 接着就可以将要删除的前一个节点指向要删除的节点后一个节点但是考虑两种情况第一种当要删除的节点没找到就要抛出异常了。第二种当发现要删除的节点为 tail 时需要抛出异常总不能自己把自己的尾巴 切了吧 然而不用考虑是否把头节点删除因为要删除的节点总是拿不到头节点。 1.7 头删节点 当索引为0时就是头删是 remove(0) 方法的一个特例。可以直接来调用根据索引来删除节点的方法。
代码如下 //头删节点public void removeFirst() {remove(0);} 1.8 尾删节点 双链表尾删的效率是很高的因为对尾节点是有记录的。
代码如下 //尾删节点public void removeLast() {Node remove tail.prev;if (remove hand){throw new RuntimeException();}Node prev remove.prev;prev.next tail;tail.prev prev;}需要找到三个节点要删除的节点、删除节点的前一个节点、还有尾节点。需要注意的是判断要删除的节点为头节点需要抛出异常总不能自己把自己的 头部 给切了吧。 1.9 实现迭代器循环 这个完成 Iterable 接口创建新的该接口子类对象重写两个方法即可。
代码如下 //实现迭代器循环Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p hand.next;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic Integer next() {int value p.value;p p.next;return value;}};} 需要注意的是头节点的值是不用在乎的所以遍历开始为 hand.next 循环结束条件为p tail遍历到尾节点就要终止了。 2.0 双链表完整的实现代码 import java.util.Iterator;public class MyDoubleLists implements IterableInteger{private final Node hand;private final Node tail;private static class Node {public Node prev;public Node next;public int value;public Node(Node prev, int value, Node next) {this.prev prev;this.next next;this.value value;}}public MyDoubleLists() {hand new Node(null,0,null);tail new Node(hand,-1,null);hand.next tail;tail.prev hand;}//根据索引查找节点private Node findNode(int index) {int i -1;for (Node p hand; p !tail ; p p.next,i){if (i index) {return p;}}return null;}//根据索引插入节点public void insert(int index, int value) {Node p findNode(index - 1);if (p null){throw new RuntimeException(用索引访问失败);}Node prev p;Node next prev.next;Node insertNode new Node(prev, value,next);prev.next insertNode;next.prev insertNode;}//头插节点public void addFirst(int value) {insert(0,value);}//尾插节点public void addLast(int value) {Node lats tail;Node prev lats.prev;Node addNode new Node(prev,value,lats);prev.next addNode;lats.prev addNode;}//根据索引来删除节点public void remove(int index) {Node prev findNode(index - 1);if (prev null) {throw new RuntimeException(用索引来删除数据失败);}Node remove prev.next;if (remove tail) {throw new RuntimeException(用索引来删除数据失败);}Node next remove.next;prev.next next;next.prev next;}//头删节点public void removeFirst() {remove(0);}//尾删节点public void removeLast() {Node remove tail.prev;if (remove hand){throw new RuntimeException();}Node prev remove.prev;prev.next tail;tail.prev prev;}//根据索引来查询数据public int get(int index) {Node find findNode(index);if (find null){throw new RuntimeException(根据该索引找不到数据);}return find.value;}//实现迭代器循环Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p hand.next;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic Integer next() {int value p.value;p p.next;return value;}};}} 3.0 环形双链表的说明 环形双链表是一种数据结构它类似于双向链表但是链表的最后一个节点指向第一个节点形成一个环形结构。简单来说先对比与一般的双链表环形双链表就是头尾节点都是同一个节点。 3.1 环形双链表 - 创建 把环形双链表看成一个对象该类中需要封装一个节点的内部类对外不开放的需要用限制修饰符来修饰。外部类中的成员变为 sentinel 即作为头节点也作为尾节点。
代码如下 public class MyAnnularDoubleList{private final Node sentinel;private static class Node {public Node prev;public int value;public Node next;public Node(Node prev, int value, Node next) {this.prev prev;this.value value;this.next next;}}public MyAnnularDoubleList() {sentinel new Node(null,0,null);sentinel.prev sentinel;sentinel.next sentinel;}} 在创建环形双链表时在用无参构造器就可以先把 sentinel 初始化了。 3.2 环形双链表 - 头插节点 根据 next sentinel.next 就可以得到插入点的下一个节点就可以把新节点的指向的前一个节点来指向 sntinel新节点的指向后一个节点来指向 next 。 这里需要考虑一种情况假设该环形双链表中就只有一个 sentinel 节点以上阐述的思路还能不能用呢答案时可以的如果实在理解不了的话可以把一个 sentinel 节点想象成两个 sentinel 节点效果都是一样的都是指向自己嘛。
代码如下 //头插节点public void addFirst(int value) {Node hand sentinel;Node tail sentinel.next;Node addNode new Node(hand,value,tail);hand.next addNode;tail.prev addNode;} 3.3 环形双链表 - 尾插节点 根据 prev sentinel.prev 来找到插入节点的前一个的节点插入节点的后一个节点就是 sentinel 新节点的指向前的节点为 prev新节点的指向后的节点为 sentinel 接着 prev.next 指向新节点sentinel.prev 指向新节点。
代码如下 //尾插节点public void addLast(int value) {Node prev sentinel.prev;Node next sentinel;Node addNode new Node(prev,value,next);prev.next addNode;next.prev addNode;} 同理不需要额外考虑当节点只有一个时以上代码依旧可以实现尾插节点。 3.4 环形双链表 - 头删节点 根据 remove sentinel.next 可以得到需要删除的节点再由 next remove.next得到删除节点的后一个节点这样三个节点后已知了santinel.next 指向 next next.prev 指向sentinel 剩下的没有被引用的节点对象会被 JVM 自动回收。
代码如下 //头删节点public void removeFirst() {Node remove sentinel.next;if (remove sentinel) {throw new RuntimeException(删除失败);}Node next remove.next;sentinel.next next;next.prev sentinel;} 需要注意的是当删除的节点为 sentinel 需要抛出异常但是个人感觉不加判断也可以sentinel 根本不会被删除即使只有 sentinel 一直被删除。 3.5 环形双链表 - 尾删节点 根据 remove sentinel.prev 得到需要删除的节点通过 prev remove.prev 得到需要删除的前一个节点prev.next 指向 sentinelsentinel.prev 指向 prev 即可。
代码如下 //尾删节点public void removeLast() {Node remove sentinel.prev;Node prev remove.prev;prev.next sentinel;sentinel.prev prev;} 同样的当删除的节点为 sentinel 需要抛出异常但是个人感觉不加判断也可以sentinel 根本不会被删除即使只有 sentinel 一直被删除。 3.6 环形链表 - 根据值来删除节点 先独立一个方法根据值来查询节点一开始的循环节点为 sentinel.next 对于 sentinel 里面的值是什么根本不在乎的。循环终止条件为p sentinel 已经转完一圈了。找到就返回该节点找不到就返回 null 。删除的原理是一样的得先找到三个节点然后把前后节点直接关联起来。
代码如下 //根据值来删除节点private Node findValue (int value) {for (Node p sentinel.next; p ! sentinel; p p.next) {if (p.value value) {return p;}}return null;}public void removeValue (int value) {Node remove findValue(value);if (remove null) {throw new RuntimeException(找不到该数据来删除相对应的节点);}Node prev remove.prev;Node next remove.next;prev.next next;next.prev prev;} 需要注意的是当接收到的节点为 null 时需要抛出异常找不到对应该值的节点。 4.0 环形双链表完整的实现代码 import java.util.Iterator;public class MyAnnularDoubleList implements IterableInteger{private final Node sentinel;private static class Node {public Node prev;public int value;public Node next;public Node(Node prev, int value, Node next) {this.prev prev;this.value value;this.next next;}}public MyAnnularDoubleList() {sentinel new Node(null,0,null);sentinel.prev sentinel;sentinel.next sentinel;}//头插节点public void addFirst(int value) {Node hand sentinel;Node tail sentinel.next;Node addNode new Node(hand,value,tail);hand.next addNode;tail.prev addNode;}//尾插节点public void addLast(int value) {Node prev sentinel.prev;Node next sentinel;Node addNode new Node(prev,value,next);prev.next addNode;next.prev addNode;}//头删节点public void removeFirst() {Node remove sentinel.next;if (remove sentinel) {throw new RuntimeException(删除失败);}Node next remove.next;sentinel.next next;next.prev sentinel;}//尾删节点public void removeLast() {Node remove sentinel.prev;Node prev remove.prev;prev.next sentinel;sentinel.prev prev;}//根据值来删除节点private Node findValue (int value) {for (Node p sentinel.next; p ! sentinel; p p.next) {if (p.value value) {return p;}}return null;}public void removeValue (int value) {Node remove findValue(value);if (remove null) {throw new RuntimeException(找不到该数据来删除相对应的节点);}Node prev remove.prev;Node next remove.next;prev.next next;next.prev prev;}//实现迭代器Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p sentinel.next;Overridepublic boolean hasNext() {return p ! sentinel;}Overridepublic Integer next() {int value p.value;p p.next;return value;}};}
}
