Java实现单链表及基本功能

亦凉 2023-02-14 02:41 19阅读 0赞

## 一、 前言 ##

最近开始学习数据结构和算法。之所以说是学习而不是复习，还是因为自己这方面太薄弱了。长时间以来感觉自己都忘得差不多了。希望这次以写博客的方式能够记录自己这段时间的成长，也方便以后自己有遗忘再回到这复习吧，防止再花额外的时间去寻找相关的知识点。  
  因为在部分算法题中用到了栈的思想，那么就不得不提链表。数组和链表都是线性存储结构的基础，栈和队列都是线性存储结构的应用。本文这次主要讲解的是单链表的基础知识点。

## 二、回顾与知新 ##

在学习链表之前，我们先回顾一下数组。因为有数组作为比较对象后，就会很容易理解链表这种存储结构了。

#### 2.1数组说明 ####

数组是一种连续存储线性结构，元素类型相同，大小相等。

备注：以上这段话中，“大小相等”有点疑惑，猜测的意思是内存中每个元素占用内存大小相等，如果有读者知道还请您在评论区指教。  
![在这里插入图片描述][20200531155310714.png]  
**数组的优点：**

*  查询速度快

**数组的缺点：**

*  插入和删除效率低。
 *  必须先确定数组的大小，可能浪费内存（部分内存未使用）。
 *  内存空间要求高，必须有足够的连续内存空间。
 *  不能动态拓展（数组大小是固定的）。

#### 2.2链表说明 ####

看完了数组，回到我们的链表

链表是离散存储线性结构

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy_size_16_color_FFFFFF_t_70]  
**链表的优点：**

*  插入删除元素很快
 *  大小没有固定，拓展很灵活
 *  内存利用率高，不会浪费内存

**链表的缺点：**

*  查询速度很慢

链表相关术语介绍，依然通过上面那个图来标注说明：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy_size_16_color_FFFFFF_t_70 1]  
**确定一个链表我们只需要头指针，通过头指针就可以把整个链表都推导出来**

链表又分了好几类：

###### 单向链表： ######

特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。其中每个结点都有指针成员变量指向列表中的下一个结点

###### 双向链表： ######

它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

###### 循环链表： ######

能通过任何一个结点找到其他所有的结点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环  
**操作链表要时刻记住的是：**

*  结点中指针域指向的就是一个结点了！

## 三、Java实现链表 ##

算法：

*  遍历
 *  查找
 *  清空
 *  销毁
 *  求长度
 *  排序
 *  删除节点
 *  插入节点

首先，我们定义一个类作为结点，里面包含两个域：

*  数据域
 *  指针域

Node结点类代码：

/** * @program: Day1 * @description: 单向链表结点 * @author: sunzhen * @create: 2020-05-29 22:57 **/
    public class Node { 
    
        //数据域
        public Integer data;
    
        //指针域，指向下一个节点
        public Node next;
    
        public Node() { 
        }
    
        public Node(int data) { 
            this.data = data;
        }
    
        public Node(int data, Node next) { 
            this.data = data;
            this.next = next;
        }
    
    }

然后创建测试类（我将head结点定义在成员变量上）

**
     * @program: Day1
     * @description: 单向链表算法测试
     * @author: sunzhen
     * @create: 2020-05-29 23:07
     **/
    public class LinkedListTest { 
    
        //头结点
        private static Node head = new Node();
    
    }

#### 3.1增加节点 ####

向链表中插入数据：

*  找到尾节点进行插入
 *  即使头节点.next为null，不走while循环，也是将头节点与新节点连接的

/** * @Description: 添加数据 * @Param: [value] * @return: void * @Author: sunzhen * @Date: 2020/5/30 */
    public static void addData(int value) { 
        //初始化要加入的结点
        Node newNode = new Node(value);
    
        //临时结点
        Node temp = head;
    
        //找到尾节点
        while (temp.next != null) { 
            temp = temp.next;
        }
    
        //已经包括了头节点.next为null的情况了～
        temp.next = newNode;
    }

#### 3.2遍历链表 ####

上面我们已经编写了增加方法，现在遍历一下看一下是否正确。  
从首节点开始，不断往后面找，直到后面的节点没有数据：

/** * @Description: 遍历链表 * @Param: [head] * @return: void * @Author: sunzhen * @Date: 2020/5/30 */
    public static void traverse(Node head) { 
        //临时节点，从首节点开始
        Node temp = head.next;
    
        while (temp != null) { 
    
            if (temp.data != null) { 
                System.out.println(temp.data);
            }
    
            //继续下一个
            temp = temp.next;
        }
    }

#### 3.3获取链表的长度 ####

获取链表的长度就很简单了，遍历一下，每得到一个节点+1即可。

/** * @Description: 获取链表的长度 * @Param: [head] * @return: int * @Author: sunzhen * @Date: 2020/5/30 */
    public static int linkListLength(Node head) { 
        /*Node temp = head; int length = 0; while (temp.next != null) { length++; temp = temp.next; } return length;*/
    
        int length = 0;
    
        //临时节点，从首节点开始
        Node temp = head.next;
    
        // 找到尾节点
        while (temp != null) { 
            length++;
            temp = temp.next;
        }
    
        return length;
    
    }

