LinkedList基本实现Java版

迈不过友情╰ 2022-09-30 15:51 278阅读 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+",");  
        \}