Java数据结构-------单链表（图解增删改查详细实现，附反转链表实现）

拼搏现实的明天。 2023-10-02 12:14 18阅读 0赞

![b3cd3475ec6ca0a6ff7b57fa6ed26d7f.png][]

**目录**

1.什么是链表？

2.单链表的基本功能和结构

3.单链表基本功能代码具体实现

1.清空链表，获取链表长度，判断链表是否为空

2.获取指定位置的元素

3.像链表中添加元素t

4.向指定位置i处插入元素t

5.删除指定位置i处的元素，并返回该元素

6.查找元素第一次出现的位置

7.反转链表

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

## 1.什么是链表？ ##

一：链表是什么  
1、链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，有一系列结点（地址）组成，结点可动态的生成。

2、结点包括两个部分：（1）存储数据元素的数据域（内存空间），（2）存储指向下一个结点地址的指针域。

3、相对于线性表顺序结构，操作复杂。

4.链表分为 （1）单链表 （2）双链表 （3）单向循环链表 （4）双向循环链表  
画个图让大家更好理解两者的优缺点![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16][]

## 2.单链表的基本功能和结构 ##

public class Linklist<T>  {
        //记录头结点
        private Node head;
    
        //记录链表的长度
        private int N;
    
        //结点类
        private class Node{
            //存储数据
            T item;
            //下一个结点
            Node next;
    
            public Node(T item, Node next){
                this.item=item;
                this.next=next;
            }
        }
        //构造方法
        public Linklist() {
            //初始化元素个数
            this.N=0;
            //初始化头结点
            this.head=new Node(null,null);
        }

解析： 单链表需要一个头结点和一个int类型的变量N记录元素的个数。因为一个结点需要有数据域和指针域，所以我们单链表内需要有一个内部类Node表示结点。因为我们还不能确定存放的数据类型，所以用泛型T表示存放的数据类型的成员变量，因为next指的是下一个结点，所以需要一个Node类型的成员变量。链表的构造方法刚开始没有元素所以让N为0，头结点head的数据域不存放元素所以为null，还没有插入元素所以它的next也为null

下面是单链表需要实现的基本API

<table style="width:591px;"> 
 <tbody> 
  <tr> 
   <td> <pre>public void clear()</pre> </td> 
   <td style="width:338px;">清空链表</td> 
  </tr> 
  <tr> 
   <td> <pre>public int getN()</pre> </td> 
   <td style="width:338px;">获取链表的长度</td> 
  </tr> 
  <tr> 
   <td> <pre>public boolean isEmpty()</pre> </td> 
   <td style="width:338px;"> <pre>判断链表是否为空</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public T get(int i)</pre> </td> 
   <td style="width:338px;"> <pre>获取指定位置i的元素</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public void add(T t)</pre> </td> 
   <td style="width:338px;"> <pre>向链表中添加元素t</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public void insert(int i,T t)</pre> </td> 
   <td style="width:338px;"> <pre>向指定位置i处添加元素</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public T remove(int i)</pre> </td> 
   <td style="width:338px;"> <pre>删除指定位置处i处的元素,并返回被删除的元素</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public int indexOf(T t)</pre> </td> 
   <td style="width:338px;"> <pre>查找元素第一次出现的位置</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public void reverse()</pre> </td> 
   <td style="width:338px;"> <pre>用来反转整个链表</pre> </td> 
  </tr> 
 </tbody> 
</table>

## 3.单链表基本功能代码具体实现 ##

### 1.清空链表，获取链表长度，判断链表是否为空 ###

//清空链表
        public void clear(){
            head.next=null;
            this.N=0;
        }
    
        //获取链表的长度
        public int getN(){
            return N;
        }
    
