数组和链表的区别(数组和链表的区别java)

要说这个区别，你要先知道数据结构。要说清楚数据结构要一本书的内容，所以我只能抽个直接相关的东东来说一下：线性表。 线性表：逻辑上 是一张二维表，里面有元素和相应元素的位置。物理上 线性表以两种形式在内存中存放：顺序表和链式表。这顺序表要求：在内存中连续的内存地址存放。（可看成数组）而链式表不要求以连续的内存块平存放，它有一个指针域来索引到下一个节点。（链表）性能上分析：顺序表（数组）可直接索引到某个元素，而链表只能从链表头（如果为单链表）开始一个一个去找，所以比顺序表要低效。另外一方面，如果顺序表要删除或插入元素就要移动多个后面的元素，而链表则不用移动元素，只要修改指针域就行了，所以在有删除或修改动作时，链表比较高效。 当然我说的还很不全面，你可以参考一下数据结构这本书的线性表这章。
数组和连表最大的区别是：数组需要定义长度，连表不需要。
二者都属于一种数据结构 从逻辑结构来看1. 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。2. 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素从内存存储来看1. (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小2. 链表从堆中分配空间, 自由度大但是申请管理比较麻烦 从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反， 如果需要经常插入和删除元素就需要用链表数据结构了。

二者都属于一种数据结构 从逻辑结构来看1. 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。2. 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素从内存存储来看1. (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小2. 链表从堆中分配空间, 自由度大但是申请管理比较麻烦 从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反， 如果需要经常插入和删除元素就需要用链表数据结构了。

首先从逻辑结构上说，两者都是数据结构的一种，但存在区别，数组是申请的一块连续的内存空间，并且是在编译阶段就要确定空间大小的，同时在运行阶段是不允许改变的，所以它不能够随着需要的改变而增加或减少空间大小，所以当数据量大的时候，有可能超出了已申请好的数组上限，产生数据越界，或者是数据量很小，对于没有使用的数组空间，造成内存浪费。链表则是动态申请的内存空间，并不像数组一样需要事先申请好大小，链表是现用现申请就OK，根据需求动态的申请或删除内存空间，对于的是增加或删除数据，所以比数组要灵活。再从物理存储即内存分配上分析，数组是连续的内存，对于访问数据，可以通过下标直接读取，时间复杂度为O(1)，而添加删除数据就比较麻烦，需要移动操作数所在位置后的所有数据，时间复杂度为O（N）。链表是物理上非连续的内存空间，对于访问数据，需要从头便利整个链表直到找到要访问的数据，没有数组有效，但是在添加和删除数据方面，只需要知道操作位置的指针，很方便可以实现增删，教数组比较灵活有效率。所以综合以上，对于快速访问数据，不经常有添加删除操作的时候选择数组实现，而对于经常添加删除数据，对于访问没有很高要求的时候选择链表。

数组定义简单，以连续的变量形式储存，不可以减少或添加任何变量，因此在定义时必须已知长度，可能造成数组不够长或内存浪费的情况; 链表以结构体的自引用为原理，可以在内存中以不连续的方式储存，并动态分配内存，即随时加入或删除一个变量。但链表定义比较复杂，且除头结点外每一个结点都没有名 字，引用起来比较辛苦。如果是已知所需变量数，还是数组方便些。

1、内存不同数组静态分配内存，链表动态分配内存。2、连续情况不同数组在内存中连续，链表不连续。3、元素位置不同数组元素在栈区，链表元素在堆区。4、复杂度不同数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。