数据结构中（一维）数组与（单）链表的区别和联系？

Question

数据结构中（一维）数组与（单）链表的区别和联系？从插入，删除，内存占用，数据合并，从元素中存储方便性等几方面来说！

Answer 1

链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。
　　
　　A 从逻辑结构来看
　　
　　A-1. 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
　　
　　A-2. 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）

比如插入,在数组中插入的话,你就将其他的数据的位置移动,操作会比较多.比如a[5],假设a[4]是空着的，要在第二个位置插入一个数据x，那么a[4]=a[3],a[3]=a[2],a[2]=a[1],a[1]=x.

若在链表这只要让前面一个的结点的向后指针指向插入的数据就行,插入数据的向后指针指向他前面一个结点原来的指针指向的那个数据.比如本来a.next->b,插入后a.next->x,x.next->b（写代码的时候当然没有什么b和x，其实都是a,这里只是为了叙述得清楚，让你看懂点）

删除的话也类似,数组中就用移动许多数据的位置.
而链表中只要让要删除的结点的前面一个结点的向后指针指向要删除结点的后一个结点就可以了，比如本来a.next->x,x.next->b,修改成a.next->b就达到删除效果了。

数组中的数据在内存中的按顺序存储的，而链表是随机存储的。

LZ所谓的数据合并是什么意思？不大懂？

存储方便性，这个也不是很理解，像随意插入删除的话肯定链表方便。但是要按一定顺序的话单链表就要一个一个结点试过，而数组比如类似这样一个数组a[0]=0,a[1]=1,a[2]=2……这样各个元素的值和他所处位置的数值有关联的数组的话，找到合适位置就会方便很多，不需要像链表那样一个一个试下去，花费很多操作。