美文网首页
java 数据结构(二)

java 数据结构(二)

作者: 谁吃了我的薯条 | 来源:发表于2017-09-29 11:35 被阅读0次
    又无耻的剽窃了

    LinkedList,从源码底层为一个双链表

    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
        transient int size = 0;
    
        /**
         * Pointer to first node.
         */
        transient Node<E> first;
    
        /**
         * Pointer to last node.
         */
        transient Node<E> last;
        ...
    //  Node<E>  是一个内部类
     private static class Node<E> {
            E item;
            Node<E> next; //指向下一个节点
            Node<E> prev; //指向前一个节点
    
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }
    

    LinkedList同时实现了List接口和Deque接口,继承了AbstractSequentialList 类。也就是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。这样看来,LinkedList简直就是个全能冠军。当你需要使用栈或者队列时,可以考虑使用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类,更遗憾的是,Java里根本没有一个叫做Queue的类(它是个接口名字)。关于栈或队列,现在的首选是ArrayDeque,它有着比LinkedList(当作栈或队列使用时)有着更好的性能。

    同时,若链表为空,其first 及 last 均为null;first为第一个节点,last为最后一个节点;

       /*
        void dataStructureInvariants() {
            assert (size == 0)
                ? (first == null && last == null)
                : (first.prev == null && last.next == null);
        }
        */
    

    显而易见,双链表的结构,决定了它的插入及删除操作均为O(1)操作,但是其查找操作为O(n);(即LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间,而在首段或者末尾删除元素只需要常数时间)

    常见方法
    1、add()方法
    分为两种:
    对尾部进行插入,新建一个节点,即将旧尾部的next指向新建新节点,新节点的prev 指向旧节点;
    对指定位置的插入,先找到下表为index的节点,然后在按照节点插入将新建节点左右指针变更;
    (因为为双向指针,同意可以将其插入到first节点处);

    
      public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
     void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
    
     public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
        void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
            final Node<E> pred = succ.prev;
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
            modCount++;
        }
    
         /*查找操作,采用了小技巧,先判断index在size的偏向那一侧,然
         后决定采用那个方向进行查找索引*/
     Node<E> node(int index) {
            // assert isElementIndex(index);
           
            if (index < (size >> 1)) {     
            //优化了查找效率,将时间复杂度控制在了O(n/2)
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }
    
    

    2、remove()方法
    其实与add()方法类似,也可以分为两种:
    删除指定元素
    删除指定下标
    在寻找被删元素引用的时候remove(Object o)调用的是元素的equals方法,而remove(int index)使用的是下标计数,两种方式都是线性时间复杂度。两个revome()方法都是通过unlink(Node<E> x)方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

     
    public boolean remove(Object o) {
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item)) {
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }
    
      public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
        E unlink(Node<E> x) {
            // assert x != null;
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
    
            if (prev == null) {
                first = next;
            } else {
                prev.next = next;
                x.prev = null;
            }
    
            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }
    
    

    3、set() 和 get() 方法,其实已经包含在了上述两者之中了;

    4、PS,为什么说LinkedList 可以看作一个stack,又可以看作Queue?
    如果是单链表的结构呢?

    相关文章

      网友评论

          本文标题:java 数据结构(二)

          本文链接:https://www.haomeiwen.com/subject/uyobextx.html