链表的认识

忘是亡心i 2023-09-26 22:47 96阅读 0赞

**目录**

引入：

链表的基础概念

链表的基本操作

查找节点

更新节点

插入节点

删除节点

数组和链表

--------------------

## **引入：** ##

前面我们已经讲了重要的一种数据结构——数组，如果说数组是**方便读取数据**，那么今天所学习的链表便是**方便写入数据**的数据结构，为什么这么说呢？让我们走进今天的链表学习。

首先让我们来看一个最基础的单向链表：

![cf40db07a054430bac05c65f0a2bf474.png][]

由图可见，链表和数组数据结构最主要的区别是链表是单线联络的，就像是工厂的产品，一般都是生产之后，然后交给超市等批发商，最后才能到达消费者的手中，产品的运输，就像是链表。

### **链表的基础概念** ###

链表(linked list)是一种在物理中**非连续 ，非顺序**的数据结构，由若干节点(node)所组成。

由上图可知，单向链表又包含了两个部分，一是存放数据的变量data，另一个是指向下一个节点的指针next。

public static class Node{
        int data;
        Node next;
    }

链表的第一个节点称为头节点，最后一个节点叫做尾节点，尾节点的next指针指向NULL。

那么，有的人就要发问了，链表总是通过一个节点寻找到下一个节点，那如何通过链表的一个节点寻找到它的前一个结点呢？

这就用到了**双向链表：**双向链表不仅拥有原来的data和next，还拥有指向前一个节点的指针prev。

如图所示：

![e81939a7d3884f0d88890d0bf2775636.png][]

接下来我们来看一下链表在内存中的存储方式：

如果说数组在内存中的存储方式为顺序存储，那么链表在内存中的存储方式就是**随机存储**。

何为随机存储呢？

上一篇博文中我们讲到数组在内存中的存储存储方式是**顺序存储**。而链表则是采用了**见缝插针**的方式。链表的每一个节点分配在内存中的不同位置，用next指针联系起来，这样可以灵活的运用零碎的内存空间。

如图所示：

![601dbf11a38e49e18a880f35fc1db269.png][]

（其中：灰色表示没有数据，绿色表示其他数据，红色表示该链表数据，直线指向为next指针指向，为3->1->6->4->8->7->6）。

## 链表的基本操作 ##

### **查找节点** ###

还是上面那个例子，如果工厂发现某一产品有质量问题，那么应该如何找到有质量问题的产品呢？

答案就是先从工厂开始找，无果，则去下一级经销商中寻找，无果，则通过下一级经销商找到下下一级经销商，若还没有，就继续寻找，最坏的结果就是直至找到最底一级——客户。由此可见，该查找方式就是一级一级寻找，链表亦是如此。

链表的查找方式就是**从头结点开始，向后一个一个节点逐一查找**。

例如给出一个链表，需要查找从头结点开始的第3个节点

1.第一步，将指针定位在头节点。

![bb6c7e51ff7444ca82b4c43367e51d86.png][]

2.第二步，根据头结点的next ，定位到第二个节点。

![8d9a7e28613b4cc7a77b8ad079779817.png][]

3.第三步，根据第二个节点的next指针，定位到第三个节点，查找完毕。

![c01f7aee5f73416e80729282da6052b6.png][]

### **更新节点** ###

如果不考虑查找结点的过程，链表的更新会像数组一样简单，**直接把旧数据改成新数据**即可。

![c2f4e283848d4ec3a191260d46bf00f4.png][]

### **插入节点** ###

与数组类似，链表插入节点时，同样分为三种情况。

**尾部插入**

**中间插入**

**头部插入**

尾部插入，是最简单的情况，把最后一个节点的next指针指向新插入的节点即可。

![571e3b4be56c4cb99bbea5c130666a48.png][]

头部插入，可以分成两个步骤。

第一步，把新节点的next指针指向原先的头节点。

第二步，将新节点设置为链表的头节点。

![e65d8adec01c444f9ea1516f7e30b888.png][]

中间插入，同样分为两个步骤。

第一步，新节点的next指针，只想插入位置的节点。

第二步，插入位置前置节点的next指针，指向新节点。

![1c18c90cb5ab408ba48348ebfbe86d57.png][]

**只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要考虑像数组一样的扩容问题。**

下面我们来看一下插入操作的代码：

public class ClassNode{
       //链表实际大小
       private int size;
       //头结点指针
       private Node head;
       //尾结点指针
       private Node last;
     
       public static class Node{
           int data;//数据域
           Node next;//节点指针
           Node(int data){
               this.data = data;
           }
    
       //data为插入元素，index为插入位置
       public void insert(int data,int index) 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 prevNode = get(index-1);//通过get函数找到插入位置的前一个节点
                insertedNode.next = prevNode.next;
                prevNode.next = insertedNode;
            }
    
