目录

引入：

链表的基础概念

链表的基本操作

查找节点

更新节点

插入节点

删除节点

数组和链表

---

引入：

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

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

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

链表的基础概念

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

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

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

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

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

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

如图所示：

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

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

何为随机存储呢？

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

如图所示：

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

链表的基本操作

查找节点

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

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

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

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

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

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

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

 

更新节点

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

插入节点

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

尾部插入

中间插入

头部插入

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

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

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

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

 

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

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

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

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

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

​
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指针指向空即可。

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

 

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

 

 需要注意的是，许多高级语言如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;
    }

数组和链表

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

我们来对比一下性能：

	查找	更新	插入	删除
数组	O（1）	O（1）	O（n）	O（n）
链表	O（n）	O（1）	O（1）	O（1）

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