#### 3.4插入节点 ####

插入一个节点到链表中，首先得判断这个位置是否是合法的，才能进行插入。  
找到想要插入的位置的上一个节点就可以了。

/** * @Description: 插入结点 * @Param: [head, index, value] * @return: void * @Author: sunzhen * @Date: 2020/5/30 */
    public static void insertNode(Node head, int index, int value) { 
        //首先需要判断指定位置是否合法，
        //插入的合法范围（包含头尾）：1 <-> 链表长度+1
        if (index < 1 || index > linkListLength(head) + 1) { 
            System.out.println("插入位置不合法。");
            return;
        }
    
        //临时节点，从头节点开始
        Node temp = head;
    
        //记录遍历的当前位置
        int currentPos = 0;
    
        //初始化要插入的节点
        Node insertNode = new Node(value);
    
        //这里循环成立的条件是小于等于用户能插入的最后一个位置（链表长度+1）
        while (currentPos <= linkListLength(head)) { 
    
            //找到上一个节点的位置了
            if ((index - 1) == currentPos) { 
    
                //temp表示的是上一个节点
    
                //将原本由上一个节点的指向交由插入的节点来指向
                insertNode.next = temp.next;
    
                //将上一个节点的指针域指向要插入的节点
                temp.next = insertNode;
    
                return;
    
            }
    
            currentPos++;
            temp = temp.next;
        }
    
    }

#### 3.5删除节点 ####

删除某个位置上的节点其实是和插入节点很像的， 同样都要找到上一个节点。将上一个节点的指针域改变一下，就可以删除了。

/** * @Description: 删除结点 * @Param: [head, index] * @return: void * @Author: sunzhen * @Date: 2020/5/30 */
    public static void deleteNode(Node head, int index) { 
        //首先需要判断指定位置是否合法，合法范围（包含头尾）： 1 <-> 链表长度
        if (index < 1 || index > linkListLength(head)) { 
            System.out.println("删除位置不合法。");
            return;
        }
    
        //临时节点，从头节点开始
        Node temp = head;
    
        //记录遍历的当前位置
        int currentPos = 0;
        
        while (temp.next != null) { 
    
            //找到上一个节点的位置了
            if ((index - 1) == currentPos) { 
    
                //temp表示的是上一个节点
    
                //temp.next表示的是想要删除的节点
    
                //将想要删除的节点存储一下
                Node deleteNode = temp.next;
    
                //想要删除节点的下一个节点交由上一个节点来控制
                temp.next = deleteNode.next;
    
    
                //Java会回收它，设置不设置为null应该没多大意义了(个人觉得,如果不对请指出哦～)
                deleteNode = null;
    
                return;
    
            }
            currentPos++;
            temp = temp.next;
        }
    }

#### 3.6对链表进行排序 ####

冒泡排序

**
     * @Description: 对链表进行排序
     * @Param: [head]
     * @return: void
     * @Author: sunzhen
     * @Date: 2020/5/30
     */
    public static void sortLinkList(Node head) { 
        Node currentNode;
        Node nextNode;
        for (currentNode = head.next; currentNode.next != null; currentNode = currentNode.next) { 
            for (nextNode = head.next; nextNode.next != null; nextNode = nextNode.next) { 
                if (nextNode.data > nextNode.next.data) { 
                    int temp = nextNode.data;
                    nextNode.data = nextNode.next.data;
                    nextNode.next.data = temp;
                }
            }
        }
    }

#### 3.7找到链表中倒数第k个节点 ####

这个算法挺有趣的。设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点

/** * @Description: 找到链表中倒数第k个结点 * 找到链表中倒数第k个节点(设置两个指针p1、p2，让p2比p1快k-1个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点 * @Param: [head, k] * @return: com.sunzhen.blog.Node * @Author: sunzhen * @Date: 2020/5/30 */
    public static Node findKNode(Node head, int k) { 
        if (k < 1 || k > linkListLength(head))
            return null;
        Node p1 = head;
        Node p2 = head;
    
        // p2比怕p1快k-1个节点
        for (int i = 0; i < k - 1; i++)
            p2 = p2.next;
    
    
        // 只要p2为null，那么p1就是倒数第k个节点了
        while (p2.next != null) { 
            p2 = p2.next;
            p1 = p1.next;
        }
        return p1;
    }

#### 3.8删除链表重复数据 ####

