【java数据结构与算法学习】LinkedList的实现

水深无声 2022-05-31 13:41 178阅读 0赞

LinkedList是一个双向链表，是链表的一种特殊情况。

链表有单链表、静态链表、双向链表、循环链表。

单链表节点有一个数据域，一个指针域，其中指针域指向下一个节点。

静态链表底层是一个数组和游标组成。数组中的第一个元素为空，第一个游标是数组中第一个为空的元素的下标；数组中最后一个元素也为空，最后一个游标是数组中第一个不为空元素的下标；游标为0的元素是静态链表最后一个元素。根据最后一个游标找到静态链表中的第一个元素，根据第一个元素的游标找到第二个元素，以此类推，如下图。

![20180226225802723][]

双向链表节点有一个数据域，两个指针域。其中一个指针域（prev）指向节点前一个节点，另一个节点（next）指向节点后一个节点。

循环链表尾节点指向头节点，构成一个圈。

好了，接下来我们实现一个自己的LinkedList。

import java.util.ConcurrentModificationException;
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    public class MyLinkedList<AnyType> implements Iterable<AnyType> {
    
        //链表大小
        private int theSize;
        //链表更改次数
        private int modCount = 0;
        //头节点
        private Node<AnyType> beginMarker;
        //结束节点
        private Node<AnyType> endMarker;
    
        //链表节点
        private static class Node<AnyType>{
            public AnyType data;
            public Node prev;
            public Node next;
    
            public Node(AnyType d, Node<AnyType> p, Node<AnyType> n){
                data = d;
                prev = p;
                next = n;
            }
        }
    
        public MyLinkedList(){
            doClear();
        }
        public void clear(){
            doClear();
        }
        //创建一个空链表
        public void doClear(){
            // beginMarker --> endMarker
            beginMarker = new Node<>(null, null, null);
            endMarker = new Node<>(null, beginMarker, null);
            beginMarker.next = endMarker;
    
            theSize = 0;
            modCount++;
        }
        //返回链表大小
        public int size(){
            return theSize;
        }
        //判断链表是否为空
        public boolean isEmpty(){
            return size() == 0;
        }
        //添加元素(相当于在最后的位置添加元素)
        public boolean add(AnyType x){
            add(size(),x);
            return true;
        }
        //在指定位置添加元素
        public void add(int index, AnyType x){
            /*
                调用添加元素的方法的时候index等于size()，
                getNode(index, 0, size())返回的是尾节点，在末尾添加元素
            */
            addBefore(getNode(index, 0, size()), x);
        }
        //获得某位置的元素
        public AnyType get(int index){
    
            return getNode(index).data;
        }
        //更新元素
        public AnyType set(int index, AnyType newVal){
            Node<AnyType> p = getNode(index);
            AnyType oldVal = p.data;
            p.data = newVal;
            return oldVal;
        }
        //删除元素
        public AnyType remove(int index){
            return remove(getNode(index));
        }
        //在某节点之前添加节点
        private void addBefore(Node<AnyType> p, AnyType x){
            Node<AnyType> newNode = new Node<>(x, p.prev, p);
            p.prev.next = newNode;
            p.prev = newNode;
            theSize++;
            modCount++;
        }
    
        private AnyType remove(Node<AnyType> p){
            p.prev.next = p.next;
            p.next.prev = p.prev;
            theSize--;
            modCount++;
            return p.data;
        }
        //在查询、更新、删除元素的时候调用，元素位置范围在 0到size()-1 之间
        public Node<AnyType> getNode(int index){
            return getNode(index,0,size()-1);
        }
        //得到具体位置的节点
        public Node<AnyType> getNode(int index, int lower, int upper){
            Node<AnyType> p;
            //判断范围
            if (index < lower || index > upper){
                throw new IndexOutOfBoundsException();
            }
            /*
                如果要找的位置小于链表长度的一半，
                那么我们从头节点开始查找，否则我们从尾节点查找
             */
            if (index < size()/2){
                p = beginMarker;
                //从头节点开始移动几次就是第几个元素
                for (int i = 0; i<index; i++){
                    p = p.next;
                }
            }else {
                p = endMarker;
                //从尾节点开始到指定位置结束
                for (int i = size(); i > index; i--) {
                    p = p.prev;
                }
            }
            return p;
        }
        @Override
        public Iterator<AnyType> iterator() {
            return new LinkedListIterator();
        }
        private class LinkedListIterator implements Iterator<AnyType>{
            private Node<AnyType> current = beginMarker.next;
            private int expectedModCount = modCount;
            //当标记为true的时候，才可以删除（先执行next，才能执行删除）
            private boolean okToRemove = false;
    
            private Node<AnyType> p = beginMarker;
            @Override
            public boolean hasNext() {
                return current != beginMarker;
            }
    
            @Override
            public AnyType next() {
                if (modCount != expectedModCount){
                    throw new ConcurrentModificationException();
                }
                if (!hasNext()){
                    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();
                }
                /*
                  这里必须写current.prev，删除当前元素之前的元素，
                  因为执行删除之前必须先执行一次next方法
                 */
                MyLinkedList.this.remove(current.prev);
                expectedModCount++;
                okToRemove = false;
            }
        }
    }

[20180226225802723]: /images/20220531/773ef8d16186416faaed87503371415e.png