数组与链表

  数组与链表，在数据结构中都属于线性表。所谓线性表，是指所有元素都排列在一个维度上；对其中的任意一个元素来说，除了头和尾，都有且只有一个前驱元素和一个后继元素。

数组

数组的实现逻辑

储存：数组储存在连续的内存中。

访问：因为数组存储的内存连续，因此支持随机访问。所谓随机访问，也就是直接下标操作。

增加：因为数组内存的连续性，因此若要增加元素，为保持数组的线性，必须把此元素之后的所有元素依次后移。

删除：删除同理增加元素，必须把元素依次前移，以保证数组的线性和完整性。

数组的时间复杂度

操作时间复杂度追加O(1)查找O(1)插入O(n)删除O(n)

链表

链表的实现逻辑

存储：链表可以用任意的存储单元进行存储，也就是说链表的存储可以是连续的内存单元，也可以是不连续的内存单元。

结构：由于链表的非连续存储，因此对于连接元素的表示，除了本身的值之外，还需要存储元素的下一个元素的指针。

访问：链表的特性决定其失去了线性表随机访问的特性。查找特定的值需要遍历链表。

增加：在特定的位置增加链表的元素，非常简单，只需要移动对应的下一元素的指针即可。

删除：在链表中删除元素，需要移动删除前元素的下一个元素指针到删除后的元素即可。

链表的时间复杂度

操作时间复杂度追加O(1)查找O(n)插入O(1)删除O(1)

链表的分类

单向链表：普通链表，每一个元素仅有指向下一元素的指针；双向链表：每一个元素不仅有指向下一元素的指针，还有指向前一个元素的指针；循环链表：链表的未元素有指向头元素的指针，形成循环；

LeetCode相关题目

移动零

LeetCode题目 移动零：

题目内容：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

说明:

必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。

解题思路： 题目要求在原数组上操作，因此不能使用额外数组的方式解决。

遍历数组，遇见0直接删除，在不够的位置补0.数组的删除时间复杂度为O(n)，因此这种方式也是复杂度最高的；遍历，遇见0则移到最后，非0移到前面，其复杂度也方式1一致；使用双指针，遇见0进行交换，时间复杂度为O(n)，空间复杂度为O(1)。 public void moveZeroes(int[] nums) { if(nums == null){ return; } int j = 0; // j和i是两个指向数组的指针 for(int i = 0; i < nums.length; i++){ if(nums[i] != 0){ //非0元素，移到前面 nums[j++] = nums[i]; } } for(int i = j; i < nums.length; i++){ nums[i] = 0; // 后边的全是0 } }