首页 > Java资讯 > 正文

Java中链表和数组如何学

2019-12-16 16:33:42
2150次动力节点

　　数组是有下标索引和data两部分组成

　　链表是有data和指向下一个数据的指针地址两部分组成

　　综述：数组是线性结构，可以直接索引，即要去第i个元素，a[i]即可。链表也是线性结构，要取第i个元素，只需用指针往后遍历i次就可。貌似链表比数组还要麻烦些，而且效率低些。

　　想到这些相同处中的一些细微的不同处，于是他们的真正不同处渐渐显现了：链表的效率为何比数组低些?先从两者的初始化开始。数组无需初始化，因为数组的元素在内存的栈区，系统自动申请空间。而链表的结点元素在内存的堆区，每个元素须手动申请空间，如malloc。也就是说数组是静态分配内存，而链表是动态分配内存。链表如此麻烦为何还要用链表呢?数组不能完全代替链表吗?为何那时候要用链表?因为管理系统中的插入，删除等操作都很灵活，而数组则大小固定，也无法灵活高效的插入，删除。因为堆操作灵活性更强。数组每次插入一个元素就需要移动已有元素，而链表元素在堆上，无需这么麻烦。

　　说了这么多，数组和链表的区别整理如下：

　　数组静态分配内存，链表动态分配内存;

　　数组在内存中连续，链表不连续;

　　数组元素在栈区，链表元素在堆区;

　　数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n);

　　数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。

　　1.数组的特点：

　　在内存中，数组是一块连续的区域。例如看电影来说，几个去在电影院看电影必须坐在一起。

　　数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。比如看电影时，为了保证10个人能坐在一起，必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。但是这样的缺点是，如果来的人不够10个，那么剩下的位置就浪费了。如果临时有多来了个人，那么10个就不够用了，这时可能需要将第11个位置上的人挪走，或者是他们11个人重新去找一个11连坐的位置，效率都很低。如果没有找到符合要求的作为，那么就没法坐了。

　　插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。比如原来去了5个人，然后后来又去了一个人要坐在第三个位置上，那么第三个到第五个都要往后移动一个位子，将第三个位置留给新来的人。当这个人走了的时候，因为他们要连在一起的，所以他后面几个人要往前移动一个位置，把这个空位补上。

　　随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。并且不利于扩展，数组定义的空间不够时要重新定义数组。

　　2 .链表的特点

　　在内存中可以存在任何地方，不要求连续。在电影院几个人可以随便坐。

　　每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。第一个人知道第二个人的座位号，第二个人知道第三个人的座位号……

　　增加数据和删除数据很容易。再来个人可以随便坐，比如来了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。

　　查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。要找到第三个人，必须从第一个人开始问起。

　　不指定大小，扩展方便。链表大小不用定义，数据随意增删。

　　3.各自的优缺点：

　　(1)数组的优点：

　　随机访问性强

　　查询速度快

　　(2)数组的缺点：