LinkedList基本实现Java版 迈不过友情╰ 2022-09-30 15:51 214阅读 0赞 public class MyLinkedList<AnyType> implements Iterable<AnyType>\{ private static class Node<AnyType>\{ public AnyType data; public Node<AnyType> prex; public Node<AnyType> next; public Node(AnyType d,Node<AnyType> p,Node<AnyType> n)\{ data=d; prex=p; next=n; \} \} private int theSize;//元素个数 private int modCount=0;//操作次数 private Node<AnyType> beginMarker;//开始指针,指向第一个元素的前一个位置 private Node<AnyType> endMarker;//末尾指针,指向最后一个元素的后一个位置 public MyLinkedList()\{ doClear(); \} public void clear()\{ doClear(); \} public void doClear()\{ beginMarker=new Node<AnyType>(null,null,null); endMarker=new Node<AnyType>(null,beginMarker,null); beginMarker.next=endMarker; theSize=0; modCount++; \} public int size()\{ return theSize; \} public boolean isEmpty()\{ return size()==0; \} //在p之前添加一个元素,内部调用,为public函数服务 private void addBefore(Node<AnyType> p,AnyType x)\{ Node<AnyType> newNode=new Node<>(x,p.prex,p); newNode.prex.next=newNode; p.prex=newNode; theSize++; modCount++; \} //移除一个元素 private AnyType remove(Node<AnyType> p)\{ p.next.prex=p.prex; p.prex.next=p.next; theSize--; modCount++; return p.data; \} //查找指定位置的元素,之所以添加lower和upper是为了避免使用thesize,为了避免不小心修改thesize private Node<AnyType> getNode(int idx,int lower,int upper)\{ Node<AnyType> p; if(idx<lower||idx>upper)\{ throw new IndexOutOfBoundsException(); \} if(idx<size()/2)\{ p=beginMarker.next; for(int i=0;i<idx;i++)\{ p=p.next; \} \} else \{ p=endMarker; for(int i=size();i>idx;i--)\{ p=p.prex; \} \} return p; \} //得到指定位置的元素 private Node<AnyType> getNode(int idx)\{ return getNode(idx,0,size()-1); \} //在末尾添加一个元素 public boolean add(AnyType x)\{ add(size(),x); return true; \} //在指定位置添加一个元素 public void add(int idx,AnyType x)\{ addBefore(getNode(idx,0,size()),x); \} public AnyType get(int idx)\{ return getNode(idx).data; \} //修改指定位置的值 public AnyType set(int idx,AnyType newVal)\{ Node<AnyType> p=getNode(idx); AnyType oldVal=p.data; p.data=newVal; return oldVal; \} public AnyType remove(int idx)\{ return remove(getNode(idx)); \} //添加迭代器 @Override public Iterator<AnyType> iterator() \{ // TODO Auto-generated method stub return new LinkedListIterator(); \} private class LinkedListIterator implements Iterator<AnyType>\{ private Node<AnyType> current=beginMarker.next;//得到第一个元素的指针 private int expectedModCount=modCount; private boolean okToRemove=false;//用来判断当前是否可以进行删除,避免二次删除, //发生不可预知的错误 @Override public boolean hasNext() \{ // TODO Auto-generated method stub return current!=endMarker; \} @Override public AnyType next() \{ // TODO Auto-generated method stub if(modCount!=expectedModCount) throw new ConcurrentModificationException(); if(!hasNext())\{//如果当前已经在尾部,那么不可进行next()操作 throw new NoSuchElementException(); \} AnyType nextItem=current.data; current=current.next; okToRemove=true; return nextItem; \} public void remove()\{ if(modCount!=expectedModCount)\{ throw new ConcurrentModificationException(); \} if(!okToRemove)\{//如果已经执行过删除,那么本次删除无效 throw new IllegalStateException(); \}//调用MyLinkedList的删除函数,因为当前current已经向后移动过了,所以需要前移 MyLinkedList.this.remove(current.prex); expectedModCount++; okToRemove=false; \} \} //测试 MyLinkedList<Integer> a=new MyLinkedList<>(); a.add(1); a.add(2); a.add(3); a.add(1,4); for(Integer s:a)\{//测试迭代器 System.out.print(s+","); \} System.out.println(); System.out.println(a.size()+","+a.get(1)); a.remove(1);//删除 Iterator<Integer> t=a.iterator(); while(t.hasNext())\{ if(t.next()==1) t.remove();//用迭代器删除 \} for(Integer s:a)\{//测试迭代器 System.out.print(s+","); \}
还没有评论,来说两句吧...