数据结构笔记（一）：数组、链表（数据结构数组和链表的区别）

（一）数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

1、数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

通过 a[i]_address = a[0]_address + i*元素的大小（字节） ，得到a[i]所在的位置。

2、插入：

数组长度为n，在索引k插入一个元素，k~n的元素都需要向后搬移。时间复杂度为O(n) 。（在末尾插入时间复杂度O(1)，首位插入则为O（n）,平均时间复杂度为O（n））

如果数组是无序的，可以在末尾插入，再和第k个元素互换，实现O（1）时间复杂度复杂度的插入。

3、删除

和插入类似。数组长度为n,删除第k个元素，则k+1~n的元素都需要向前搬移一位，时间复杂度为o(n)。

如果数组是无序的，可以将末尾的元素和第k个元素互换位置，然后再删除，实现O(1)时间复杂度的删除。

（二）链表

1、数组与链表在底层存储结构上的区别

（1）数组需要一段连续的内存空间，链表则不需要

（2）链表通过“指针”，将一组零散的内存空间串联在一起。

2、常用的链表结构

（1）单链表

（2）双向链表

（3）循环链表

3、单链表

（1）把内存块(data)称为链表的“结点”,用于存储数据。next记录下一个节点的内存地址，把这个记录下个结点地址的指针称为后继指针next。

（2）第一个结点称为头结点，最后一个结点称为尾结点。尾结点的指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表的最后一个结点。

（3）链表插入、删除的时间复杂度O（1），只需要修改指针即可。

（4）链表随机访问的时间复杂度是O（n）。因为链表的内存空间是零散的，没法像数组那样通过简单的寻址公式实现随机访问，只能一个一个结点依次遍历，直到找到相应的结点。

4、循环链表

和单链表唯一的区别就在于尾结点，尾结点的指针指向头结点，而不是空地址。

5、双向链表

(1)相比单链表，多了一个前驱指针，指向前一个结点

（三）练习题

1、单链表反转。 leetcode : 206

2、链表中环的检测: leetcode 141

3、两个有序的链表合并

4、删除链表倒数第 n 个结点

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。