今日目录：
1：可能说出链表的存储构造和特点
2：可能说出链表的几种分类及各自的存储构造
3：能说出链表和数组的差别
4：实现实战演练题目
5：实现综合案例
1、概念及存储构造
问题：思考一下动静数组ArrayList存在哪些弊病？
1：插入，删除工夫复杂度高
2：可能会造成内存空间的大量节约
3：须要一块间断的存储空间，对内存的要求比拟高，比方咱们要申请一个1000M的数组，如果内存中没有间断的足够大的存储空间则会申请失败，即使内存的残余可用空间大于1000M，依然会申请失败。
论断：是否做到用多少内存空间就申请多少内存？
链表（Linked list）是一种物理存储单元上非间断、非程序的存储构造，链表中的每一个元素称之为结点（Node），结点之间用指针（援用）连接起来，指针的指向程序代表了结点的逻辑程序，结点能够在运行时动静生成。每个结点包含两个局部：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表能解决数组不能解决的事件吗？
1：链表天生就具备动静扩容的特点，不须要像动静数组那样先申请一个更大的空间，而后将原空间内的数据拷贝到新空间；可能防止内存空的大量节约
2：链表不须要一块间断的内存空间，它通过指针将一组零散的内存块串联起来应用，所以如果咱们申请一个1000M大小的链表，只有内存残余的可用空间大于1000M，便不会呈现问题。
然而需注意：存储同样的数据，链表要比数组消耗内存！
2、链表分类
链表依据其结点之间的连贯模式咱们又可分为：单链表，双向链表，循环链表，双向循环链表
2.1、单链表
单链表就是咱们刚刚讲到的链表的最根本的构造，链表通过指针将一组零散的内存块串联在一起。。如图所示，咱们把这个记录下个结点地址的指针叫作后继指针 next ，如果链表中的某个节点为p，p的下一个节点为q，咱们能够示意为：p.next=q
链表中有两个结点是比拟非凡的，它们别离是第一个结点和最初一个结点。咱们习惯性地把第一个结点叫作头结点，把最初一个结点叫作尾结点。其中，头结点用来记录链表的基地址,有了它，咱们就能够遍历失去整条链表。而尾结点非凡的中央是：指针不是指向下一个结点，而是指向一个空地址 NULL，示意这是链表上最初一个结点。
与数组一样，链表也反对数据的查找、插入和删除操作。
在进行数组的插入、删除操作时，为了放弃内存数据的连续性，须要做大量的数据搬移，所以工夫复杂度是 O(n)。而在链表中插入或者删除一个数据，咱们并不需要为了放弃内存的连续性而搬移结点，因为链表的存储空间自身就不是间断的。所以，在链表中插入和删除一个数据是十分疾速的。
如图所示，针对链表的插入和删除操作，咱们只须要思考相邻结点的指针扭转，所以插入删除的工夫复杂度是 O(1)。
然而，无利就有弊。链表要想随机拜访第 k 个元素，就没有数组那么高效了。因为链表中的数据并非间断存储的，所以无奈像数组那样，依据首地址和下标，通过寻址公式就能间接计算出对应的内存地址，而是须要依据针一个结点一个结点地顺次遍历，直到找到相应的结点，所以，链表随机拜访的性能没有数组好，查问的工夫复杂度是O(n)。
2.2、双向链表
单向链表只有一个方向，结点只有一个后继指针 next。而双向链表，顾名思义，它反对两个方向，每个结点不止有一个后继指针 next 指向前面的结点，还有一个前驱指针 prev 指向后面的结点，如图所示
从图中能够看进去，双向链表须要额定的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。尽管两个指针比拟节约存储空间，但能够反对双向遍历，这样也带来了双向链表操作的灵活性，比方
1：能够在O(1)工夫内找到给定结点的前驱节点，而对于单链表则须要O(n)的工夫
2：依据索引来查找元素时可极大晋升查找效率
.....
在很多场景下双向链表都比单向链表更加高效，这就是为什么在理论的软件开发中，双向链表只管比拟费内存，但还是比单链表的利用更加宽泛的起因。如果你相熟 Java 语言，你必定用过LinkedHashMap 这个容器。如果你深入研究 LinkedHashMap 的实现原理，就会发现其中就用到了双向链表这种数据结构。
实际上，这里有一个更加重要思维就是用空间换工夫的设计思维。当内存空间短缺的时候，如果咱们更加谋求代码的执行速度，咱们就能够抉择空间复杂度绝对较高、但工夫复杂度绝对很低的算法或者数据结构。相同，如果内存比拟紧缺，比方代码跑在手机等存储容量小的设施上，这个时候，就要反过来用工夫换空间的设计思路。比方最典型的缓存零碎就是一个用空间换工夫的思维。
2.3、循环链表
循环链表是一种非凡的单链表。实际上，循环链表也很简略。它跟单链表惟一的区别就在尾结点。咱们晓得，单链表的尾结点指针指向空地址，示意这就是最初的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该能够看进去，它像一个环一样首尾相连，所以叫作“循环”链表，和单链表相比，循环链表的长处是从链尾到链头比拟不便。当要解决的数据具备环型构造特点时，就特地适宜采纳循环链表，循环链表的构造如图所示
2.4、双向循环链表
理解了循环链表和双向链表，如果把这两种链表整合在一起就是一个双向循环链表
3、小结&实战
3.1、链表数组比照
数组和链表是两种截然不同的内存组织形式。正是因为内存存储的区别，它们插入、删除、随机拜访操作的工夫复杂度正好相同，下图表明了链表和数组在插入删除和随机拜访上工夫复杂度的比照
3.2、206. 反转链表
字节跳动，腾讯，阿里，美团点评最近面试题，206. 反转链表
高频题
双指针迭代
class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr !=null) { ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; }}3.3、141. 环形链表
阿里，腾讯，百度最近面试题，141. 环形链表
快慢指针
public class Solution { public boolean hasCycle(ListNode head) { //非凡判断 if (head == null || head.next == null) { return false; } ListNode fast = head; ListNode slow = head; //两个指针别离下后走 while (true) { fast = fast.next.next; slow = slow.next; if (fast == null || fast.next == null) { return false; } if (fast == slow) { break; } } return true; }}4、综合案例
4.1、需要
在学习数组的时候咱们基于数组实现了一个List容器，反对数据的增加，批改，删除，查问等操作，明天学习完链表之后可能基于链表来实现一个LinkedList容器呢？
要求：
1：要求和动静数组ArrayList具备雷同的性能
2：请基于双向链表实现，
4.2、实现
（1）定义接口，com.itheima.linkedlist.inf.List，接口办法跟之前实现ArrayList时一样，只不过增加上泛型
package com.itheima.linkedlist.inf;/** * Created by 传智播客*黑马程序员. */public interface List<E> { /** * 返回容器中元素的个数 * @return */ int size(); /** * 判断容器是否为空 * @return */ boolean isEmpty(); /** * 查问元素在容器中的索引下标 * @param o 元素对象 * @return 在容器中的下标 不存在则返回-1 */ int indexOf(E o); /** * 判断容器是否蕴含某个特定的元素 * @param e * @return */ boolean contains(E e); /** * 将元素增加到容器结尾 * @param e 要增加的元素 * @return 是否增加胜利 */ boolean add(E e); /** * 向指定地位增加元素 * @param index 地位下标 * @param element 元素对象 */ void add(int index, E element); /** * 用指定的元素替换指定地位的数据 * @param index 指定的地位索引下标 * @param element 新的元素 * @return 原始的元素 */ E set(int index, E element); /** * 获取指定地位的元素 * @param index 索引下标 * @return 该地位的元素 */ E get(int index); /** * 移除指定地位的元素 * @param index 索引下标 * @return 被移除的元素 */ E remove(int index); /** * 革除容器中所有元素 */ void clear();}（2）创立接口实现：com.itheima.linkedlist.LinkedList，实现对应接口
（3）容器要基于双向链表实现，链表是由一个一个结点形成的，因而定义链表结点对象，编写一个动态的外部类
//定义链表结点对象private static class Node<E>{ E val; Node<E> prev; Node<E> next; //定义结构 public Node(Node<E> prev,E val,Node<E> next){ this.prev = prev; this.val = val; this.next = next; }}（4）定义相干的成员变量
//定义容器中元素的个数int size;//定义链表的头结点Node<E> first;//定义链表的尾结点Node<E> last;（5）实现size,isEmpty,indexOf,contains等办法的编写
@Overridepublic int size() { return size;}@Overridepublic boolean isEmpty() { return size == 0;}@Overridepublic int indexOf(E o) { int index = 0; //分状况 o是否为null，为null和不为null判断的形式不一样，null是用==，不为null用equals if (o == null) { for ( Node x = first;x!=null;x=x.next) { if (x.val == null) { return index; } index++; } }else { for ( Node x = first;x!=null;x=x.next) { if (o.equals(x.val)) { return index; } index++; } } return -1;}@Overridepublic boolean contains(E e) { return indexOf(e) != -1;}（6）实现add办法的编写
@Overridepublic boolean add(E e) { //增加是将元素值增加到链表尾部 linkLast(e); return true;}private void linkLast(E e) { Node l = last; Node newNode = new Node(l,e,null); last = newNode; if (l==null) { //第一次增加 first = newNode; }else { l.next = newNode; } size++;}@Overridepublic void add(int index, E element) { //查看索引 checkIndex(index); if (index == size) { linkLast(element); }else { linkBefore(element,node(index)); }}/** * 在指定结点前增加一个元素 * @param element * @param node */private void linkBefore(E element, Node<E> node) { Node<E> prev = node.prev; Node<E> newNode = new Node<E>(prev,element,node); node.prev = newNode; if (prev == null) { first = newNode; }else { prev.next = newNode; } size++;}/** * 查找索引为index的结点 * @param index * @return */private Node<E> node(int index){ //折半查找 if ( index < (size >> 1)) { //从头开始查找 Node<E> f = first; for (int i = 0;i< index;i++) { //i<index留神不能是i<=index 因为当i=index-1时 f=f.next其实f曾经指向了索引为index地位的元素了 f = f.next; } return f; }else { //从尾开始查找 Node<E> l = last; for (int i=size-1;i> index;i--) {//同上 l = l.prev; } return l; }}private void checkIndex(int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("index"+index+",size="+size); }}（7）实现set，get办法的编写
/** * 替换指定索引地位的元素 * @param index 指定的地位索引下标 * @param element 新的元素 * @return */@Overridepublic E set(int index, E element) { isElementIndex(index); Node<E> oldNode = node(index); E oldVal = oldNode.val; oldNode.val = element; return oldVal;}private void isElementIndex(int index) { if (index < 0 || index >=size) { throw new IndexOutOfBoundsException("index="+index+",size="+size); }}@Overridepublic E get(int index) { isElementIndex(index); return node(index).val;}（8）实现remove办法的编写
@Overridepublic E remove(int index) { isElementIndex(index); Node<E> node = node(index); return unlink(node);}private E unlink(Node<E> node) { Node<E> prev = node.prev; Node<E> next = node.next; E val = node.val; node.val = null; //node是头结点 if (prev == null) { first = next; }else { prev.next = next; node.prev = null; } //node是尾结点 if (next == null) { last = prev; }else { next.prev = prev; node.next = null; } size--; return val;}（9）实现clear，toString办法的编写
@Overridepublic void clear() { for (Node l = first;l!=null;) { Node next = l.next; l.val = null; l.prev = null; l.next = null; l = next; } first = last = null; size=0;}@Overridepublic String toString() { //输入 1->2->Null格局的数据 StringBuilder stringBuilder = new StringBuilder(); for (Node l=first;l!=null;l = l.next) { stringBuilder.append(l.val).append("->"); } stringBuilder.append("Null"); return stringBuilder.toString();}（10）编写测试类：com.itheima.linkedlist.LinkedListTest
public static void main(String[] args) { List list = new LinkedList(); list.add(1); list.add(2); list.add(3); System.out.println("容器内元素为:"+list); // 1->2->3->Null System.out.println("容器内元素个数:"+list.size()+"容器是否为空:"+list.isEmpty()); System.out.println("容器中是否蕴含3:"+list.contains(3)); list.add(0,4);// 4->1->2->3->Null System.out.println("容器内元素为:"+list); list.add(3,5);//4->1->2->5->3->Null System.out.println("容器内元素为:"+list); list.add(2,6);//4->1->6->2->5->3->Null System.out.println("容器内元素为:"+list); System.out.println("获取索引为0的元素:"+list.get(0)); System.out.println("获取索引为5的元素:"+list.get(5)); System.out.println("获取索引为2的元素:"+list.get(2)); list.remove(0);//1->6->2->5->3->Null System.out.println("容器内元素为:"+list); list.remove(3);//1->6->2->3->Null System.out.println("移除后容器内元素为:"+list); list.clear(); System.out.println("清空后为:"+list);}查看输入后果！
容器内元素为:1->2->3->Null
容器内元素个数:3容器是否为空:false
容器中是否蕴含3:true
容器内元素为:4->1->2->3->Null
容器内元素为:4->1->2->5->3->Null
容器内元素为:4->1->6->2->5->3->Null
获取索引为0的元素:4
获取索引为5的元素:3
获取索引为2的元素:6
容器内元素为:1->6->2->5->3->Null
移除后容器内元素为:1->6->2->3->Null
清空后为:Null
本文由传智教育博学谷 - 狂野架构师教研团队公布，转载请注明出处！
如果本文对您有帮忙，欢送关注和点赞；如果您有任何倡议也可留言评论或私信，您的反对是我保持创作的能源