用ps怎么做网站步骤,有没有专门做素食的美食网站,上海网页制作电话,网站建设维保免费内容【2】单链表 1、单链表2、单链表的设计3、接口设计4、SingleLinkedList5、node(int index) 返回索引位置的节点6、clear()7、添加8、删除9、indexOf(E element) 1、单链表
#x1f4d5;动态数组有个明显的缺点 #x1f58a; 可能会造成内存空间的大量浪费 #x1f4d5; 能否… 【2】单链表 1、单链表2、单链表的设计3、接口设计4、SingleLinkedList5、node(int index) 返回索引位置的节点6、clear()7、添加8、删除9、indexOf(E element) 1、单链表
动态数组有个明显的缺点 可能会造成内存空间的大量浪费 能否用到多少就申请多少内存 链表可以办到这一点 链表是一种链式存储的线性表所有元素的内存地址不一定是连续的 每个节点中有一个成员变量指记录着下一个节点的内存地址 2、单链表的设计 size 存储单链表的节点个数 first 被称作头指针指向头节点 每个节点Node中有 element 属性存储具体的数据next 属性存储下一个节点的内存地址 尾节点的 next 属性为 null 单链表也是线性表有索引的概念 3、接口设计 链表的大部分接口和动态数组是一致的 public interface ListE {/*** 返回存储的元素数量*/int size();/*** 是否为空*/boolean isEmpty();/*** 是否包含给定元素*/boolean contains(E element);/*** 返回索引位置的元素*/E get(int index);/*** 返回指定元素的索引*/int indexOf(E element);/*** 添加元素到尾部*/void add(E element);/*** 往索引位置添加元素*/void add(int index, E element);/*** 删除索引位置的元素** return 被删除的元素*/E remove(int index);/*** 清空所有元素*/void clear();/*** 设置索引位置的元素*/E set(int index, E element);
}4、SingleLinkedList 往单链表中添加一个数据就会创建的一个 Node 对象
public class SingleLinkedListE implements ListE {private int size;private NodeE first;/*** 返回存储的元素数量*/Overridepublic int size() {return 0;}/*** 是否为空*/Overridepublic boolean isEmpty() {return false;}/*** 是否包含给定元素*/Overridepublic boolean contains(E element) {return false;}/*** 返回索引位置的元素*/Overridepublic E get(int index) {return null;}/*** 返回指定元素的索引*/Overridepublic int indexOf(E element) {return 0;}/*** 添加元素到尾部*/Overridepublic void add(E element) {}/*** 往索引位置添加元素*/Overridepublic void add(int index, E element) {}/*** 删除索引位置的元素** return 被删除的元素*/Overridepublic E remove(int index) {return null;}/*** 清空所有元素*/Overridepublic void clear() {}/*** 设置索引位置的元素*/Overridepublic E set(int index, E element) {return null;}private static final class NodeE {private E element;private NodeE next;public Node(E element, NodeE next) {this.element element;this.next next;}}}5、node(int index) 返回索引位置的节点 若需要 index 位置的节点则从 first 头指针指向的头节点开始 next index 次即可 /*** 返回index索引处的节点*/private NodeE node(int index) {checkIndex(index);NodeE node first;for (int i 0; i index; i) {node node.next;}return node;}get(int index) 方法 /*** 返回索引位置的元素*/Overridepublic E get(int index) {return node(index).element;}set(int index, E element) 方法 /*** 设置索引位置的元素*/Overridepublic E set(int index, E element) {NodeE node node(index);E e node.element;node.element element;return e;}6、clear() first 头指针指向 null则头节点会被Java的垃圾回收器回收 头节点的内存被回收会导致它 next 指向的节点也被回收最终整个链表就被清空了 /*** 清空所有元素*/Overridepublic void clear() {first null;size 0;}7、添加 如果 index 0把元素添加到头节点位置直接让 first 头指针指向新节点新节点的 next 指向之前的头节点 如果 index ! 0① 找到 index - 1 索引处的节点 prev② 新节点的 next 指向 prev.next③ prev.next 指向新节点 * 往索引位置添加元素*/Overridepublic void add(int index, E element) {checkIndex4Add(index);if (index 0) {first new Node(element, first);} else {NodeE prev node(index - 1);prev.next new Node(element, prev.next);}size;}在编写链表代码时要注意边界测试比如 index 为 0 、size – 1 、size 时 边界介绍0往头节点位置添加元素size-1边界检查通过size往链表尾部添加元素 /*** 添加元素到尾部*/Overridepublic void add(E element) {add(size, element);}8、删除 如果 index 0删除头节点元素直接用头指针 first 指向 first.next 如果 index ! 0① 找到前一个节点 prev② prev.next 指向 prev.next.next /*** 删除索引位置的元素** return 被删除的元素*/Overridepublic E remove(int index) {checkIndex(index);NodeE node first;if (index 0) {first first.next;} else {NodeE prev node(index - 1);node prev.next;prev.next node.next;}size--;return node.element;}在编写链表代码时要注意边界测试比如 index 为 0 、size – 1 、size 时 边界介绍0删除头节点size-1边界检查通过size抛异常
9、indexOf(E element) 从 first 开始挨个遍历比较 考虑 element null 的情况 /*** 返回指定元素的索引*/Overridepublic int indexOf(E element) {NodeE node first;if (element null) {for (int i 0; i size; i) {if (node.element null) return i;node node.next;}} else {for (int i 0; i size; i) {if (element.equals(node.element)) return i;node node.next;}}return ELEMENT_NOT_FOUND;}单链表完整代码
