【学点数据结构和算法】02-链表Alice菌的博客-

写在前面： 博主是一名软件工程系大数据应用开发专业大二的学生，昵称来源于《爱丽丝梦游仙境》中的Alice和自己的昵称。作为一名互联网小白，写博客一方面是为了记录自己的学习历程，一方面是希望能够帮助到很多和自己一样处于起步阶段的萌新。由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！个人小站:https://alices.ibilibili.xyz/ , 博客主页:https://alice.blog.csdn.net/
尽管当前水平可能不及各位大佬，但我还是希望自己能够做得更好，因为一天的生活就是一生的缩影。我希望在最美的年华，做最好的自己！

        上一篇博客博主为大家带来了数组的内容，本篇博客我们来学习另外一个重要的数据结构——链表!

概念

        链表是一种链式数据结构，由若干节点组成，每个节点包含当前节点的数据和指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查找链表节点的时间复杂度是O(n)，中间插入、删除节点的时间复杂度是O(1)。

分类

        根据不同的结构，链表可以有多种分类。常见的有单向链表，双向链表，循环链表，双向循环链表，静态链表和动态链表…

1、单向链表

        最简单的就是单向链表。单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指 向下一个节点的指针next。

        链表的第1个节点被称为头节点，最后1个节点被称为尾节点，尾节点的next指针指向空。

        与数组按照下标来随机寻找元素不同，对于链表的其中一个节点A，我们只能根据节点A的next指针来找到该节点的下一个节点B，再根据节点B的next指针找到下一个节点 C……

特点

• 在内存中，元素的空间可以在任意地方，空间是分散的，不需要连续
• 链表中的元素都有两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址(只能next)。每一个数据都会保存下一个数据的内存的地址，通过此地址可以找到下一个数据
• 查找数据时效率低,时间复杂度为O(N)
• 空间不需要提前指定大小，是动态申请的，根据需求动态的申请和删除内存空间，扩展方便，故空间的利用率较高
• 任意位置插入元素和删除元素效率较高，时间复杂度为O(1)
• 链表的空间是从堆中分配的

2、双向链表

概念

        相比于单链表，双向链表有两个指针，一个指向前一个节点，一个指向后一个节点。可以通过next()获取后一个节点，也可以通过prev()快速找到前一结点。

优势

• 插入删除不需要移动元素外，可以原地插入删除
• 查找时可以借用二分法的思想，从head（首节点）向后查找操作和last（尾节点）向前查找操作同步进行，这样双链表的效率可以提高一倍(双向遍历)

劣势

        1、从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，而长度为n就需要 n*length（这个指针的length在32位系统中是4字节，在64位系统中是8个字节） 的空间，这在一些追求时间效率高应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这是一种工程总体上的衡量。

        2、增加删除节点复杂，需要多分配一个指针存储空间。

3、循环链表

概念

        链表的两头连接，形成了一个环状链表，称为循环链表。

特点

• 从任何一个节点出发都能到链表中的所有节点，这一点单向链表做不到。
• 没有空指针的节点。单循环链表理论上来说是没有头节点和尾节点的，每个节点的next指针都有指向。
• 判断链表结束条件发生变化。单向链表是判断节点为空即为结束，但是循环链表判断链表循环结束的条件是哨兵节点的next和某个节点相等，即为结束。

4、双向循环链表

概念

        双向链表的两头连接，形成了一个环状链表，称为循环链表。

特点

• 双向循环链表的节点不仅包含指向下一个节点的指针(next)，还包含指向前一个节点的指针(prev)
• 双向循环链表的头指针head的前一个节点指向end，尾节点end的后一个节点指向head。

优势

• 相比单链表，双向循环链表所有基本操作均快于单链表(java源码的LinkList类就是双向循环链表)
• 能直接获取节点的前一个节点，十分灵活

劣势

        相比单链表，双链表的空间内存明显要大很多。

        双链表的设计应用了算法设计的“空间换时间”思想，通过消耗更多的空间来缩小操作的时间复杂度。

5、静态链表

