美文网首页
LinkdeList源码笔记

LinkdeList源码笔记

作者: 杨旭_ | 来源:发表于2020-11-24 16:46 被阅读0次

    惯例,笑话开头。


    哈哈哈
    阅读本文你可以掌握,LinkedList 相关知识点和细节。
    目录
    数据结构基础
    LinkedList源码解析
    面试知识

    数据结构基础

    链表的特点

    1,链表查询数据,需要遍历整个链表,即便是做了优化,判断当前index,确定从前边遍历或者从后边遍历,时间复杂度仍是O(n)。
    2,链表插入和删除的,首先需要找到当前插入的点,也需要遍历链表,然后把节点指针相连,所以时间复杂度也是O(n);但是为什么都说链表更适合插入和删除呢,因为链表查找的时间要比移动数据快很多。
    3 ,内存利用率高,不会浪费内存(数组需要提前分配内存,链表则不需要,而且没有大小限制,内存也可以不连续)

    单链表和双链表

    单链表
    缺点:每个节点只有一个next指针,只能一种遍历方式,
    优点:单链表存储一个节点,就比较节省内存,当节点N无线大的时候,节省的内存还是挺可观的。
    双链表
    优点:每个节点有两个指针,可以从前边或者从后边遍历,利用二分查找,所以理论上双链表遍历效率是比单链表快的,
    缺点:但是相对单链表来说占用内存相对较大

    LinkedList源码解析

    Node 节点代码
        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;
            }
        }
    
    成员属性
    属性
    size 链表长度
    first 头节点
    last 尾节点
    modCount failFast机制
     transient int size = 0;
    
        /**
         * Pointer to first node.
         * Invariant: (first == null && last == null) ||
         *            (first.prev == null && first.item != null)
         */
        transient Node<E> first;
    
        /**
         * Pointer to last node.
         * Invariant: (first == null && last == null) ||
         *            (last.next == null && last.item != null)
         */
        transient Node<E> last;
    
    
    为什么定义两个节点?

    如果只有一个头节点,添加数据就需要从头结点遍历拿到最后一个节点,这样时间复杂度O(n),数据量庞大的时候效果非常明显,定义一个last节点,添加单个数据的时间复杂度就变成了O(1).

     void linkBefore(E e) {
    
            Node newNode = new Node(e, null);
            Node next = first;
    
            if (next ==null){
                first =newNode;
            }else{
                //遍历找到最后一个节点
                for (int i = 0; i < size; i++){
                    next = next.next;
                }
                next.next =newNode;
            }
      size++;
        }
    这种写法 每次添加数据的时候需要找到最后一个节点,时间复杂度O(n);
    
        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++;
        }
    定义一个last节点,添加就变成了O(1)级别
    
    构造方法
        public LinkedList() {
        }
    
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
    

    第二种,把当前数据转换成数组,然后遍历数组,创建Node节点添加到链表中。

    为什么使用双链表?

    单链表遍历只能一个方向遍历,时间复杂度O(n),使用双链表可以两个方向遍历,时间复杂度O(n/2),当N足够大其实也是O(n),但是这样实际减少了遍历消耗。

     */
        Node<E> node(int index) {
            // assert isElementIndex(index);
    
            if (index < (size >> 1)) {
                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;
            }
        }
    

    面试知识

    LinkdeList 面试大部分是对比ArrayList 来的。
    1,为什么实现不是单链表
    答 :空间换时间,消耗了一定空间,遍历的时候速度相对来说加快一倍。
    2,为什么定义两个节点?
    答:优化了添加的时间复杂度,一个节点需要遍历找到最后的节点,定义一个尾节点,使得添加时间复杂度从O(n)降低为O(1);
    3,什么时候使用Arraylist 什么时候使用lindekList?
    答:如果需要频繁移除或者中间插入这种,arraylist都需要调用arraycopy比较消耗性能,这种时候需要考虑linkedlist,如果只是遍历就用arraylist 查询级别O(1);linkedlist查询虽然做了优化,(二分查找) 但是数据足够大还是o(n)级别。

    相关文章

      网友评论

          本文标题:LinkdeList源码笔记

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