        //判断链表是否为空
        public boolean isEmpty(){
            return N==0;
        }

解析：因为链表的查询需要从头结点一个个next查找下去，如果头结点的next直接为null，那我们就什么也查不到了，链表就变成空，同时让N为0。获取链表的长度直接返回N的值即可。判断链表是否为空我们返回N是否等于0即可。

### 2.获取指定位置的元素 ###

//获取指定位置i的元素
        public T get(int i){
            //通过循环，从头结点往后找
            Node n=head.next;
            for (int j = 0; j <i; j++) {
               n=n.next;
            }
            return n.item;
        }

解析：我们首先建立一个Node结点n并将它赋值为头结点的下一个结点，通过for循环，我们一个一个遍历下去直到找到我们指定的位置i。这里我们要注意循环的判定条件，我们走一次循环就走一个结点，因为我们是从第一个结点开始，所以需要走i-1次循环，如果你的n设的是head，那我们就要走i次循环，判定条件应为j<=i。

### 3.像链表中添加元素t ###

//向链表中添加元素t
        public void add(T t){
            //找到当前最后一个结点
            Node n=head;
            while (n.next!=null){
                n=n.next;
            }
            //创建新节点保存元素
            Node node = new Node(t,null);
            n.next=node;
            //元素个数加1
            N++;
        }

解析：添加元素，我们需要找到最后一个结点，此时它的next是null，我们设一个结点n赋值为头结点，用while循环不断更新为下一个结点，当它的下一个结点为null时说明我们n已经成为了最后一个结点。得到最后一个结点后我们新建立一个结点node，它的数据域填充我们的需要插入的元素t，让它接在我们的最后一个结点后，然后让N加一，我们的添加就完成了。要在尾部添加元素，单链表必须要从头遍历到尾部，在这方面单链表比不上顺序表。但插入到具体的位置的操作单链表却具有顺序表不具有的优点。

### 4.向指定位置i处插入元素t ###

//向指定位置i处添加元素
        public void insert(int i,T t){
            //找到i位置前一个结点
           Node pre=head;
           for(int j=0;j<=i-1;i++){
               pre=pre.next;
           }
           //找到i位置的结点
            Node curr =pre.next;
           //创建新节点,并且新结点需要指向原来i位置的结点
            Node newNode=new Node(t,curr);
            //原来i位置的前一个节点指向新结点即可
            pre.next=newNode;
            N++;
        }

解析:在指定位置插入元素，类似我们上面在结尾添加元素，但插入时我们不仅要让i位置前一个结点next新节点，还要让新结点的next指向i位置后一个结点。我们先通过遍历找到i位置的前一个结点并记录为pre，此时我们pre.next就是我们i位置处的结点，我们保存为curr。这时我们创建新节点newNode，它的数据域为t，指针域为我们的curr，也就是原来i位置上的结点，这时我们再让pre指向newNode就完成了我们的插入操作。可以看看下面的图解步骤![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

**对于指定位置的插入操作，顺序表需要对大量的元素进行移动，效率很低，如果你想在下标为0处插入，甚至需要整个数组进行后移。而链表相对于顺序表最显著的优点就在这，它在插入时完全不需要考虑移动元素，因为它的地址是不连续的，它可以在任意地方开辟空间生成结点。**

###  5.删除指定位置i处的元素，并返回该元素 ###

//删除指定位置处i处的元素,并返回被删除的元素
        public T remove(int i){
            Node pre=head;
              //先找到i处前一个结点
            for (int j = 0; j <= i - 1; j++) {
                pre=pre.next;
            }
               //记录i处的结点
            Node n=pre.next;
                //让i处前一个结点指向i处后一个结点
            pre.next=n.next;
            N--;
            return n.item;
        }

解析：删除的操作很简单，我们同样通过遍历得到i处的前一个元素并记录为pre，再将pre.next也就是i处的结点记录为n。然后我们让n.next赋值给pre.next，也就是让i处前一个结点（pre）指向i处后一个结点

下面为简易图解![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

### 6.查找元素第一次出现的位置 ###

//查找元素第一次出现的位置
        public int indexOf(T t){
            Node pre=head;
            for (int i = 0;pre.next!=null; i++) {
                pre=pre.next;
                if(pre.item==t) return i;
            }
            return -1;
        }

解析：从头开始遍历，每次判断是否是我们需要查找的结点，如果是直接返回，如果遍历完仍未找到，则返回-1，表示链表中没有需要查找的元素。

### 7.反转链表 ###

**该内容为补充内容，反转链表不属于链表的功能，但我们也需要了解，技多不压身。**

//用来反转整个链表
        public void reverse(){
            //判断当前链表是否为空，如果为空则结束运行
            if(isEmpty())   return;
            reverse(head.next);
        }
    
        //反转指定的某个结点
        public Node reverse(Node curr){
            if(curr.next==null){
                head.next=curr;
                return curr;
            }
            //递归的反转当前结点curr的下一个结点，返回值就是链表反转后，当前结点的上一个结点
            Node pre=reverse(curr.next);
            //让返回的结点的下一个结点变为当前结点curr
            pre.next=curr;
            //把当前的下一个结点变为null
            curr.next=null;
            return curr;
        }

**解析：这个代码最好通过debug一步步去理解它，它会在Node pre=reverse(curr.next)这个地方一直进入循环，因为要满足if循环中的某个结点curr.next为null，那么只有链表中的最后一个结点，此时让头结点指向它，也就是下图中的第一次递归完的情况。但我们要清楚在我们将最后一个结点传入这个方法时，此时是在倒数第二个结点为curr的情况下，因为此时curr这个结点在这个方法体中，在if判断中它不成立，因为它后面还有链表最后一个结点，前面的结点也是如此，所以if判断条件都不通过，但此时curr传入它的next进入循环后，我们姑且称之为尾结点，尾结点在if判断中是成立的，它在完成反转后，也就是让头结点指向它后，将自己返回。这时尾结点被一个pre接收，然后pre.next=curr，也就是让最后一个结点指向倒数第二个结点，接着将倒数第二个结点返回，然后继续递归，如图：**![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

总结：单链表和顺序表一样属于基础数据结构，需要我们掌握并熟悉它的功能，反转链表部分我的表达可能不是很清楚，不明白的同学可以自己画图一步步debug，毕竟数据结构很抽象，需要我们画图才更易理解

![f704dcb374c688a57eae9f5dd97c3655.png][]

[b3cd3475ec6ca0a6ff7b57fa6ed26d7f.png]: https://img-blog.csdnimg.cn/img_convert/b3cd3475ec6ca0a6ff7b57fa6ed26d7f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4b733d52e02d4ddda0bd401eac4c8e3d.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5omn5qKX,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/570c949228974f4ca9eef98c5ba4e07e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5omn5qKX,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/837e246ec8da43ed92f9e58112b6d68d.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5omn5qKX,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/85931477d41649d6959d1fce7782e410.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5omn5qKX,size_20,color_FFFFFF,t_70,g_se,x_16
[f704dcb374c688a57eae9f5dd97c3655.png]: https://img-blog.csdnimg.cn/img_convert/f704dcb374c688a57eae9f5dd97c3655.png