java string转list集合,list集合转成数组 1.1 说一下 ArrayList 和 LinkedList 的区别?

慈云数据 2023-03-14 行业资讯 689 22

本文已收录,技术和职场问题,请关注公众号【彭旭睿】提问。

前言

大家好,我是小鹏。

在上一篇文章中,我们谈到了基于动态数组的线性列表。 今天我们来讨论一个基于链表的线性表——。

小鹏02交流群已经建立,欢迎加入~

思维导图:

string数组转list_java string转list集合,list集合转成数组_数组转list集合

1. 特点 1.1 说说和?的区别? 遍历速度上:数组是连续的内存空间,基于局部性原则可以更好的命中CPU cache line,而链表是离散的内存空间,对cache line不友好; 在访问速度方面:数组是一个连续的内存空间,支持O(1)时间复杂度的随机访问,而链表需要O(n)时间复杂度来查找元素; 另外和删除操作:如果是在数组的末尾,只需要O(1)的时间复杂度,但是在数组的中间操作需要移动元素,所以需要O(n)的时间复杂度,以及链表本身的删除操作只是修改了引用点,只需要O(1)的时间复杂度(如果考虑到查询被删除节点的时间,复杂度分析还是O(n),还是比较快的比工程分析中的数组); 在额外的内存消耗方面:在数组的末尾增加了一个空闲位置java string转list集合,list集合转成数组,在节点中增加了前驱和后继指针。 1.2 多面生活

数据结构上,它不仅实现了相同的List接口,还实现了Deque接口(继承自Queue接口)。

Deque接口代表了一个双端队列(Ended Queue),它允许在队列的两端进行操作,因此它可以同时实现队列行为和栈行为。

队列接口:

拒绝策略 抛出异常 返回一个特殊值 入队(队尾) add(e)offer(e) 出队(队头) ()poll() 观察(队头) ()peek ()

Queue的API可以分为两类,区别在于方法的拒绝策略:

双端队列接口:

Java并没有提供标准的栈接口(不知为何没有),而是放在Deque接口中:

拒绝策略 抛出异常相当于push(e)(e)出栈 pop()() 观察(栈顶) peek()()

除了标准的队列和堆栈行为外,Deque 接口还提供了 12 个在两端操作的方法:

拒绝策略 抛出异常 返回值增加 (e)/ (e)(e)/ (e) ()/ ()()/ () ()/ ()()/ ()

2.源码分析

string数组转list_数组转list集合_java string转list集合,list集合转成数组

本节我们来分析一下主进程的源码。

2.1 属性

属性很容易理解。 如无意外,有小朋友走出来举手提问:

直接回答这个问题。 我的理解是:因为内部类编译后会生成一个独立的Class文件,如果外部类的字段是类型,那么编译器需要调用方法,非字段可以直接访问字段。

我们在分析源码的过程中回答这个问题。

