链表

与数组一样，链表也是一种基础的数据结构，与数组不同的是，数组需要一组连续的存储空间，但是，链表就不需要，它通过一个指针这样的结构，来实现数据的连续性。

数组与链表的内存分布

链表，有多种实现方式，最基本的单链表，复杂一点的双链表，还有循环链表等，首先来看单链表。

单链表

从图中可以看出，单链表的一个结点由数据和指针组成，写出代码就是：

public static class Node {   //单链表节点类

    AnyTypeAdapter val;

    Node next;

   Node(AnyTypeAdapter data, Node n) {

        val = data;

        next = n;

       }

}

可以看出，链表就是一个链表对象的next对象引用指向另外一个链表对象，这样符合面向对象思想，全员皆对象，同时也表现了它的一大特性，插入删除特别快，只需要常数的时间就可以做到。我们不需要像数组增删一样，要考虑到它的连续性，因为链表在底层中的存储时不连续的。

为了方便理解，上一张图：

单链表增删

从上图来看，增删只需要将节点对象中的next这个对象引用指向对应结点对象就可以了。

增删快速是链表的最大特点，但是由此带来的坏处显而易见，查询特别慢，因为不像数组可以通过地址查询快速定位，想要定位链表中的某一个数据，我们只能从头节点来遍历来确定位置。

单链表较为简单，在来看双链表：

双向链表

双向链表相较于单链表，多了一个指向前面结点对象的指针。

以删除来说，不外乎两种情况

1：删除链表中指定值的结点

2：删除链表中给定指定的结点

第一种情况下，不管是单链表还是双向链表，都需要遍历一遍

不过在第二种情况下，由于双向链表有指向前一个对象的指针，就可以在O(1) 时间解决，不过对应单链表，依然要O(n)的时间内解决。

知其然知其所以然，依然不够，多练是学习的根本之道：

*单链表反转

*链表中环的检测

*两个有序的链表合并

*删除链表倒数第 n 个结点

*求链表的中间结点