LinkedList

简介: LinkedList

「这是我参与11月更文挑战的第4天,活动详情查看:2021最后一次更文挑战」

LinkedList简介
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行队列操作。 LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。 LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。 LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。 LinkedList 是非同步的。

数据结构

源码解析
方法字段
public class LinkedList

extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

{

//元素个数
transient int size = 0;

/**
 * 指向第一个节点
 * 
 */
transient Node<E> first;

/**
 * 指向最后一个节点
 */
transient Node<E> last;
.
.
.
.
}

构造函数

/**
 * 空的构造函数
 */
public LinkedList() {
}

/**
 * 包含一个数组的构造函数,链表中的顺序按照集合中的元素顺序进行插入
 *
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);//这里调用了addAll(),就是插入所有元素
}

addAll(int index, Collection c)
插入给定集合的元素,从指定的index开始插入

public boolean addAll(int index, Collection<? extends E> c) {

    checkPositionIndex(index);

    Object[] a = c.toArray();//为什么要将集合转为数组?????
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;//前驱和后继引用
    if (index == size) {//如果插入的位置刚好在最后位置
        succ = null;//后继用用置位空
        pred = last;//前驱为last所引用的尾结点
    } else {
        succ = node(index);//寻找插入的节点位置
        pred = succ.prev;//保存该节点的前驱
    }

    for (Object o : a) {//循环插入每个节点
        @SuppressWarnings("unchecked") E e = (E) o;//向下转型
        Node<E> newNode = new Node<>(pred, e, null);//生成一个新节点
        if (pred == null)//前驱为空,表示在第一个位置插入
            first = newNode;
        else//否则在index前面插入新节点
            pred.next = newNode;
        pred = newNode;//前驱为新节点
    }

    if (succ == null) {//后继为空
        last = pred;//在末尾插入
    } else {
        pred.next = succ;//否则链接最后的节点
        succ.prev = pred;
    }

    size += numNew;//节点个数增加
    modCount++;//结构性修改
    return true;
}

linkFirst(E e)
在头部插入一个新节点

private void linkFirst(E e) {
    final Node<E> f = first;//1、创建一个引用
    final Node<E> newNode = new Node<>(null, e, f);//2、创建新节点,它的下一个节点为当前的头结点
    first = newNode;//3、头引用指向新节点
    if (f == null)//如果没有头结点,只有尾结点
        last = newNode;//新节点为尾结点
    else
        f.prev = newNode;//4、否则之前的头结点的前引用指向新节点
    size++;
    modCount++;
}

linkLast(E e)
在尾部插入一个新节点,过程与在头部插入类似

void linkLast(E e) {

    final Node<E> l = last;//创建一个指向尾部的指针
    final Node<E> newNode = new Node<>(l, e, null);//创建新节点,新节点的前一个节点为当前的尾结点
    last = newNode;//last引用指向新节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;//当前尾结点的前引用指向新的尾结点
    size++;
    modCount++;
}

linkBefore(E e, Node succ)
在某个节点之前插入一个新节点

void linkBefore(E e, Node 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++;
}

indexOf(Object o)
从前向后查找,返回“值为对象(o)的节点对应的索引, 不存在就返回-1

public int indexOf(Object o) {
    int index = 0;
    if (o==null) {
        for (Entry e = header.next; e != header; e = e.next) {
            if (e.element==null)
                return index;
            index++;
        }
    } else {
        for (Entry e = header.next; e != header; e = e.next) {
            if (o.equals(e.element))
                return index;
            index++;
        }
    }
    return -1;
}

lastIndexOf(Object o)
从后向前查找,返回“值为对象(o)的节点对应的索引,不存在就返回-1*

public int lastIndexOf(Object o) {

    int index = size;
    if (o==null) {
        for (Entry e = header.previous; e != header; e = e.previous) {
            index--;
            if (e.element==null)
                return index;
        }
    } else {
        for (Entry e = header.previous; e != header; e = e.previous) {
            index--;
            if (o.equals(e.element))
                return index;
        }
    }
    return -1;
}

add(E e):队尾插入新节点,如果队列空间不足,抛出异常;LinkedList没有空间限制,所以可以无限添加。

offer(E e):队尾插入新节点,空间不足,返回false,在LinkedList中和add方法同样效果。

remove():移除队头节点,如果队列为空(没有节点,first为null),抛出异常。LinkedList中就是first节点(链表头)

poll():同remove,不同点:队列为空,返回null

element():查询队头节点(不移除),如果队列为空,抛出异常。

peek():同element,不同点:队列为空,返回null。

/**

 * 检索头结点元素
 */
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

/**
 * 与peek()作用一样
 */
public E element() {
    return getFirst();
}

/**
 * 删除并返回第一个节点
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * 与poll()作用一样
 */
public E remove() {
    return removeFirst();
}

/**
 * 在尾部添加节点与add()一样
 */
public boolean offer(E e) {
    return add(e);
}

// Deque operations

/**

 * 调用add是在最后链接的
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

总结
LinkedList是基于双向链表实现的,不论是增删改查方法还是队列和栈的实现,都可通过操作结点实现 LinkedList无需提前指定容量,因为基于链表操作,集合的容量随着元素的加入自动增加 LinkedList删除元素后集合占用的内存自动缩小,无需像ArrayList一样调用trimToSize()方法 LinkedList的所有方法没有进行同步,因此它也不是线程安全的,应该避免在多线程环境下使用

相关文章
|
SQL 存储 分布式计算
流批一体技术简介
本文由阿里云 Flink 团队苏轩楠老师撰写,旨在向 Flink 用户整体介绍 Flink 流批一体的技术和挑战。
50997 3
流批一体技术简介
【Hbuilder】Hbuilder 插件[App]云打包安装失败--已解决
【Hbuilder】Hbuilder 插件[App]云打包安装失败--已解决
625 0
计算机网络:信道复用技术概念解析
计算机网络:信道复用技术概念解析
387 0
|
算法
双指针法将时间复杂度从 O(n^2) 优化到 O(n)
 双指针法(Two Pointers)是一种常见的算法技巧,常用于数组和链表等数据结构中。
186 0
|
分布式计算 Hadoop 网络安全
|
存储 开发者 流计算
Github成就解锁指南详细讲解
Github在 2022 年推出了全新的成就勋章, 用于表彰有卓越开源贡献的开发者, 在日常使用 Github 的活动中可以解锁这些成就, 并在 Github 个人主页上展示,因此本文将快速介绍如何解锁 Github 成就勋章,截止目前,Github 共开放了 9 个成就, 后续还会推出更多成就!
947 0
|
安全 Java 编译器
【JavaSE专栏3】JDK安装、IntelliJ IDEA安装、配置环境变量(一)
【JavaSE专栏3】JDK安装、IntelliJ IDEA安装、配置环境变量
664 0
|
设计模式 消息中间件 JavaScript
看了我写的设计模式,全公司同事都开始悄悄模仿了。。。 下
看了我写的设计模式,全公司同事都开始悄悄模仿了。。。 下