1. 首页
  2. Java基础

050-五十、Java之手写LinkedList改造

改造Iterator


/** * 返回在此列表中的元素上进行迭代的迭代器(按适当顺序)。 * 此实现仅返回列表的一个列表迭代器。 * @return */ public Iterator<T> iterator() { /** * 这里我们回顾一下匿名内部类 */ return new Iterator<T>() { /** * 第一次记录first节点 */ private Node<T> node = first; @Override public boolean hasNext() { return !Objects.isNull(node); } /** * 每次迭代一次之后就将节点转移到next节点上 * @return */ @Override public T next() { T t = node.data; //转移到下一个节点 node = node.next; return t; } }; } 这样效率稍微会好一点。 MyLinkedList<String> list = new MyLinkedList<>(); list.add("zhangsan1"); list.add("zhangsan2"); list.add("zhangsan3"); list.add("zhangsan4"); Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + "\t"); } 结果:zhangsan1 zhangsan2 zhangsan3 zhangsan4

MyLinkedList源码


import java.util.Iterator; import java.util.Objects; /** * @author dcc */ public class MyLinkedList<T> { /** * 链表元素的长度 */ private int size; /** * 链表的第一个节点 */ private Node<T> first; /** * 链表的最后一个节点 */ private Node<T> last; /** *向链表末尾添加一个新节点,该节点中的数据是参数t指定的对象 * @param t * @return */ public boolean add(T t){ /** * 每次在添加的时候就创建一个节点 */ final Node<T> node = new Node<>(t); /** * 当第一次添加的时候就将节点赋值给first,表示第一个节点的引用 */ if(this.first == null){ //第一个节点 this.first = node; //第一次第一个节点和最后一个节点相同 this.last = this.first; }else { /** * 因为每次add的时候都会add到最后一个节点上, * 那么这个时候last需要赋值给previousNode * 这个时候previousNode节点就变成倒数第二个节点了 * 也就是说新的node节点变成last节点了 * 并且previousNode变成了last节点的上一个节点了 * 这样就证明LinkedList添加操作效率就比ArrayList操作效率高多了。 */ Node<T> previousNode = this.last; this.last = node; this.last.prev = previousNode; previousNode.next = this.last; } this.size++;//表示元素的总个数 return true; } /** * 得到指定位置的节点, * @param index * @return */ public T get(int index) { //下标越界提醒 arrayIndexOutOfBoundsException(index); /** * 以上条件都不满足,那么就开始递归查询 * 为什么大家都说LinkedList的get效率低呢? * 主要是因为get的时候需要逐个遍历来匹配获取数据,这样效率就低很多 了。 * ArrayList是直接操作数组的,get也是直接在数组里面根据索引获取的。 * * 因为linkedList是没有index属性的,所以需要一个临时变量,那么直接传入一个0进入方法即可 * 因为需要逐个递归需要和索引比配上才能找到对应的元素 */ /** * 根据index获取对应的节点 * 这里改造 */ Node<T> node = this.first.get(index,0); return node.data; } /** * 向链表表头添加一个新节点,该节点中的数据是参数element指定的对象 * @param t */ public void addFirist(T t) { Node<T> newNode = new Node<>(t); /** * 第一步需要判断first是否为null,为null就添加 * 在这里需要将oldFirst节点也就是老的first节点,添加到新的first节点上 */ if (this.first != null) { /** * 首先将first的引用保存在一个临时变量oldFirst中 */ Node oldFirst = this.first; /** * 将这个节点存放在first节点上 */ this.first = newNode; this.first.next = oldFirst; /** * 然后将first的引用赋值给oldFirst.prev就好了 */ oldFirst.prev = this.first; if (this.last == null) { this.last = this.first; } } else {//表示为第一次添加 //第一个节点 this.first = newNode; //第一次第一个节点和最后一个节点相同 this.last = this.first; } this.size++; } /** * 向链表指定位置添加一个新节点,该节点中的数据是参数element指定的对象 * @param index * @param t */ public void add(int index,T t) { //下标越界提醒 arrayIndexOutOfBoundsException(index); /** * 1、获取要插入的节点和节点位置。 */ Node<T> oldNode = first.get(index,0); /** * 每次在添加的时候就创建一个节点 */ final Node<T> newNode = new Node<>(t); /** * 如果oldNode.prev为null就表示为first节点 * 反过来就是不等于null的话那么就需要将新节点(newNode.prev)的引用值等于老节点oldNode.prev * =oldNode.prev */ if (oldNode.prev != null) { newNode.prev = oldNode.prev; //并且需要将newNode节点的上级(prev)节点的next值等于newNode newNode.prev.next = newNode; } //然后改变oldNode.prev=newNode oldNode.prev = newNode; //将oldNode节点引用存放到新插入的节点next下 newNode.next = oldNode; //元素总量增加1 this.size++; } /** * 向链表表尾添加一个新节点,该节点中的数据是参数 t 指定的对象 * @param t */ public void addLast(T t) { /** * 这个就简单了,外部类直接就有最有一个节点的引用,直接互换就可以了。 */ Node<T> oldLast = this.last; /** * 每次在添加的时候就创建一个节点 */ final Node<T> newNode = new Node<>(t); //直接互换位置即可 this.last = newNode; this.last.prev = oldLast; oldLast.next = this.last; this.size++; } /** * 删除第一个节点并返回这个节点中的对象 * @return */ public T removeFirst() { /** * 如果first直为空,表示没有数据可删除,直接返回null */ if (this.first == null) { return null; } Node<T> oldFirst = this.first; /** * 直接将第二个节点替换成first节点 * 然后将first节点的prev值设置为null就好了 * 不过首先需要判断一下first.next是否为null * 如果为null就表示只有一个元素 */ if (this.first.next != null) { this.first = this.first.next; this.first.prev = null; } this.size--; return oldFirst.data; } /** * 删除最后一个节点并返回这个节点中的对象 * @return */ public T removeLast() { /** * 如果last直为null,表示没有数据可删除,直接返回null */ if (this.last == null) { return null; } Node<T> oldLast = this.last; /** * 直接将倒数第二个节点替换成last节点 * 然后将last节点的next值设置为null就好了 * 首先也的判断一下last的上一个节点是否为null * 如果是那么就表示只有数据 */ this.last = this.last.prev; this.last.next = null; this.size--; return oldLast.data; } /** * 删除指定位置的节点 * @param index * @return */ public T remove(int index) { //下标越界提醒 arrayIndexOutOfBoundsException(index); /** * 获取要删除的节点保存到临时变量中 */ Node<T> removeNode = this.first.get(index,0); /** * 删除中间节点 * 如果节点prev不为null表示不是first节点 * 如果节点next不为null表示不是last节点 * 如果找到了直接互换perv和next即可 */ if (removeNode.prev != null && removeNode.next != null) { removeNode.prev.next = removeNode.next; removeNode.next.prev = removeNode.prev; } /** * 删除first节点 * 表示为first节点 * 直接将第二个节点移位到first节点 * 并且将first.prev=null即可 */ else if (removeNode.prev == null && removeNode.next != null) { this.first = removeNode.next; this.first.prev = null; } /** * 删除last节点 * 直接将倒数第二个节点next=null即可 */ else if (removeNode.prev != null) { this.last = removeNode.prev; this.last.next = null; } this.size--; return removeNode.data; } /** * 获取第一个节点 * @return */ public T getFirst() { /** * 只要first值不为null就直接返回了 */ if (Objects.isNull(this.first)) { throw new NullPointerException("空指针异常,因为容器里还没有任何元素"); } return this.first.data; } /** * 得到链表最后一个节点的对象 * @return */ public T getLast() { /** * 只要last值不为null就直接返回了 */ if (Objects.isNull(this.last)) { throw new NullPointerException("空指针异常,因为容器里还没有任何元素"); } return this.last.data; } /** * 返回节点对象t在链表中首次出现的位置,如果链表中无此节点的对象则返回-1 * @param t * @return */ public int indexOf(T t) { /** * 首先判断first==null。如果为null那么表示没有元素 * 在判断first==t。如果为t直接返回 */ if (Objects.isNull(this.first)) { return -1; } else { /** * 如果链表中有数据就开始递归匹配 */ return this.first.index(t,0); } } /** * 返回节点对象t在链表中最后出现的位置,如果链表中无此节点的对象则返回-1 * @param t * @return */ public int lastIndexOf(T t) { /** * 这个时候只需要从后往前面找了 * last就是最后一个元素,size-1就是最后一个元素的索引了 * 这样就比较好找多了 */ if (Objects.isNull(this.last)) { return -1; } return this.last.lastIndexOf(t,--this.size); } /** * 将当前链表index位置节点中的对象替换成参数t指定的对象,返回被替换对象 * @param index * @param t * @return */ public T set(int index,T t) { /** * 获取需要替换的node节点,然后直接替换节点的data即可 */ Node<T> node = this.first.get(index,0); //保存被替换的值 T temp = node.data; //替换新的值 node.data = t; return temp; } /** * 判断链表节点对象中是否含有t * @param t * @return */ public boolean contains(T t) { return this.indexOf(t) != -1; } /** * 下标越界异常 * @param index */ private void arrayIndexOutOfBoundsException(int index){ /** * size==0表示链表中没有数据,直接抛出异常 * index>=size或者index<0,表示index索引已经越界,直接抛出异常 */ if (size == 0 || index >= size || index < 0) { throw new ArrayIndexOutOfBoundsException("下标越界!!!"); } } /** * 获取数组长度 * @return */ public int size(){ return this.size; } /** * 返回在此列表中的元素上进行迭代的迭代器(按适当顺序)。 * 此实现仅返回列表的一个列表迭代器。 * @return */ public Iterator<T> iterator() { /** * 这里我们回顾一下匿名内部类 */ return new Iterator<T>() { /** * 第一次记录first节点 */ private Node<T> node = first; @Override public boolean hasNext() { return !Objects.isNull(node); } /** * 每次迭代一次之后就将节点转移到next节点上 * @return */ @Override public T next() { T t = node.data; //转移到下一个节点 node = node.next; return t; } }; } /** * 这个内部类就是每次添加的节点 * @param */ private class Node<T>{ /** * 要添加的数据 */ private T data; /** * 下个节点的引用 */ private Node<T> next; /** * 上一个节点引用 */ private Node<T> prev; /** * 每次构造的时候index加1 * @param t */ private Node(T t) { this.data = t; } /** * 获取index索引的节点 * @param index * @return */ private Node<T> get(int index,int tempIndex) { /** * 匹配就直接返回了 */ if (index == tempIndex) { return this; } /** * 如果传入索引和临时索引不匹配将递归到下一个节点在进行匹配 * 以此类推 */ return this.next.get(index,++tempIndex); } /** * 查询 * @param t * @param index * @return */ private int index(T t, int index) { /** * 如果值相当就直接返回 */ if (this.data == t) { return index; } /** * 当递归前判断一下this.next==null,如果为null就不需要在递归了 * 表示没有该元素,直接返回-1 */ else if(Objects.isNull(this.next)) { return -1; } else { return this.next.index(t,++index); } } /** * 递归链表上节点方式查找 * @param t * @param index * @return */ private int lastIndexOf(T t, int index) { if (this.data == t) { return index; } /** * 表示没有上个节点了,就是没有元素了直接返回-1 */ else if (Objects.isNull(this.prev) || index - 1 < 0) { return -1; } /** * 递归继续向上查找 */ else { return this.prev.lastIndexOf(t, --index); } } } }

写完了如果写得有什么问题,希望读者能够给小编留言,也可以点击[此处扫下面二维码关注微信公众号](https://www.ycbbs.vip/?p=28 "此处扫下面二维码关注微信公众号")

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
  4. JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

    本文著作权归作者所有,如若转载,请注明出处

    转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

    标题:050-五十、Java之手写LinkedList改造

    链接:https://www.javajike.com/article/1357.html

« 051-五十一、Java之HashMap详解
049-四十九、Java之手写LinkedList(下)»

相关推荐

QR code