从前慢现在也慢

这个屌丝很懒，什么也没留下！

热门标签

Java复习知识点十八：List集合、ArrayList扩容机制、Vector、LinkedList的原理_linkedlist扩容机制原理

作者：从前慢现在也慢 | 2024-03-27 05:03:43

踩

linkedlist扩容机制原理

1、List接口

基本介绍：List接口是Collection接口的子接口 单列集合

List集合类中元素有序（即添加和取出顺序一致）、且可以重复
List集合中的每个元素都有其对应的顺序索引，即支持索引
List的所有实现子类：
常用的只有 ArrayList、LinkedList、Vector

1.1 List接口常用方法

> List集合里添加了一些根据索引来操作集合元素的方法
1

void add(int index.Object ele)：在index位者插入ele元素
boolean addAll(int index, Collection eles)：从index位置开始将
eles中的所有元素添加进来
Object get(int index)：获取指定index位置的元素
int indexof(Object obj)：返回obj在集合中首次出现的位置
int lastIndexOf(Object obj)：返向obj在当前集合中末次出现的位置
Object remove(int index)：移除指定index位置的元素，并返回此元
素
Object set(int index,Object ele)：设置指定index位智的元素为ele ,
相当于是替换.
List subList(int fromlndex, int tolndex)：返回从fromlndex到
tolndex位置的子集合

1.2 List的三种遍历方式

使用Iterator

iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.print(iterator.next()+" ");
}
1
2
3
4

使用增强for

for (Object o : list) {
	System.out.println(o);
}
1
2
3

使用普通for

for(int i = 0; i < list.size(); i++){
	Object obj = list.get(i);
	System.out.println(obj);
}
1
2
3
4

2、ArrayList

2.1 ArrayList注意事项

可以存放任意值，包含null，ArrayList可以加入null，并且多个
ArrayList是由数组实现数据存储的
ArrayList基本等同于Vector，除了ArrayList是线程不安全（执行效率高），在多线程情况下不建议使用ArrayList

2.2 ArrayLIst扩容源码分析

ArrayList类中拥有一个 transient Object[ ] elementData成员变量，对象数组
```
 > transient表示该属性不会被序列化
1
```
使用无参构造器，创建ArrayList对象时，则初始elementData容量为0，第一次添加，则扩容elememtData为10，如果需要再次扩容，则扩容elementData为1.5倍
如果使用指定大小的构造器，则初始elementData容量为 指定大小，若需要扩容，则直接扩容为elementData的1.5倍

无参构造器：初始容量为空

在这里插入图片描述

添加第一个元素：会执行扩容到10

在这里插入图片描述

扩容方法：

在这里插入图片描述

有参构造：

在这里插入图片描述

3、Vector

3.1 Vector基本介绍

Vector类的定义：
Vector底层也是一个对象数组，protected Object[] elementData；
Vector是一个线程同步的，即线程安全，方法都带有synchronize
在开发中，需要线程同步安全时，考虑使用Vector

3.2 Vector扩容源码分析

使用无参构造器，会初始化容量为10，容量满后，会按照2倍扩容
使用有参构造，每次容量满后，直接按2倍扩容

无参构造：

在这里插入图片描述

调用有参构造：初始化大小为10

在这里插入图片描述

添加元素：

在这里插入图片描述

3.3 Vector vs ArrayList

在这里插入图片描述

4、LinkedList

4.1 LinkedList基本介绍

LinkedList底层实现了 双向链表 和 双端队列 特点
可以添加任意元素（元素可以重复），包括null
线程不安全，没有实现同步

底层结构：

LinkedList 底层维护了一个双向链表。
LinkedList 维护了两个属性 first 和 last 分别指向 首节点 和 尾结点。
每个节点（Node对象），里面又维护了 prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表。
LinkedList 元素的添加和删除不是通过数组来完成的，相对来说效率较高

模拟一个双向链表：

public class LinkedList01 {
    public static void main(String[] args) {
        //模拟一个简单的双向链表

        Node jack = new Node("jack");
        Node tom = new Node("tom");
        Node bob = new Node("bob");

        //连接三个节点，形成双向链表
        //jack -> tom -> bob
        jack.next = tom;
        tom.next = bob;
        //bob -> tom -> jack
        bob.prev = tom;
        tom.prev = jack;

        Node first = jack;
        Node last = bob;

        //遍历 从头到尾
        System.out.println("====从头到尾=====");
        while (true) {
            if (first == null) {
                break;
            }
            System.out.println(first);
            first = first.next;

        }
        //遍历 尾到头
        System.out.println("=====从尾到头=====");
        while (true) {
            if (last == null) {
                break;
            }
            System.out.println(last);
            last = last.prev;

        }
        //添加节点 在 tom 和 bob之间
        Node simth = new Node("simth");
        simth.next = bob;
        simth.prev = tom;

        tom.next = simth;
        bob.prev = simth;
        //遍历
        System.out.println("=====添加元素后遍历=====");
        //让first再指向jack
        first = jack;

        while (true) {
            if (first == null) {
                break;
            }
            System.out.println(first);
            first = first.next;
        }
    }
}

//定义一个Node类，Node对象 表示 双向链表的一个节点
class Node {
    public Object item;//真正存放数据
    public Node next;//指向下一个节点
    public Node prev;//指向上一个节点

    public Node(Object name) {
        this.item = name;
    }
    
    @Override
    public String toString() {
        return "Node name=" + item;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77