手撕LinkedList底层源码

阳光穿透心脏的1/2处 2024-04-20 11:19 85阅读 0赞

## 手撕LinkedList底层源码 ##

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
        
        //操作数 -- 记录添加、删除数据的次数
        protected transient int modCount = 0;
    }
    public abstract class AbstractSequentialList<E> extends AbstractList<E> {
        
    }
    public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>{
        
        //元素个数
        transient int size = 0;//0
        //第一个节点
        transient Node<E> first;//null
        //最后一个节点
        transient Node<E> last;//null
       
        //无参构造
        public LinkedList() {
        
        }
        
        //节点类
        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;
            }
        }
        
        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++;
        }
    }

//创建LinkedList对象
    LinkedList<String> list = new LinkedList<>();
    
    //添加元素
    list.add("大乔");
    list.add("小乔");
    list.add("孙尚香");

> 1.  LinkedList底层数据结构是什么？
> 
> 双向链表
> 
> 1.  ArrayList vs LinkedList
> 
> 应用上的区别：
> 
> LinkedList比ArrayList多队列模式和栈模式
> 
> 数据结构的区别：
> 
> ArrayList：一维数组
> 
> LinkedList：双向链表
> 
> 效率的区别：
> 
> 添加 – 扩容的情况下：LinkedList快
> 
> 添加 – 不扩容的情况下：ArrayList快
> 
> 删除：LinkedList快
> 
> 查询：ArrayList快
> 
> 修改：ArrayList快
> 
> 经验：平时我们使用ArrayList更多，因为ArrayList查询快，而项目中查询业务是最多的