一. 自定义LinkedList
LinkedList 位于 java.util 包下， 内部封装的是链接， 用于快速 添加，删除元素，也支持查询元素。
由于是内部封装链表，数据结构需要多看一下。
LinkedList 的源码非常好，建议多读一下。
老蝴蝶简单自定义一个 LinkedList, 实现相应的基础功能。
一.一 自定义 MyLinkedList, 实现 LinkedList 功能
package com.yjl.collection; /** * package: com.yjl.collection * className: MyLinkedList * Description: 请输入相应的描述 * * @author : yuezl * @Date :2020/6/11 11:35 */ public class MyLinkedList<E>{ /*内部定义一个Node. 静态的*/ private static class Node<E>{ /** * @param previous 上一节点 * @param next 下一节点 * @param e 当前元素 * */ private Node<E> previous; private Node<E> next; private E e; public Node(){ } public Node(Node previous,E e,Node next){ this.previous=previous; this.e=e; this.next=next; } } /*需要定义三个属性， 根节点，尾节点，和长度size*/ /** * @param first 根节点 * @param last 尾节点 * @param size 当前长度 * * 如果没有元素的话， first=last=null, * 如果只有一个元素的话， first=last=唯一的那个元素值构成的Node * 如果有两个或者两个以上的话， first指向第一个,last指向最后一个 */ private Node<E> first; private Node<E> last; private int size; /*定义构造方法*/ public MyLinkedList(){ } public MyLinkedList(MyLinkedList<E> mll){ addAll(mll); } /*关于添加的相应操作*/ /** * 添加 到最后 * @param e * @return */ public boolean add(E e){ addLast(e); return true; } /** * 有索引的添加 * @param index * @param e * @return */ public boolean add(int index,E e){ //如果是最后一个，那么就是追加 if(index==size){ addLast(e); }else{ addBefore(e,getNodeByIndex(index)); } return true; } public boolean addAll(MyLinkedList<E> mll){ addAll(size,mll); return true; } public boolean addAll(int index,MyLinkedList<E> mll){ //转换成数组，获取里面的元素。 Object[] obj=mll.toArray(); int length=obj.length; if(length==0){ throw new NullPointerException("传入的集合为空"); } //定义两个对象，一个上一个对象，一个当前对象。 Node<E> pre,local; //说明是后面插入的，或者调用 addll()方法的。 if(index==size){ pre=last; //当前的为空 local=null; }else{ local=getNodeByIndex(index); pre=local.previous; } for(int i=0;i<obj.length;i++){ //构建新对象 Node<E> node=new Node(pre,obj[i],null); //判断一下，是否是开头插入 if(pre==null){ first=node; }else{ //上一个的下一个为node pre.next=node; } //新的pre pre=node; } //判断一下，是否是末尾插入 if(local==null){ last=pre; }else{ pre.next=local; local.previous=pre; } size+=length; return true; } /** * 添加到第一个 * @param e */ public void addFirst(E e){ // 构建Node,记录一下，以前的第一个。 以前的第一个，将会变成新Node 的next Node<E> f=first; Node<E> node=new Node(null,e,f); first=node; //看以前是否有内容，来判断是否有下一个。 if(f==null){ //以前没有值的话， last为现在的node last=node; }else{ //设置 以前的previous 为node， 以前previous为null f.previous=node; } size++; } /** * 添加到最后一个 * @param e */ public void addLast(E e){ //先构建 Node,记录一下，以前的最后一个。 以前的最后一个，将变成新的前。 Node<E> l=last; //新Node Node node=new Node(l,e,null); //最后一个，last 指向新的 node last=node; //判断一下 l, 由此确定一下 first if(l==null){ //根节点为 node. first=node; }else{ //以前的下一个为 last, 以前是null l.next=last; } size++; } /** * 在以前的任意结点上添加元素，不适用末尾添加。 * @param e * @param node */ private void addBefore(E e,Node<E> node){ //获取该节点的上一个节点。 下一个接点，是不变的。 final Node prev=node.previous; //构建新的Node 新结点的上一个结点为prev,下一个接点为当前结点。 Node newNode=new Node(prev,e,node); //将上一个结点变成新结点。 node.previous=newNode; if(prev==null){ first=newNode; }else{ prev.next=newNode; } size++; } /** * 放置元素， 放置在最前面 * @param e */ public void push(E e){ addFirst(e); } /** * 移除元素， 移除第一个。 * @return */ public E pop(){ return unLinkFirst(first); } /** 移除的操作*/ /** * 移除第一个 * @return */ public E remove(){ return removeFirst(); } /** * 移除固定索引的元素 * @param index * @return */ public E remove(int index){ return unLink(getNodeByIndex(index)); } /** * 按照对象移除 * @param obj * @return */ public E remove(Object obj){ int index=indexOf(obj); if(index>=0){ return remove(index); } return null; } /** * 移除第一个 * @return */ public E removeFirst(){ return unLinkFirst(first); } /** * 移除最后一个 * @return */ public E removeLast(){ return unLinkLast(last); } /** * 移除中间的元素 * @param node * @return */ private E unLink(Node<E> node){ //获取上一个，获取下一个。 上一个和下一个，均是有值的。 Node<E> pre=node.previous; Node<E> next=node.next; E element=node.e; node.e=null; //前面为空，说明只有一个元素 if(pre==null){ first=null; }else{ pre.next=next; //当前元素断开 node.previous=null; } //最后一个时 if(next==null){ last=pre; }else{ pre.next=next; node.next=null; } size--; return element; } /** * 移除头部 * @param node * @return */ private E unLinkFirst(Node<E> node){ //获取下一个元素 Node next=node.next; E element=node.e; //GC node.e=null; node.next=null; //first 就指向下一个元素了 first=next; if(next==null){ last=null; }else{ //令下一个元素的上一个元素为null,下一个元素不变 next.previous=null; } size--; return element; } /** * 移除最后一个 * @param node * @return */ private E unLinkLast(Node<E> node){ //获取前面的元素 Node pre=node.previous; E element=node.e; node.previous=null; node.e=null; last=pre; //看是否是第一个 if(pre==null){ first=null; }else{ pre.next=null; } size--; return element; } /*设置和获取*/ /** * 获取长度 * @return */ public int size(){ return size; } /** * 判断是否为空 * @return */ public boolean isEmpty(){ return size==0?true:false; } /** * 是否包含某个对象 * @param obj * @return */ public boolean contains(Object obj){ return indexOf(obj)>=0?true:false; } /** * 索引位置 * @param obj * @return */ public int indexOf(Object obj){ int index=-1; //对象为null if(obj==null){ for(Node<E> node=first;node!=null;){ index++; if(node.e==obj){ return index; } node=node.next; } }else{ for(Node<E> node=first;node!=null;){ index++; if(obj.equals(node.e)){ return index; } node=node.next; } } return -1; } /** * 倒序的索引位置 * @param obj * @return */ public int lastIndexOf(Object obj){ int index=-1; //对象为null if(obj==null){ for(Node<E> node=last;node!=null;){ index++; if(node.e==obj){ return index; } node=node.previous; } }else{ for(Node<E> node=last;node!=null;){ index++; if(obj.equals(node.e)){ return index; } node=node.previous; } } return -1; } /** * 设置值 * @param index * @param e * @return */ public E set(int index,E e){ Node old=getNodeByIndex(index); old.e=e; return (E)old.e; } /** * 获取值 * @param index * @return */ public E get(int index){ Node node=getNodeByIndex(index); return (E)node.e; } /** * 得到头部 * @return */ public E getFirst(){ if(first==null){ return null; } return first.e; } /** * 得到尾部 * @return */ public E getLast(){ if(last==null){ return null; } return last.e; } /** * 根据索引编号获取相应的节点 * @param index * @return */ private Node<E> getNodeByIndex(int index){ //判断一下，当前的index 是在左半部分，还是在右半部分 if(index<=(size>>2)){ Node node=first; for(int i=0;i<index;i++){ node=node.next; } return node; }else{ Node node=last; for(int i=size-1;i>index;i--){ node=last.previous; } return node; } } /** * 清空 */ public void clear(){ //需要将以前的那些链接清空，方便GC 收集 for(Node<E> node=first;node!=null;){ Node<E> next=node.next; node.previous=null; node.e=null; node.next=null; node=next; } first=null; last=null; size=0; // } /** * 转换成数组 * @return */ public Object[] toArray(){ Object[] result=new Object[size]; int i=0; for(Node<E>node=first;node!=null;node=node.next){ result[i++]=node.e; } return result; } /** * 打印输出 * @return */ public String toString(){ if(size==0){ return "[]"; } StringBuilder sb=new StringBuilder(); sb.append("["); for(Node<E> node=first;node!=null;node=node.next){ String temp= node.e.toString(); sb.append(temp+","); } sb.replace(sb.length()-1,sb.length(),"]"); return sb.toString(); } }
一.二 测试自定义 MyLinkedList
package com.yjl.collection; /** * package: com.yjl.collection * className: MyLinkedListTest * Description: 请输入相应的描述 * * @author : yuezl * @Date :2020/6/11 15:18 */ public class MyLinkedListTest { public static void main(String[] args) { MyLinkedList<Integer> mal = new MyLinkedList<Integer>(); System.out.println("长度:" + mal.size() + ",是否为空:" + mal.isEmpty()); //添加元素 mal.add(3); mal.add(4); //索引时添加 mal.add(0, 1); mal.addFirst(0); mal.addLast(100); //打印 System.out.println("mal:" + mal.toString()); //集合构建 MyLinkedList<Integer> mal2 = new MyLinkedList<Integer>(mal); System.out.println("mal2:" + mal2.toString()); //添加所有 mal2.addAll(mal); System.out.println("新的mal2:" + mal2.toString()); //获取值 Integer val = mal2.get(3); System.out.println("输出值为:" + val); //索引长度构造 MyLinkedList<Integer> mal3=new MyLinkedList<Integer>(); mal3.add(1); mal3.add(2); System.out.println("是否包含2:"+mal3.contains(2)); System.out.println("长度1:"+mal3.toArray().length); //清除 mal3.clear(); System.out.println("长度:"+mal3.size()+",是否为空:"+mal3.isEmpty()); } }
控制台打印输出:
谢谢您的观看，如果喜欢，请关注我，再次感谢 !!!