            size++;
    
        }
    }

##  ##

附：链表查找元素的函数get（）

//find-查找的位置
     public Node get(int find) throws Exception{
         
       if(find < 0 || find > size){
                throw new IndexOutOfBoundsException("超出链表结点范围！");
            }
    
            Node temp = head;
    
            for(int i=0; i<find; i++){
                temp = temp.next;
            }
    
            return temp;
        }

### 删除节点 ###

链表的删除同样分为三种情况：

**尾部删除**

**头部删除**

**中间删除**

尾部删除，把倒数第二个节点的next指针指向空即可。

![bb9e17c6ca8d43b4ad83f980555176a0.png][]

头部删除，也很简单，把链表的头节点设为原先头结点的next指针即可。

![a31410698b44462fabd27452c6858a6c.png][]

中间删除，也同样简单，把删除节点的前置节点的next指针，指向删除结点的下一个节点即可。

![750237933ae7499c9fb7ea331098feaf.png][]

需要注意的是，许多高级语言如java，拥有**自动化的垃圾回收装置**，所以不**用刻意去释放删除的节点**，只要没有外部引用它们，被删除的节点就会自动释放。

代码如下：

//pos:删除的位置
        public Node remove(int pos) throws Exception{
    
            if(pos < 0 || pos > size){
                throw new IndexOutOfBoundsException("超出链表节点范围！");
            }
    
            Node removedNode = null;
    
            if(pos == 0){
                //删除头节点
                removedNode = head;
                head.next = head;
            }else if(pos == size-1){
                //删除尾节点
                Node prevNode = get(pos - 1);
                removedNode = prevNode.next;
                prevNode.next = null;
            }else{
                //删除中间节点
                Node prevNode = get(pos - 1);
                Node nextNode = prevNode.next.next;
                removedNode = prevNode.next;
                prevNode.next = nextNode;
            }
    
            size--;
            return removedNode;
        }

## **数组和链表** ##

根据对于数组和链表的学习，我们知道它们都属于线性结构，而**它们没有绝对的好与坏**。

我们来对比一下性能：

这个表格也印证了一开始的结论：**读操作多，写操作少用数组，反之用链表**。

![6fa0eff7fe654c7cad5c2b0de9c279e8.jpeg][]

[cf40db07a054430bac05c65f0a2bf474.png]: https://img-blog.csdnimg.cn/cf40db07a054430bac05c65f0a2bf474.png
[e81939a7d3884f0d88890d0bf2775636.png]: https://img-blog.csdnimg.cn/e81939a7d3884f0d88890d0bf2775636.png
[601dbf11a38e49e18a880f35fc1db269.png]: https://img-blog.csdnimg.cn/601dbf11a38e49e18a880f35fc1db269.png
[bb6c7e51ff7444ca82b4c43367e51d86.png]: https://img-blog.csdnimg.cn/bb6c7e51ff7444ca82b4c43367e51d86.png
[8d9a7e28613b4cc7a77b8ad079779817.png]: https://img-blog.csdnimg.cn/8d9a7e28613b4cc7a77b8ad079779817.png
[c01f7aee5f73416e80729282da6052b6.png]: https://img-blog.csdnimg.cn/c01f7aee5f73416e80729282da6052b6.png
[c2f4e283848d4ec3a191260d46bf00f4.png]: https://img-blog.csdnimg.cn/c2f4e283848d4ec3a191260d46bf00f4.png
[571e3b4be56c4cb99bbea5c130666a48.png]: https://img-blog.csdnimg.cn/571e3b4be56c4cb99bbea5c130666a48.png
[e65d8adec01c444f9ea1516f7e30b888.png]: https://img-blog.csdnimg.cn/e65d8adec01c444f9ea1516f7e30b888.png
[1c18c90cb5ab408ba48348ebfbe86d57.png]: https://img-blog.csdnimg.cn/1c18c90cb5ab408ba48348ebfbe86d57.png
[bb9e17c6ca8d43b4ad83f980555176a0.png]: https://img-blog.csdnimg.cn/bb9e17c6ca8d43b4ad83f980555176a0.png
[a31410698b44462fabd27452c6858a6c.png]: https://img-blog.csdnimg.cn/a31410698b44462fabd27452c6858a6c.png
[750237933ae7499c9fb7ea331098feaf.png]: https://img-blog.csdnimg.cn/750237933ae7499c9fb7ea331098feaf.png
[6fa0eff7fe654c7cad5c2b0de9c279e8.jpeg]: https://img-blog.csdnimg.cn/6fa0eff7fe654c7cad5c2b0de9c279e8.jpeg