java常用数据结构和方法

字符串

String、StringBuffer、StringBuilder之间的区别

在 Java 中字符串属于对象，Java 提供了 String 类来创建和操作字符串。String 类是不可变类，即一旦一个 String 对象被创建以后，包含在这个对象中的字符序列是不可改变的，直至这个对象被销毁。

Java 提供了两个可变字符串类 StringBuffer 和 StringBuilder，中文翻译为“字符串缓冲区”。

StringBuilder 类是 JDK 1.5 新增的类，它也代表可变字符串对象。实际上，StringBuilder 和 StringBuffer 功能基本相似，方法也差不多。不同的是，StringBuffer 是线程安全的，而 StringBuilder 则没有实现线程安全功能，所以性能略高。因此在通常情况下，如果需要创建一个内容可变的字符串对象，则应该优先考虑使用 StringBuilder 类。

StringBuffer、StringBuilder、String 中都实现了 CharSequence 接口。CharSequence 是一个定义字符串操作的接口，它只包括 length()、charAt(int index)、subSequence(int start, int end) 这几个 API。

StringBuffer、StringBuilder、String 对 CharSequence 接口的实现过程不一样，如下图 1 所示：

对CharSequence接口的实现

图 1 对CharSequence接口的实现

可见，String 直接实现了 CharSequence 接口，StringBuilder 和 StringBuffer 都是可变的字符序列，它们都继承于 AbstractStringBuilder，实现了 CharSequence 接口。

总结

String 是 Java 中基础且重要的类，被声明为 final class，是不可变字符串。因为它的不可变性，所以拼接字符串时候会产生很多无用的中间对象，如果频繁的进行这样的操作对性能有所影响。

StringBuffer 就是为了解决大量拼接字符串时产生很多中间对象问题而提供的一个类。它提供了 append 和 add 方法，可以将字符串添加到已有序列的末尾或指定位置，它的本质是一个线程安全的可修改的字符序列。

在很多情况下我们的字符串拼接操作不需要线程安全，所以 StringBuilder 登场了。StringBuilder 是 JDK1.5 发布的，它和 StringBuffer 本质上没什么区别，就是去掉了保证线程安全的那部分，减少了开销。

线程安全：

StringBuffer：线程安全 StringBuilder：线程不安全

速度：

一般情况下，速度从快到慢为 StringBuilder > StringBuffer > String，当然这是相对的，不是绝对的。

使用环境：

操作少量的数据使用 String。单线程操作大量数据使用 StringBuilder。多线程操作大量数据使用 StringBuffer。

ArrayList和LinkedList

ArrayList和LinkedList区别

ArrayList和LinkedList都是实现了List接口，都不保证线程安全的
ArrayList是使用的动态数组的数据结构，LinkedList使用的是双向链表的数据结构
一般来说LinkedList的空间占用要比ArrayList要大，因为LinkedList的每个元素都需要保存前后元素的位置以及数据，ArrayList元素数量如果到达临界值时需要扩容
ArrayList因为使用数组，因此在随机访问的速度上要比LinkedList速度快
LinkedList使用双向链表数据结构，但是在删除和新增的时候速度不一定要比ArrayList速度快（下面举例说明）

ArrayList和LinkedList对比

首先简单说明ArrayList和LinkedList的查询和插入逻辑： ArrayList：查询数据时，直接找到对应索引的值。插入数据时，若指定位置，则需要将该位置后所有元素向后移动，删除同理。 LinkedList：查询数据时，若索引值小于索引数据量的1/2，则从头开始查找，若索引值大于索引数据量的1/2，则从尾开始查找。插入数据时，需要先找到对应位置，所以和ArrayList相比不一定谁快谁慢。
举例说明首先向ArrayList和LinkedList各插入100000数据，之后进行查询和插入，比较时间。查询的结果毋庸置疑，展示看看就好。需要多次对比插入的数据量及插入位置。

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
   /**
   * ArrayList和LinkedList查询和插入时间
   */
public class ListTest {
   public static void main(String[] args) {
       ArrayList<Integer> arrayList = new ArrayList<Integer>();
       LinkedList<Integer> linkedList = new LinkedList<Integer>();
       //插入十万数据
       for (int i = 0; i < 100000; i++) {
           arrayList.add(i);
           linkedList.add(i);
       }
       //记录时间
       //System.out.println("array查询时间："+gettime(arrayList));
       //System.out.println("linked查询时间："+gettime(linkedList));
       System.out.println("array插入时间："+inserttime(arrayList));
       System.out.println("linked插入时间："+inserttime(linkedList));
	}
//插入数据
    private static long inserttime(List<Integer> list) {
        long number = 10000;//插入的数据量   10000  50000  80000
        int index = 10000;//从哪里开始插入   100   1000   10000
        long time = System.currentTimeMillis();
        for (int i = 0; i < number; i++) {
            list.add(index,i);
        }
        return System.currentTimeMillis()-time;
    }

    //查询数据
    public static long gettime(List<Integer> list){
        long time = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            //根据索引值找到对应索引
            int search = Collections.binarySearch(list, list.get(i));
            if (search!=i){
                System.out.println("索引值错误！");
            }
        }
        return System.currentTimeMillis()-time;
    }
}

下面为多次测试的输出结果

--在100位置插入10000条数据
array查询时间：16
linked查询时间：27901
array插入时间：129
linked插入时间：2

--在1000位置插入10000条数据
array查询时间：13
linked查询时间：28892
array插入时间：145
linked插入时间：17

--在10000位置插入10000条数据
array查询时间：19
linked查询时间：30404
array插入时间：116
linked插入时间：175

--在50000位置插入10000条数据
array查询时间：18
linked查询时间：27936
array插入时间：55
linked插入时间：857

--在50000位置插入100条数据
array查询时间：16
linked查询时间：28612
array插入时间：3
linked插入时间：9

--在50000位置插入1000条数据
array查询时间：14
linked查询时间：28853
array插入时间：12
linked插入时间：88

因此可以看出，ArrayList和LinkedList的插入速度和数据量及插入位置有关。

在插入小数据量时差异不大，但是插入数据量变大时，LinkedList速度会逐渐比ArrayList慢。
若插入位置在中间则LinkedList会达到最慢，越靠近边缘位置LinkedList速度越快。