概念

        所谓静态链表，就是用数组来实现链式存储结构，目的是方便在不设指针类型的高级程序设计语言中使用链式结构。

特点

• 和动态链表一样，删除和插入元素时间复杂度低
• 和数组一样，需要提前分配一块较大的空间

6、动态链表

概念

        动态链表是用内存申请函数（malloc/new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。

特点

• 删除和插入元素时间复杂度低
• 访问数据效率低，只能通过指针顺序访问

代码操作

        下面展示的是单链表的相关代码操作，其他类型的链表操作感兴趣的朋友可以自行Google/百度。

/**  * @Author: Alice菌  * @Date: 2020/6/7 20:35  * @Description:  */ public class OwnLinkedList { // 头结点指针 private Node head; // 尾节点指针 private Node last; // 链表实际长度 private int size; public void insert(int index,int data) throws Exception{ if (index <0 || index > size){ throw new IndexOutOfBoundsException("超出链表节点范围!"); }          Node insertedNode = new Node(data); if (size == 0){ // 空链表            head = insertedNode;            last = insertedNode; }else if (index == 0){ // 在头部插入             insertedNode.next = head;             head = insertedNode; }else if (size == index){ // 插入尾部             last.next = insertedNode;             last = insertedNode; }else { // 在中间插入 // 获取该位置的原节点             Node preNode = get(index - 1); // 新插入节点接替原节点的指针指向位置             insertedNode.next = preNode.next; // 原节点的指针指向新节点             preNode.next = insertedNode; } // 链表的长度+1         size++; } public Node remove(int index) throws Exception{ if (index <0 || index >= size){ throw new IndexOutOfBoundsException("超出链表节点范围!"); } // 创建一个节点对象,保存需要删除的节点         Node removedNode = null; if(index == 0){ //删除头节点             removedNode = head; //原头节点的位置后移             head = head.next; }else if (index == size-1){ // 删除尾节点 // 获取到尾节点的前一个元素prevNode             Node prevNode = get(index - 1);             removedNode = prevNode.next; // 将prevNode的指针指向null[间接删除了尾节点]             prevNode.next = null; // 现在尾节点变成了prevNode             last = prevNode; }else { // 删除的是中间节点 // 获取到需要删除节点的前一个节点preNode             Node preNode = get(index - 1); // 获取到需要删除节点的后一个节点nextNode             Node nextNode = preNode.next.next;             removedNode = preNode.next; // 将preNode的指针指向nextNode[间接删除了中间节点]             preNode.next = nextNode; } // 链表的长度-1         size--; // 返回被删除的节点 return removedNode; } /**      * 链表查找元素      * @param index 查找的位置      * @return 返回获取到的Node节点元素      * @throws Exception 抛出异常      */ public Node get(int index) throws Exception{ if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("超出链表节点范围!"); } // 获取到头结点         Node temp = head; // 通过遍历，依次获取到每个节点 for (int i = 0; i < index; i++) {             temp = temp.next; } return temp; } public void output(){          Node temp = head; while (temp!=null) { // 打印节点的内容data             System.out.println(temp.data); // 不断通过一个节点的next指针，找到下一个节点             temp = temp.next; } } /**      * 链表节点      */ private static class Node{ // 当前的数据 int data; // 指针，指向下一个节点         Node next; Node(int data) { this.data = data; } } public static void main(String[] args) throws Exception { // 新建一个链表对象         OwnLinkedList ownLinkedList = new OwnLinkedList(); // 添加元素         ownLinkedList.insert(0,3);         ownLinkedList.insert(0,4);         ownLinkedList.insert(2,9);         ownLinkedList.insert(3,5);         ownLinkedList.insert(1,6); // 删除头节点         ownLinkedList.remove(0); // 打印链表内容         ownLinkedList.output(); //6 //3 //9 //5 } } 

总结： 数组 VS 链表

        从表格可以看出，数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些。

        相反地，链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更合适一些。

        如果以上过程中出现了任何的纰漏错误，烦请大佬们指正😅

        受益的朋友或对大数据技术感兴趣的伙伴记得关注支持一波🙏

        希望我们都能在学习的道路上越走越远😉