疑惑少了很多,真香(别高兴得太早)。

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable {
    // 疑问 1:为什么字段都不声明 private 关键字?
    // 疑问 2:为什么字段都声明 transient 关键字?
    // 元素个数
    transient int size = 0;
    // 头指针
    transient Node first;
    // 尾指针
    transient Node last;
    // 链表节点
    private static class Node {
        // 节点数据
        // (类型擦除后:Object item;)
        E item;
        // 前驱指针
        Node next;
        // 后继指针
        Node prev;
        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

2.2 施工方法

有2个构造函数:

// 无参构造方法
public LinkedList() {
}
// 带集合的构造方法
public LinkedList(Collection c) {
    this();
    addAll(c);
}
// 在链表尾部添加集合
public boolean addAll(Collection c) {
    // 索引为 size,等于在链表尾部添加
    return addAll(size, c);
}

2.3 如何添加

提供了很多方法,都称为一个系列java string转list集合,list集合转成数组,或者内部完成。 如果在链表的中间添加了一个节点,会使用node(index)方法查询指定位置的节点。

其实我们会发现,所有添加的逻辑都可以归纳为6个步骤:

分析添加方法的时间复杂度,区分在链表的两端或中间添加元素:

添加方法

public void addFirst(E e) {
    linkFirst(e);
}
public void addLast(E e) {
    linkLast(e);
}
public boolean add(E e) {
    linkLast(e);
    return true;
}
public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        // 在尾部添加
        linkLast(element);
    else
        // 在指定位置添加
        linkBefore(element, node(index));
}
public boolean addAll(Collection c) {
    return addAll(size, c);
}
// 在链表头部添加
private void linkFirst(E e) {
    // 1. 找到插入位置的后继节点(first)
    final Node f = first;
    // 2. 构造新节点
    // 3. 将新节点的 prev 指针指向前驱节点(null)
    // 4. 将新节点的 next 指针指向后继节点(f)
    // 5. 将前驱节点的 next 指针指向新节点(前驱节点是 null,所以没有这个步骤)
    final Node newNode = new Node<>(null, e, f);
    // 修改 first 指针
    first = newNode;
    if (f == null)
        // f 为 null 说明首个添加的元素,需要修改 last 指针
        last = newNode;
    else
        // 6. 将后继节点的 prev 指针指向新节点
        f.prev = newNode;
    size++;
    modCount++;
}
// 在链表尾部添加
void linkLast(E e) {
    final Node l = last;
    // 1. 找到插入位置的后继节点(null)
    // 2. 构造新节点
    // 3. 将新节点的 prev 指针指向前驱节点(l)
    // 4. 将新节点的 next 指针指向后继节点(null)
    final Node newNode = new Node<>(l, e, null);
    // 修改 last 指针
    last = newNode;
    if (l == null)
        // l 为 null 说明首个添加的元素,需要修改 first 指针
        first = newNode;
    else
        // 5. 将前驱节点的 next 指针指向新节点
        l.next = newNode;
    // 6. 将后继节点的 prev 指针指向新节点(后继节点是 null,所以没有这个步骤)
    size++;
    modCount++;
}
// 在指定节点前添加
// 1. 找到插入位置的后继节点
void linkBefore(E e, Node succ) {
    final Node pred = succ.prev;
    // 2. 构造新节点
    // 3. 将新节点的 prev 指针指向前驱节点(pred)
    // 4. 将新节点的 next 指针指向后继节点(succ)
    final Node newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        // 5. 将前驱节点的 next 指针指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}
// 在指定位置添加整个集合元素
// index 为 0:在链表头部添加
// index 为 size:在链表尾部添加
public boolean addAll(int index, Collection c) {
    checkPositionIndex(index);
    // 事实上,c.toArray() 的实际类型不一定是 Object[],有可能是 String[] 等
    // 不过,我们是通过 Node中的item 承接的,所以不用担心 ArrayList 中的 ArrayStoreException 问题
    Object[] a = c.toArray();
    // 添加的数组为空,跳过
    int numNew = a.length;
    if (numNew == 0)
        return false;
    // 1. 找到插入位置的后继节点
    // pred:插入位置的前驱节点
    // succ:插入位置的后继节点
    Node pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 找到 index 位置原本的节点,插入后变成后继节点
        succ = node(index);
        pred = succ.prev;
    }
    // 插入集合元素
    for (Object o : a) {
        E e = (E) o;
        // 2. 构造新节点
        // 3. 将新节点的 prev 指针指向前驱节点
        Node newNode = new Node<>(pred, e, null);
        if (pred == null)
            // pred 为 null 说明是在头部插入,需要修改 first 指针
            first = newNode;
        else
            // 5. 将前驱节点的 next 指针指向新节点
            pred.next = newNode;
        // 修改前驱指针
        pred = newNode;
    }
    if (succ == null) {
        // succ 为 null 说明是在尾部插入,需要修改 last 指针
        last = pred;
    } else {
        // 4. 将新节点的 next 指针指向后继节点
        pred.next = succ;
        // 6. 将后继节点的 prev 指针指向新节点
        succ.prev = pred;
    }
    // 数量增加 numNew
    size += numNew;
    modCount++;
    return true;
}
// 将 LinkedList 转化为 Object 数组
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

在链表中间添加节点时,会使用node(index)方法查询指定位置的节点。 可以看出,维护首尾节点的作用又发挥出来了:

虽然,从复杂度分析的角度来看,向哪个方向查询没有区别,时间复杂度都是O(n)。 但从工程分析的角度来看,还是有区别的。 从靠近目标节点的位置开始查询,实际执行时间会更短。

数组转list集合_string数组转list_java string转list集合,list集合转成数组

查询指定位置节点

// 寻找指定位置的节点,时间复杂度:O(n)
Node node(int index) {
    if (index < (size >> 1)) {
        // 如果索引位置小于 size/2,则从头节点开始找
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 如果索引位置大于 size/2,则从尾节点开始找
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

方法其实就是add方法的逆操作,这里不再赘述。

// 删除头部元素
public E removeFirst() {
    final Node f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
// 删除尾部元素
public E removeLast() {
    final Node l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
// 删除指定元素
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

2.4 的迭代器

Java 是句法糖,本质上就是它采用的方式。 由于它是双向的,因此只提供了 1 个迭代器:

与其他容器类一样,它的迭代器中有一个快速失败机制。 如果在迭代过程中发现有变化,就说明数据被修改了,会提前抛出异常(当然不一定是被其他线程修改了)。

public ListIterator listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}
// 非静态内部类
private class ListItr implements ListIterator {
    private Node lastReturned;
    private Node next;
    private int nextIndex;
    // 创建迭代器时会记录外部类的 modCount
    private int expectedModCount = modCount;
    ListItr(int index) {
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
    public E next() {
        // 更新 expectedModCount
        checkForComodification();
        ...
    }
    ...
}

2.5 序列化过程

string数组转list_java string转list集合,list集合转成数组_数组转list集合

重写了JDK序列化的逻辑,不再对链表节点进行序列化,只对链表节点中的有效数据进行序列化,从而减小序列化后产品的体积。 反序列化时,只需要将对象添加到链表的末尾即可恢复链表的顺序。

// 序列化和反序列化只考虑有效数据
// 序列化过程
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();
    // 写入链表长度
    s.writeInt(size);
    // 写入节点上的有效数据
    for (Node x = first; x != null; x = x.next)
        s.writeObject(x.item);
}
// 反序列化过程
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();
    // 读取链表长度
    int size = s.readInt();
  
    // 读取有效元素并用 linkLast 添加到链表尾部
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}

2.6 clone()过程

中的第一个和最后一个指针是引用类型,所以需要在clone()中实现深拷贝。 否则,两个对象克隆后会相互影响:

private LinkedList superClone() {
    try {
        return (LinkedList) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}
public Object clone() {
    LinkedList clone = superClone();
    // Put clone into "virgin" state
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;
    // 将原链表中的数据依次添加到新立案表中
    for (Node x = first; x != null; x = x.next)
        clone.add(x.item);
    return clone;
}

2.7 如何实现线程安全?

有5种方式:

三、总结

在上一篇文章中,我们提到了List的数组实现,不仅是List的链表实现,还有Queue和Stack的链表实现。 那么,Java中Queue和Stack的数组实现是怎样的呢? 我们将在下一篇文章中讨论,敬请关注。

评论列表

234
中间操作需要移动元素,所以需要O(n)的时间复杂度,以及链表本身的删除操作只是修改了引用点,只需要O(1)的时间复杂度(如果考虑到查询被删除节点的时间,复杂度分析还是O(n),还是比较快的比工程分析
2023-03-15 06:50:07 回复
234
点 private static class Node { // 节点数据 // (类型擦除后:Object item;) E item; // 前驱指针 Node next; //
2023-03-15 00:55:49 回复
// 疑问 1:为什么字段都不声明 private 关键字? // 疑问 2:为什么字段都声明 transient 关键字? // 元素个数 transient int size = 0;
2023-03-15 00:51:07 回复
his.prev = prev; } }}2.2 施工方法有2个构造函数:// 无参构造方法public LinkedList() {}// 带
2023-03-15 11:33:13 回复
个在两端操作的方法:拒绝策略 抛出异常 返回值增加 (e)/ (e)(e)/ (e) ()/ ()()/ () ()/ ()()/ ()2.源码分析本节我们来分
2023-03-15 09:12:24 回复
2:为什么字段都声明 transient 关键字? // 元素个数 transient int size = 0; // 头指针 transient
2023-03-15 05:33:07 回复
()2.源码分析本节我们来分析一下主进程的源码。2.1 属性属性很容易理解。 如无意外,有小朋友走出来举手提问:直接回答这个问题。 我的理解是:因为内部类编译后会生成一个独立的Class文件,如果外部类的字段是类型,那么编译器需要调用方法,非字段可以直接访问字段。我们在分析源码的过程中回答这个问
2023-03-15 07:46:38 回复
class Node { // 节点数据 // (类型擦除后:Object item;) E item; // 前驱指针 Node next; // 后继指针 Node prev
2023-03-15 03:37:44 回复
em; // 前驱指针 Node next; // 后继指针 Node prev; Node(Node prev, E element, Node next) { this.item = eleme
2023-03-15 09:49:16 回复
= prev; } }}2.2 施工方法有2个构造函数:// 无参构造方法public LinkedList() {}// 带集合的构造方法public LinkedList(Coll
2023-03-15 08:37:41 回复
接口(继承自Queue接口)。Deque接口代表了一个双端队列(Ended Queue),它允许在队列的两端进行操作,因此它可以同时实现队列行为和栈行为。队列接口:拒绝策略
2023-03-15 10:29:55 回复
// 后继指针 Node prev; Node(Node prev, E element, Node next) {
2023-03-15 06:29:04 回复
ist(Collection
2023-03-15 00:14:06 回复
,因此它可以同时实现队列行为和栈行为。队列接口:拒绝策略 抛出异常 返回一个特殊值 入队(队尾) add(e)offer(e) 出队(队头) ()poll() 观察
2023-03-15 07:46:33 回复
空闲位置java string转list集合,list集合转成数组,在节点中增加了前驱和后继指针。 1.2 多面生活在数据结构上,它不仅实现了相同的List接口,还实现
2023-03-15 10:08:40 回复
ic class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serial
2023-03-15 05:00:34 回复
ze = 0; // 头指针 transient Node first; // 尾指针 transient Node last; // 链表节点 private
2023-03-15 06:57:06 回复
2个构造函数:// 无参构造方法public LinkedList() {}// 带集合的构造方法public LinkedList(Collection
2023-03-15 06:38:48 回复
Queue的API可以分为两类,区别在于方法的拒绝策略:双端队列接口:Java并没有提供标准的栈接口(不知为何没有),而是放在Deque接口中:拒绝策略 抛出异常相当于push(e)(e)出栈 pop()() 观察(栈顶) peek()()除了标准的队列和堆栈行为外,
2023-03-15 10:50:55 回复
别高兴得太早)。public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable { /
2023-03-15 08:24:27 回复
{ // 节点数据 // (类型擦除后:Object item;) E item; // 前驱指针 Node next; // 后继指针 Node prev; No
2023-03-15 04:11:22 回复
本文已收录,技术和职场问题,请关注公众号【彭旭睿】提问。前言大家好,我是小鹏。在上一篇文章中,我们谈到了基于动态数组的线性列表。 今天我们来讨论一个基于链表的线性表——。小鹏02
2023-03-15 04:48:46 回复

发表评论:

微信扫一扫加客服

微信扫一扫加客服

微信扫一扫加客服

微信扫一扫加客服