建企业网站怎么收费,wordpress是怎么添加登录的,谁会在掏宝网上做网站,怎么样做一个自己的网站目录 引出从ArrayList到Linkedlist手动实现ArrayList从ArrayList到LinkedList 总体设计Node类Node的方法#xff1a;根据index找node 增删改查的实现增加元素删除元素修改元素查询元素 toString方法完整代码List接口类LinkedList的实现测试类 总结 引出 1.linkedList的节点根据index找node 增删改查的实现增加元素删除元素修改元素查询元素 toString方法完整代码List接口类LinkedList的实现测试类 总结 引出 1.linkedList的节点当前上一个下一个的思想 2.根据index找node的方法根据index确定从头部还是尾部 3.linkedlist的增删改查的实现本质是改变节点的信息 4.递归方法实现自定义链表的toString方法
从ArrayList到Linkedlist 手动实现ArrayList
Java进阶3——手动实现ArrayList 源码的初步理解分析 数组插入数据和删除数据的问题 从ArrayList到LinkedList
如果发生对表的一些插入和删除操作特别是对表的前端进行那么数组就不是一种好的选择。另一种数据结构链表(linked list)。 链表由一系列节点组成这些节点不必在内存中相连。每一个节点均含有表元素和到包含该元素后继元的节点的链(link)。我们称之为next链。最后一个单元的next链引用null。 链表的插入 让每一个节点持有一个指向它在表中的前驱节点的链我们称之为双链表(doubly linked list)。 总体设计 在考虑设计方面我们将需要提供三个类 1.MyLinkedList类本身它包含到两端的链、表的大小以及一些方法。 2.Noe类它可能是一个私有的嵌套类。一个节点包含数据以及到前一个节点的链和到下一个节点的链还有一些适当的构造方法。 3.LinkedListIterator类该类抽象了位置的概念是一个私有类并实现接口Iterator。它提供了方法next、hasNext和remove的实现。
标记节点
前端创建一个额外的节点逻辑上代表开始的标记。这些额外的节点有时候就叫作标记节点(sentinel node)特别地在前端的节点有时候也叫作头节点(header node),而在末端的节点有时候也叫作尾节点(tail node) Node类
私有的内部类
当前节点前置节点后续节点表示链表中的一个基本元素 /*** 内部类节点属性当前节点前置节点后续节点* param T*/private static class NodeT {T item; // 当前的节点NodeT next; // 下一个节点NodeT prev; // 前置节点Node(NodeT prev,T element,NodeT next) {this.item element;this.prev prev;this.next next;}Overridepublic String toString() {String nextStr null;if (next!null){nextStr next.item.toString();}String prevStr null;if (prev!null){prevStr prev.item.toString();}return Node{ prev prevStr item item , next nextStr };}}Node的方法根据index找node 思路从头部开始找进行循环 public NodeT NodeByIndex(int index){NodeT x first; // 从头部开始找for (int i 0; iindex;i){x x.next;}return x;}源码采用如下策略 1.根据index和list的size确定从头部还是尾部找2.根据index找node节点 分析
降低了复杂度
如果都从头部找时间复杂度就是O(i)在最极端的情况下根据index找最后一个时间复杂度是O(N)
如果是先确定从头部找还是从尾部找则时间复杂度最大是O(N/2)
增删改查的实现
增加元素 最简单的情况都是从尾部新增元素 1.新的节点的上一个节点为之前的尾部节点2.新的尾部节点为当前新增的节点3.如果是第一个节点则需要把first设置为当前的节点4.链表的size1 Overridepublic void add(T e) {NodeT l last;NodeT newNode new Node(l, e, null); // 新增的节点尾部添加last newNode;if (lnull){// 是第一个节点first newNode;System.out.println(FirstNode ---first);}else {l.next newNode;System.out.println(Add {e} ----l);}size;}更一般的情况如下插入一个元素 删除元素 删除头部尾部中间 1.如果删除的是头部节点则让被删除的节点的下一个节点为first节点2.如果删除的尾部节点则让被删除的节点的上一个节点的下一个节点为null3.如果删除的是中间的节点让该节点的前置节点的下一个节点指向该节点的下一个节点 Overridepublic void remove(int index) {// 找到要删除的节点前置节点后续节点// 1.如果删除的是头部节点if (index0){first NodeByIndex(index1);return;}// 2.如果不是头部节点NodeT tNode NodeByIndex(index); // 当前节点NodeT prev tNode.prev; // 当前节点的上一个节点NodeT next tNode.next; // 当前节点的下一个节点if (nextnull){// 删除的是尾部节点prev.next null;return;}// 删除的是中间的某个节点// 让该节点的前置节点的下一个节点指向该节点的下一个节点prev.next next;next.prev prev;size--;}修改元素 被修改的节点的节点关系不变只需要把当前节点的元素变为最新的元素即可 代码实现 查询元素 调用node方法即可 Overridepublic T get(int index) {// 索引不能大于等于sizeif (index0 || indexsize){throw new IndexOutOfBoundsException(LinkedList的索引越界);}return NodeByIndex(index).item;}toString方法 完整代码
List接口类
package com.tianju.book.jpa.mlist;/*** 手工打造ArrayList*/
public interface MyListT {/*** 增加一个元素涉及到容量的变化*/void add(T t);/*** 根据索引删除元素* param index 要删除元素的索引超过索引索引不存在*/void remove(int index);/*** 根据索引修改一个元素* param index 要修改的索引* param t 修改的值*/void set(int index,T t);/*** 根据索引获取元素* param index 索引* return 获取的元素*/T get(int index);int size();String toString();}LinkedList的实现
package com.tianju.book.jpa.myLinkList;import com.tianju.book.jpa.mlist.MyList;public class MyLinkedListT implements MyListT {int size 0;NodeT first; // 头部节点NodeT last; // 尾部节点/*** 内部类节点属性当前节点前置节点后续节点* param T*/private static class NodeT {T item; // 当前的节点NodeT next; // 下一个节点NodeT prev; // 前置节点Node(NodeT prev,T element,NodeT next) {this.item element;this.prev prev;this.next next;}Overridepublic String toString() {String nextStr null;if (next!null){nextStr next.item.toString();}String prevStr null;if (prev!null){prevStr prev.item.toString();}return Node{ prev prevStr item item , next nextStr };}}Overridepublic void add(T e) {NodeT l last;NodeT newNode new Node(l, e, null); // 新增的节点尾部添加last newNode;if (lnull){// 是第一个节点first newNode;System.out.println(FirstNode ---first);}else {l.next newNode;System.out.println(Add {e} ----l);}size;}public NodeT NodeByIndex(int index){NodeT x first; // 从头部开始找for (int i 0; iindex;i){x x.next;}return x;}Overridepublic void remove(int index) {// 找到要删除的节点前置节点后续节点// 1.如果删除的是头部节点if (index0){first NodeByIndex(index1);return;}// 2.如果不是头部节点NodeT tNode NodeByIndex(index); // 当前节点NodeT prev tNode.prev; // 当前节点的上一个节点NodeT next tNode.next; // 当前节点的下一个节点if (nextnull){// 删除的是尾部节点prev.next null;return;}// 删除的是中间的某个节点// 让该节点的前置节点的下一个节点指向该节点的下一个节点prev.next next;next.prev prev;size--;}Overridepublic void set(int index, T element) {// 索引不能大于等于sizeif (index0 || indexsize){throw new IndexOutOfBoundsException(LinkedList的索引越界);}NodeT tNode NodeByIndex(index); // 当前节点T oldVal tNode.item; // 获取旧的元素tNode.item element; // 把当前节点的元素设置成新的
// System.out.println(oldVal);}Overridepublic T get(int index) {// 索引不能大于等于sizeif (index0 || indexsize){throw new IndexOutOfBoundsException(LinkedList的索引越界);}return NodeByIndex(index).item;}Overridepublic int size() {return size;}/*** 为了实现toString方法*/String str null--;// 通过第一个节点递归调用获得LinkedList的链private String recursion(NodeT first){if (!str.contains(first.item.toString())){str str first.item;}if (first.nextnull){return str --null;}str str -- first.next.item.toString();first first.next;return recursion(first);}// 在每次调用后把str归位private void backStr(){str null--;}Overridepublic String toString() {String recursion recursion(first);backStr();return MyLinkedList{ recursion };}
}
测试类
package com.tianju.book.jpa.myLinkList;import org.hibernate.event.spi.SaveOrUpdateEvent;import java.util.List;public class MyLinkedListTest1 {public static void main(String[] args) {MyLinkedListString list new MyLinkedList();list.add(PET1);list.add(PET2);list.add(PET3);System.out.println(**********);System.out.println(list);list.add(PET4);System.out.println(list);System.out.println(list.size());// System.out.println(list.get(4));
// list.remove(0);
// System.out.println(删除头部节点);
// System.out.println(list);
//
// System.out.println(删除尾部节点);
// list.remove(3-1);
// System.out.println(list);System.out.println(删除中间的节点);list.remove(2);System.out.println(list);System.out.println(进行set);list.set(0, SHI1);System.out.println(list);}
} 总结
1.linkedList的节点当前上一个下一个的思想 2.根据index找node的方法根据index确定从头部还是尾部 3.linkedlist的增删改查的实现本质是改变节点的信息 4.递归方法实现自定义链表的toString方法
