您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

集合源码学习-LinkedList

特点:

底层是双向链表,在增加或删除元素时,只需要断开连接点两边的引用即可,所以增删快,但是查询需要遍历,所以查询慢。LinkedList比ArrayList更占用内存,它维护了两个引用。

源码:

add()

//示例
LinkedList l = new LinkedList();
l.add("3");
l.add("5");
//新增元素
public boolean add(E e) {
    //第一次add e=3
    linkLast(e);
    return true;
}
void linkLast(E e) {
    //LinkedList是新建的,此时last为null,l为null
    final Node<E> l = last;
    //此时l为null,则值为 null----e----null
    //链表操作 prev(前指针)=null element(节点元素)=3 next(后指针)=null
   // Node(Node<E> prev, E element, Node<E> next) {
  //          this.item = element;    ------item=3
  //          this.next = next;		  ------next=null
  //          this.prev = prev;		  ------prev=null	
  //      }
    //此时 newNode = e
    final Node<E> newNode = new Node<>(l, e, null);
    //last =  e
    last = newNode;
    //如果l为null
    if (l == null) {
       // 此时,e是第一个添加的元素,first指针指向该点
        first = newNode; 
    } else {
        l.next = newNode;
    }
    size++;
    modCount++;
    //此时,第一个元素添加完毕。
}
public boolean add(E e) {
    //此时e=5
    linkLast(e);
    return true;
}
void linkLast(E e) {
    //e = 5
    //此时链表中有值,last不为空,得到原链表
    final Node<E> l = last;
  	//此时newNode 链表当前节点值为e=5
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    // 此时l不为null
    if (l == null) {
        first = newNode; 
    } else {
        //l的后指针指向newNode当前节点
        l.next = newNode;
    }
    size++;
    modCount++;
}

remove()/remove(index)

两者的区别是如果没有传参,则先判断第一个元素是否存在,不存在抛异常,存在则进行删除;如果有传参,则先验证传入参数的下标是否越界或者为负数,通过验证后对节点的链接进行断开删除。

public E remove() {
    return removeFirst();
}
public E removeFirst() {
    //判断第一个元素是否为空,为空则抛出异常
    final Node<E> f = first;
    if (f == null) {
        throw new NoSuchElementException();
    }
    return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    //获取f的节点元素
    final E element = f.item;
    //获取f的下一个元素
    final Node<E> next = f.next;
    //把f节点元素置为null
    f.item = null;
    //把f节点下一个元素置为null,主要为了垃圾回收
    f.next = null; // help GC
    //把下一个点的值给第一个节点
    first = next;
    //如果下一个元素为null,则链表为null
    if (next == null) {
        last = null;
    } else {
        如果不为null,则将上一个元素置为null
        next.prev = null;
    }
    size--;
    modCount++;
    return element;
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进