|
LinkedList作为ArrayList的老弟，也继承了父亲List的特点:有序，允许存null值，允许重复值。和大哥ArrayList相比，LinkedList底层靠链表存储元素，不用考虑数组扩容，删除插入元素所带来的资源消耗的问题。但在访问元素上就没有数组直接通过索引这么方便了，大家根据不同的业务场景来选择不同的集合。那什么又是链表呢？ 没错，这就是链表!!! 同事之间靠自己的手抓住下一个同事的肩膀来构成关系。跑到天涯海角，都能找到你。链表中的每一个节点靠记录上一个/下一个节点位于内存中的地址来维护节点之间的关系，节点在内存中的位置也可以是不固定，分散的，这点和数组不同。 插入节点当有新的同事插入队列时，需要从第一个同事开始一直向下找到想要插队的位置，然后自己的手搭在右边同事的肩上，再将左边同事的手搭在自己肩膀上，就入队成功了。有同事出队也一样。 比如有同事插队到第四个位置去： 插入删除元素，需要从第一个元素开始一直向下找到该位置上的节点再做操作。和数组比较起来，数组是牺牲时间和空间，而链表是牺牲时间，最坏从第一个找到最后一个时间复杂度O(n)。对于链表节点会多使用内存的情况，个人认为单向链表需要多使用一块内存来记录下一个节点的位置，而数组本身也是存储记录对象的内存地址的，个人觉得两者相比并没有谁更节约。欢迎大家提出自己的看法。 双向链表删除和插入元素都需要从第一个开始向下寻找，当元素越来越多时，性能肯定会越来越不好。上面新同事插队到以四个位置，如果从最后一个同事开始向前找位置，会快跟多。问题的根本在于，每个节点只记录下一个节点的位置。节点只能找到自己后面的节点，找不到自己前面的节点。所以前辈们又发明了双向链表:节点之间紧紧相扣。 同时每个节点还需要一块空间来记录前面节点的位置。LinkedList底层就是用双向链表来实现的。 插入删除元素时，会根据索引的位置，优先选择是从头开始还是从尾开始找。最坏次数，当前链表大小的一半，当然这是牺牲些许内存所换来的。 当需要插入元素时，只需要： 2.插入节点的前驱为该位置节点的前驱，插入节点的后驱为该位置节点 3.该位置的前驱节点的next指向插入节点 4.该位置节点的pre指向插入节点
删除元素也一样： 1.找到该位置上的节点
2.将该位置节点的前驱节点的next，指向该位置节点的后驱节点
3.将该位置节点的后驱节点的pre，指向该位置节点的前驱节点
END |
|
|
