数组Array

数组在内存中的简单示例：

插入和删除操作

访问时间复杂度为O(1) 插入和删除时间复杂度最差为O(n)，最好为O(1)，平均为O(n/2)

顺序存储的优缺点

 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）,要求内存中可用存储单元的地址必须是连续的。

优点：存储密度大（=1），存储空间利用率高。

缺点：插入或删除元素时要对其他元素进行挪动。

在存储空间使用的灵活性上，链式存储比顺序存储要高。

链式存储时，邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。

链表Linked List

链表结构

单链表

链表的插入

链表的删除

双链表 Doubly Linked List

既有前驱也有后继，既可以往前走可以往后走，在查询链表元素的时候会更加的方便。

面试题

206. Reverse Linked List 链表反转

Python 3解法

24.Swap Node in Pairs  链表的两两反转

给定一个列表，反转他们相邻的两个列表。如果链表节点数为单数，最后一个节点不进行操作。

Python 3解法

141.Linked List Cycle 判断链表是否存在环结构

给定一个链表，确定它是否有一个循环。你能在不使用额外空间的情况下解决这个问题吗?

思路一：暴力硬做

从head开始，next->next->next->next->……..->next…….一直往下走，看看最后一个是否为Null。

思路二：利用Set判重

将每个节点的地址存进Set里面，每到一个新节点去查找Set里面是否存在。时间复杂度 O(n)。

思路三：快、慢指针

快指针每次走两步，慢指针每次走一步。判断快与慢指针是否会相遇，相遇则有环状结构。时间复杂度 O(n)。

Python 3解法

参考摘抄来源：

截图来源：
视频：《算法面试通关40讲》 06丨面试题：反转一个单链表&判断链表是否有环
作者：覃超
链接：https://time.geekbang.org/course/intro/100019701