/** * @Description: 删除链表重复数据 * 遍历链表，把遍历的值存储到一个Hashtable中，在遍历过程中，若当前访问的值在Hashtable中已经存在， * 则说明这个数据是重复的，因此就可以删除。 * <p> * 优点：时间复杂度较低O(n) * 缺点：在遍历过程中需要额外的存储空间来保存已遍历过的值 * @Param: [head] * @return: void * @Author: sunzhen * @Date: 2020/5/30 */
    public static void deleteDuplicateV1(Node head) { 
        Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
        Node temp = head.next;
        Node pre = null; //辅助链表的头节点
        while (temp != null) { 
            if (table.containsKey(temp.data))
                pre.next = temp.next;
            else { 
                table.put(temp.data, 1);
                pre = temp;
            }
            temp = temp.next;
        }
    }
    
    /** * @Description: 删除链表重复数据 * 对链表进行双重循环遍历，外循环正常遍历链表，假设外循环当前遍历的结点为cur，内循环从cur开始遍历， * 若碰到与cur所指向结点值相同，则删除这个重复结点 * <p> * 优点：不需要额外的存储空间 * 缺点：时间复杂度较高O(n^2) * @Param: [head] * @return: void * @Author: sunzhen * @Date: 2020/5/30 */
    public static void deleteDuplicateV2(Node head) { 
        /*Node currentNode; Node temp; for (currentNode = head.next; currentNode != null; currentNode = currentNode.next) { for (temp = currentNode; temp.next != null;) { if (temp.next.data == currentNode.data) { temp.next = temp.next.next; } else { temp = temp.next; } } }*/
    
        Node p = head;
        while (p != null) { 
            Node q = p;
            while (q.next != null) { 
                if (q.next.data == p.data) { 
                    q.next = q.next.next;
                } else
                    q = q.next;
            }
            p = p.next;
        }
    }
    
    /** * @Description: 删除链表重复数据 * 外循环当前遍历的结点为cur，内循环从链表头开始遍历至cur，只要碰到与cur值相同的结点就删除该结点，同时内循环结束， * 因为与cur相同的结点只可能存在一个（如果存在多个，在前面的遍历过程中已经被删除了） * <p> * 优点：采用这种方法在特定的数据发布的情况下会提高算法的时间复杂度 * @Param: [head] * @return: void * @Author: sunzhen * @Date: 2020/5/30 */
    public static void deleteDuplicateV3(Node head) { 
        Node p = head.next;
        while (p != null) { 
            Node q = head.next;
            while (q.next != p && q.next != null) { 
                if (q.next.data == p.data) { 
                    q.next = q.next.next;
                } else
                    q = q.next;
            }
            p = p.next;
        }
    }

#### 3.9查询链表的中间节点 ####

这个算法也挺有趣的：一个每次走1步，一个每次走两步，走两步的遍历完，然后走一步的指针，那就是中间节点

**
     * @Description: 查询链表的中间节点
     * @Param: [head]
     * @return: com.sunzhen.blog.Node
     * @Author: sunzhen
     * @Date: 2020/5/30
     */
    public static Node searchMid(Node head) { 
        Node p1 = head;
        Node p2 = head;
        // 一个走一步，一个走两步，直到为null，走一步的到达的就是中间节点
        while (p2 != null && p2.next != null && p2.next.next != null) { 
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

#### 3.10通过递归从尾到头输出单链表 ####

/** * @Description: 通过递归从尾到头输出单链表 * @Param: [head] * @return: void * @Author: sunzhen * @Date: 2020/5/30 */
    public static void printListReversely(Node head) { 
        if (head == null) { 
            return;
        }
        printListReversely(head.next);
        if (head.data != null) { 
            System.out.println(head.data);
        }
    }

#### 3.11反转链表 ####

**递归：从尾部开始处理**

/** * @Description: 反转链表（递归实现） * @Param: [head] * @return: com.sunzhen.blog.Node * @Author: sunzhen * @Date: 2020/5/30 */
    public static Node linkedListReverserV1(Node head) { 
        Node prev = null;
        if (head == null || head.next == null) { 
            prev = head;
        } else { 
            Node tmp = linkedListReverserV1(head.next);
            head.next.next = head; //将前一个放到后一个的后一个实现倒置
            head.next = null; //切断之前顺序的指针
            prev = tmp;
        }
        return prev;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy_size_16_color_FFFFFF_t_70 2]  
**非递归：从头部开始处理**

/** * @Description: 反转链表（非递归实现） * @Param: [head] * @return: com.sunzhen.blog.Node1 * @Author: sunzhen * @Date: 2020/5/30 */
    public static Node linkedListReverserV2(Node head) { 
        Node prev = null;
        while (head != null) { 
            Node tmp = head;
            head = head.next;
            tmp.next = prev; //倒置
            prev = tmp;
        }
        return prev;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy_size_16_color_FFFFFF_t_70 3]

## 四、参考文献 ##

本文大量参考[Java3y的博客][Java3y]，感谢您。

## 五、 补充说明 ##

#### 5.1为什么数组要比链表查询速度快？ ####

#### 5.2为什么链表要比数组插入和删除效率低？ ####

[20200531155310714.png]: https://img-blog.csdnimg.cn/20200531155310714.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200531155322716.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200531155331684.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200531155708706.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200531155728371.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Nzk4Mjcy,size_16,color_FFFFFF,t_70
[Java3y]: https://juejin.im/post/5abb51daf265da238925c705#heading-12