数据结构之数组和链表的区别和List的三个子类的特点

青旅半醒 2022-06-16 07:30 163阅读 0赞

## 数据结构之数组和链表 ##

A:数组
    	* 查询快修改也快
    	* 增删慢
     B:链表
    	* 查询慢,修改也慢
    	* 增删快

区别 转自http://www.cnblogs.com/pre_con/archive/2009/05/27/1490745.html
    1）数组在内存中是逐个存放的，也就是说倘若数组的第一个元素在地址A,则数组第二个元素就在地址A+1。
    而链表则不是，链表每个节点没有相对固定的位置关系。某个节点在地址A其后的节点不一定是A+1,而在内存的其他空闲区域，呈现一种随机的状态。
    2）数组一旦显式的被申明后，其大小就固定了，不能动态进行扩充。而链表则可以，可以动态生成节点并且添加到已有的链表后面。
    3）链表灵活，但是空间和时间额外耗费较大；数组大小固定，元素位置固定，但是操作不灵活，且容易浪费空间，但是时间耗费较小，
    尤其是元素变化不大的时候效率很高。双向链表比单向的更灵活，但是空间耗费也更大

。。。。。

链表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。 
    链表顾名思义，要把各个元素链接起来才算撒。   
      通常链表每一个元素都要保存一个指向下一个元素的指针（单链表）。   
      双链表的化每个元素即要保存到下一个元素的指针，还要保存一个上一个元素的指针。   
      循环链表则把最后一个元素中保存下一个元素指针指向第一个元素。   
    数组是一组具有相同类型和名称的变量的集合。这些变量称为数组的元素,每个数组元素都有一个编号,
    这个编号叫做下标,我们可以通过下标来区别这些元素。数组元素的个数有时也称之为数组的长度。 
    从内存存储角度来看
    　　   a,(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。
    　　   b, 链表从堆中分配空间, 自由度大但申请管理比较麻烦.

## List的三个子类的特点 ##

ArrayList:
     底层数据结构是数组，查询快，增删慢。
     线程不安全，效率高。
     Vector:
     底层数据结构是数组，查询快，增删慢。
     线程安全，效率低。
     Vector相对ArrayList查询慢(线程安全的)
     Vector相对LinkedList增删慢(数组结构)
     LinkedList:
     底层数据结构是链表，查询慢，增删快。
     线程不安全，效率高。
     底层数据结构是数组，查询快，增删慢。
     线程不安全，效率高。

### Vector和ArrayList的区别 ###

Vector是线程安全的,效率低
    ArrayList是线程不安全的,效率高
    	共同点:都是数组实现的

### ArrayList和LinkedList的区别 ###

ArrayList底层是数组结果,查询和修改快
    LinkedList底层是链表结构的,增和删比较快,查询和修改比较慢
    		共同点:都是线程不安全的

List有三个儿子，我们到底使用谁呢? 查询多用ArrayList 增删多用LinkedList 如果都多ArrayList