昆明网站开发多少钱,网站图片漂浮代码,未来的门户网站,什么网站做ppt1. 环形链表#xff1a; 2. 建议先不要看我写得自己先实现下#xff0c;只将Node内部类复制自己命名得容器内#xff0c; 实现方法#xff1a; a. add方法#xff08;添加到头部#xff0c;尾部添加#xff0c;指定位置添加#xff09; b. get方法#xff08;获取首部… 1. 环形链表 2. 建议先不要看我写得自己先实现下只将Node内部类复制自己命名得容器内 实现方法 a. add方法添加到头部尾部添加指定位置添加 b. get方法获取首部获取尾部获取指定位置 c. remove方法删除首部删除尾部删除指定位置 d. size方法手动维护一个size变量实现0(1)复杂度 e. 迭代器实现迭代器能够循环遍历 手动实现之后每个功能只实现一种也可以再回头参照思考下即可
package com.nami.algorithm.study.day05;import java.io.Serializable;
import java.util.Iterator;
import java.util.function.Consumer;/*** 环形双向哨兵链表* 非线程安全* beyond u self and trust u self.** Author: lbc* Date: 2023-09-01 9:07* email: 594599620qq.com* Description: keep coding*/
public class RingLinkedListE implements Serializable, IterableE, Cloneable {/*** 容器已添加的元素*/private int size 1;/*** 哨兵节点*/private Node sentinel new Node(null, -1, null);/*** 初始化哨兵*/public RingLinkedList() {this.sentinel.prev this.sentinel;this.sentinel.next this.sentinel;}/*** 向链表添加数据** param element 添加的元素*/public void addFirst(E element) {Node first this.sentinel;Node next first.next;Node node new Node(first, element, next);first.next node;next.prev node;this.size;}/*** 向链表尾部添加数据** param element*/public void addLast(E element) {Node last this.sentinel.prev;Node node new Node(last, element, sentinel);last.next node;sentinel.prev node;this.size;}/*** 获取容器指定位置的值** param index* return*/public E get(int index) {if (index size - 1) {throw new IndexOutOfBoundsException(元素不存在);}Node next sentinel.next;for (int i 0; i index; next next.next, i) {}if (sentinel next) {throw new IndexOutOfBoundsException(String.format(index [%d] 不合法%n, index));}return (E) next.value;}/*** 获取指定位置节点node** param index* return*/private Node getNode(int index) {Node next sentinel.next;for (int i 0; i index; next next.next, i) {}return next;}/*** 向元素指定节点添加值** param index* param e*/public void add(int index, E e) {if (index size - 1) {throw new IndexOutOfBoundsException(元素不存在);}Node node getNode(index);Node prev node.prev;Node node1 new Node(prev, e, node);node.prev node1;prev.next node1;this.size;}/*** 移除容器内第一个元素*/public void removeFirst() {Node node getNode(0);if (sentinel node) {throw new IndexOutOfBoundsException(String.format(index [%d] 不合法%n, 0));}Node prev node.prev;Node next node.next;prev.next next;next.prev prev;--this.size;}/*** 删除第一个元素*/public void removeFirst0() {Node removed this.sentinel.next;if (removed this.sentinel) {throw new IndexOutOfBoundsException(容器内已无元素);}Node next removed.next;this.sentinel.next next;next.prev this.sentinel;}/*** 移除容器内指定位置元素** param index*/public void remove(int index) {if (index size - 1) {throw new IndexOutOfBoundsException(String.format(index [%d] 不合法%n, index));}Node node getNode(index);if (sentinel node) {throw new IndexOutOfBoundsException(String.format(index [%d] 不合法%n, 0));}Node prev node.prev;Node next node.next;prev.next next;next.prev prev;--this.size;}/*** 删除最后一个节点*/public void removeLast() {Node prev this.sentinel.prev;if (prev this.sentinel) {return;}Node next prev.next;Node prev0 prev.prev;prev0.next next;next.prev prev0;--this.size;}/*** 获取容器大小** return*/public int size() {return this.size - 1;}/*** 迭代器遍历** return*/Overridepublic Iterator iterator() {return new NodeIterator();}/*** 匿名内部类* 内部类使用到了外部类的成员变量时不能使用static修饰*/private class NodeIterator implements Iterator {Node node sentinel.next;Overridepublic boolean hasNext() {return node ! sentinel;}Overridepublic Object next() {Object value node.value;node node.next;return value;}}/*** while实现** param consumer*/public void forEach(Consumer consumer) {Node firstNode this.sentinel.next;while (firstNode ! sentinel) {consumer.accept(firstNode.value);firstNode firstNode.next;}}/*** Node类型 节点对象* 二者为组合关系所以 由外部类变为内部类对外隐藏实现细节*/private static class NodeE {/*** 上一个节点*/private NodeE prev;/*** 值*/private E value;/*** 下一个节点*/private NodeE next;public Node(NodeE prev, E value, NodeE next) {this.prev prev;this.value value;this.next next;}}}
