Java数据结构：单链表的实现与面试题汇总（带头节点与不带头节点的两种方式的链表实现）

╰+攻爆jí腚メ 2023-09-24 13:30 117阅读 0赞

![在这里插入图片描述][a0563d26c829447293c1921a20a2afac.png]

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

### 文章目录 ###

*  1 单链表
 *   *  1.1 单链表介绍
     *  1.2 单链表的实现思路分析
     *   *  1.2.1 单链表的创建与遍历
         *  1.2.2 单链表节点的插入与修改
         *  1.2.3 单链表节点的删除
     *  1.3 实现代码
 *  2 单链表的面试题
 *   *  2.1 统计单链表中有效节点数量
     *  2.2 新浪--倒数第k个节点
     *  2.3 腾讯--单链表的反转
     *  2.4 百度--逆序打印单链表
 *  3 \*不带头节点的单链表实现
 *   *  3.1 完整代码
     *  3.2 测试
 *  写在最后

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

# 1 单链表 #

## 1.1 单链表介绍 ##

由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它 **不要求在逻辑上相邻的两个元素在物理位置上也相邻。**

**物理结构示意图：**  
![在这里插入图片描述][5ef0d9708db942d1bf857474864d727f.png]

**逻辑结构示意图：**  
![在这里插入图片描述][61b4858afd664b3ebdcb7fc2e049ef76.png]

**关于单链表的一些说明：**

*  链表是以节点的方式存储的，每个节点包含data和next域，分别表示存储的数据和指向下一个节点；
 *  链表的各个节点不一定是连续存储的；
 *  可以根据实际需求来构造是否带有头节点的链表。

## 1.2 单链表的实现思路分析 ##

### 1.2.1 单链表的创建与遍历 ###

**单链表的创建：**

1.  先创建一个 head 头节点，表示单链表的头；
2.  每添加一个节点就直接加入链表的最后；

**遍历的思路：**

1.  创建一个辅助指针，用于帮助遍历整个链表；
2.  当指针指向的节点的next域为null，说明当前节点为最后一个，遍历完成。

### 1.2.2 单链表节点的插入与修改 ###

示意图如下：  
![在这里插入图片描述][8b497f0943714f0db0171d84fb20db48.png]

1.  首先需要通过遍历找到需要添加节点的位置，图中示意的为a1的位置；
2.  新的节点的next指向a1.next；
3.  将该位置，即a1.next指向新的节点。

修改操作相当于上述过程的简化，只需要找到对应的节点直接修改节点对应的属性即可，这里不再赘述。

### 1.2.3 单链表节点的删除 ###

删除序号为 “2” 的节点示意图如下：  
![在这里插入图片描述][bea704baea544d0893c7817ce9f4ab34.png]

思路如下：

1.  找到待删除节点的前一个节点，示例中则找到序号为1的节点；
2.  让该节点的 temp.next = temp.next.next，即可；
3.  由于被删除的节点没有其他的指向，则会由Java的垃圾回收机制进行回收，无需处理。

## 1.3 实现代码 ##

**StudentNode.java 节点类：**

/**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 链表的节点类，包含学生信息和next
     */
    public class StudentNode {
        
        public String no; //学号
        public String name; //姓名
        public int age; //年龄
        public StudentNode next; //指向下一个节点
    
        //构造器
        public StudentNode(String no, String name, int age ){
        
            this.no = no;
            this.name = name;
            this.age = age;
        }
    
        //为了显示方便
        @Override
        public String toString() {
        
            return "StudentNode{" +
                    "no='" + no + '\'' +
                    ", name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    }

**StudentLinkedList.java 链表的实现类：**

/**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 链表的实现类，用于管理众多StudentNode节点
     */
    public class StudentLinkedList {
        
        //初始化头节点
        private StudentNode head = new StudentNode("", "", 0);
    
    	  //获取头节点
        public StudentNode getHead() {
        
            return head;
        }
    
        //添加节点
        //1.找到当前链表的最后节点
        //2.将最后节点的next指向新的节点
        public void add(StudentNode studentNode) {
        
            StudentNode temp = head;
            //遍历链表找到最后的节点
            while (temp.next != null) {
        
                //没有找到，就后移
                temp = temp.next;
            }
            //最后的节点的next指向新节点
            temp.next = studentNode;
        }
    
        //遍历 显示链表
        public void showList(){
        
            //判断链表是否为空
            if (head.next == null){
        
                System.out.println("当前链表为空");
                return;
            }
            //遍历 使用辅助指针
            StudentNode temp = head;
            while (temp != null){
        
                //更新指针
                temp = temp.next;
                if (temp.next == null){
        
                    System.out.print(temp);
                    break;
                }
                System.out.print(temp + "--->");
            }
        }
    
        //插入节点
        //根据学号顺序查找添加的位置, 如果存在, 则提示错误信息
        public void addByOrder(StudentNode studentNode){
        
            //寻找的temp应该为添加位置的前一个节点
            StudentNode temp = head;
            boolean flag = false; //标识新添加的no是否已经存在
            while (true){
        
                if (temp.next == null){
        
                    //已经在链表的尾部
                    break;
                }
                if (Integer.parseInt(temp.next.no) > Integer.parseInt(studentNode.no)){
        
                    //位置找到 插入到temp后
                    break;
                }else if (Integer.parseInt(temp.next.no) == Integer.parseInt(studentNode.no)){
        
                    //已经存在
                    flag = true;
                    break;
                }
                //移动指针
                temp = temp.next;
            }
            if (flag){
        
                System.out.println("\n准备插入的学生信息: " + studentNode.no + "，该学号已经存在，不可添加！");
            }else {
        
                studentNode.next = temp.next;
                temp.next = studentNode;
            }
        }
    
        //根据no学号修改学生信息
        public void update(StudentNode studentNode){
        
            if (head.next == null){
        
                System.out.println("当前链表为空, 无法修改");
                return;
            }
            StudentNode temp = head.next;
            boolean flag = false; //表示是否找到节点
            while (true){
        
                if (temp == null){
        
                    break;
                }
                if (temp.no == studentNode.no){
        
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag){
        
                temp.name = studentNode.name;
                temp.age = studentNode.age;
            }else {
        
                System.out.println("没有找到");
            }
        }
    
        //删除节点
        public void delete(String no){
        
            StudentNode temp = head;
            boolean flag = false; //标志是否找到
            //查找到待删除节点的前一个节点进行删除操作
            while (true){
        
                if (temp.next == null){
        
                    //到达尾部
                    break;
                }
                if (temp.next.no == no){
        
                    //找到了
                    flag = true;
                    break;
                }
                //遍历
                temp = temp.next;
            }
            //删除操作
            if (flag){
        
                temp.next = temp.next.next;
                System.out.println("删除成功！");
            }else {
        
                System.out.println("要删除的节点不存在！");
            }
        }
    }

**测试类：**

/**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 测试链表
     */
    public class StudentListTest {
        
    
        public static void main(String[] args) {
        
            StudentNode node1 = new StudentNode("1", "黄小黄", 21);
            StudentNode node2 = new StudentNode("2", "懒羊羊", 21);
            StudentNode node3 = new StudentNode("3", "沸羊羊", 22);
            //创建单链表 录入数据 输出
            StudentLinkedList list = new StudentLinkedList();
            list.add(node1);
            list.add(node2);
            list.add(node3);
            System.out.println("遍历链表:");
            list.showList();
            //测试插入数据方法
            StudentNode node5 = new StudentNode("5", "美羊羊", 19);
            StudentNode node4 = new StudentNode("4", "暖羊羊", 19);
            list.addByOrder(node5);
            list.addByOrder(node4);
            System.out.println("\n依次插入学号为5、4的学生后:");
            list.showList();
            //测试修改方法
            System.out.println("\n测试修改方法:");
            list.update(new StudentNode("1", "祢豆子", 10));
            list.showList();
            //测试删除方法
            System.out.println("\n测试删除方法:");
            list.delete("1");
            list.delete("5");
            list.showList();
        }
    }

**实现结果：**

遍历链表:
    StudentNode{no='1', name='黄小黄', age=21}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}
    依次插入学号为5、4的学生后:
    StudentNode{no='1', name='黄小黄', age=21}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19}
    测试修改方法:
    StudentNode{no='1', name='祢豆子', age=10}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19}
    测试删除方法:
    删除成功！
    删除成功！
    StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}
    Process finished with exit code 0

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

# 2 单链表的面试题 #

## 2.1 统计单链表中有效节点数量 ##

/**
         * 
         * @param head 头节点
         * @return 返回有效节点个数
         */
        public static int getLength(StudentNode head){
        
            if (head.next == null){
        
                return 0;
            }
            int length = 0;
            StudentNode temp = head.next;
            while (temp != null){
        
                length++;
                temp = temp.next;
            }
            return length;
        }

## 2.2 新浪–倒数第k个节点 ##

> 查找链表中倒数第k个节点

**思路分析：**

1.  编写一个方法，接收head头节点和index，index表示k；
2.  链表从头到尾遍历，求出长度（链表节点个数）size；
3.  从第一个节点，遍历size-length次，即可找到倒数第k个节点。

**参考代码：**

/**
         * 获取单链表中倒数第k个节点
         * @param head 链表的头节点
         * @param index 倒数第 k 个元素
         * @return 返回倒数第 k 个元素，或者 null
         */
        public static StudentNode findLastIndexNode(StudentNode head, int index){
        
            //如果链表为空
            if (head.next == null){
        
                return null;
            }
            //得到链表的长度(节点个数)
            int size = getLength(head);
            //遍历 size-index次 得到倒数第index个节点
            //数据校验
            if (index <= 0 || index > size){
        
                return null;
            }
            //遍历
            StudentNode current = head.next;
            for (int i = 0; i < size - index; i++) {
        
                current = current.next;
            }
            return current;
        }

## 2.3 腾讯–单链表的反转 ##

> 反转单链表

**思路分析：**

1.  可以使用头插法；
2.  以原链表为模板，每遍历一个节点，取出，并接在新链表的最前端；
3.  原head头节点，指向新的节点；
4.  直到遍历完为止。

**参考代码：**

/**
         * 头插法反转链表
         * @param head 接收待反转的链表
         * @return 返回一个反转后的新链表
         */
        public static StudentLinkedList reverseList(StudentNode head){
        
            if (head.next == null){
        
                return null;
            }
            StudentNode old = head.next; //用于遍历旧链表
            //创建新链表，新链表根据原链表遍历得到
            StudentLinkedList newList = new StudentLinkedList();
            StudentNode newHead = newList.getHead(); //新链表的头节点
            //遍历构造
            boolean flag = true; //标记是否为第一次添加
            while (old != null){
        
                //头插法加入到新链表中
                StudentNode newNode = new StudentNode(old.no, old.name, old.age);
                if(flag){
        
                    newHead.next = newNode;
                    newNode.next = null;
                    flag = false;
                }else {
        
                    newNode.next = newHead.next;
                    newHead.next = newNode;
                }
                old = old.next;
            }
            return newList;
        }

**以上方式虽然可以实现链表的反转，但是是以返回一个新的反转链表的形式，并没有真正意义上实现原地反转，下面介绍另一种方式：**

**双指针:**

/**
         * 双指针就地反转链表
         * @param head 接收链表的头节点，方法中会将链表反转
         */
        public static void reverse(StudentNode head){
        
            //如果当前链表为空 或者只有一个节点 直接返回即可
            if (head.next == null || head.next.next == null){
        
                return;
            }
            //辅助指针遍历原来的链表
            StudentNode cur = head.next; //当前节点
            StudentNode next = null; //指向cur的下一个节点
            StudentNode reverseHead = new StudentNode("", "", 0);
            //遍历原来的链表，每遍历一个节点，就取出，放在新链表的最前端
            while (cur != null){
        
                next = cur.next; //暂时保存当前节点的下一个节点
                cur.next = reverseHead.next; //讲cur下一个节点放在链表最前端
                reverseHead.next = cur;
                cur = next; //cur后移动
            }
            head.next = reverseHead.next;
            return;
        }

## 2.4 百度–逆序打印单链表 ##

> 从尾到头打印单链表

**方式一：** 先将单链表反转，然后再打印。但是这样会破坏掉原有单链表的结构，而题目要求仅仅是打印，因此不建议！

**方式二：** **利用栈模拟**

将单链表的各个节点压入栈中，利用栈先进后出的特点，实现逆序打印。

**参考代码：**

/**
         * 利用栈模拟 实现链表的逆序打印
         * @param head 链表的头节点
         */
        public static void reversePrintList(StudentNode head){
        
            if (head.next == null){
        
                return; //空链表无法打印
            }
            //创建栈模拟逆序打印
            Stack<StudentNode> stack = new Stack<>(); //栈
            StudentNode cur = head.next;
            //将链表的所有节点压入栈
            while (cur != null){
        
                stack.push(cur);
                cur = cur.next;
            }
            //逆序打印
            while (!stack.empty()){
        
                //出栈
                System.out.println(stack.pop());
            }
            return;
        }

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

# 3 \*不带头节点的单链表实现 #

## 3.1 完整代码 ##

**ListIndexOutOfException**  
自定义异常类

/**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 链表越界异常
     */
    public class ListIndexOutOfException extends RuntimeException {
        
    
        public ListIndexOutOfException(String message) {
        
            super(message);
        }
    }

**MyLinkedList**  
使用泛型实现

/**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 不带头节点的单向链表
     */
    @SuppressWarnings({
        "all"})
    public class MyLinkedList<T> {
        
    
        public Node head; // 指向链表的头
    
        class Node<T>{
        
            public T val; // 存储的数据
            public Node next; // 存储下一个节点的地址
    
            public Node(T val) {
        
                this.val = val;
            }
        }
    
        /**
         * 遍历链表
         */
        public void display(){
        
            Node<T> cur = head; // 辅助指针
            while (cur != null){
        
                if (cur.next == null){
        
                    System.out.println(cur.val);
                }else {
        
                    System.out.print(cur.val + "->");
                }
                cur = cur.next;
            }
        }
    
        /**
         * 查看链表是否包含key
         * @param key 查询的值
         * @return
         */
        public boolean contains(T key){
        
            Node<T> cur = head;
            while (cur != null){
        
                if (cur.val.equals(key)){
        
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
    
        /**
         * 查看链表的长度
         * @return 链表的长度
         * 时间复杂度O(n),如果属性中存储长度,则只需要每次添加和删除的时候size++,时间复杂度O(1)
         */
        public int size(){
        
            int count = 0;
            Node<T> cur = head;
            while (cur != null){
        
                count++;
                cur = cur.next;
            }
            return count;
        }
    
        /**
         * 头插法
         * @param data 插入的节点数据
         */
        public void addHead(T data){
        
            Node<T> newNode = new Node<>(data);
            newNode.next = head;
            head = newNode;
        }
    
        /**
         * 尾插法
         * @param data 插入的节点数据
         */
        public void add(T data){
        
            Node<T> newNode = new Node<>(data);
            if(head == null){
        
                head = newNode;
            }else {
        
                Node<T> cur = head;
                while (cur.next != null){
        
                    cur = cur.next;
                }
                cur.next = newNode;
            }
        }
    
        /**
         * 清空链表
         */
        public void clear(){
        
            head = null;
        }
    
        /**
         * 在指定位置处插入节点，第一个位置为0下标
         * @param index 指定位置
         * @param data 插入的节点
         */
        public void insertByIndex(int index, T data){
        
            if (index < 0 || index > size()){
        
                throw new ListIndexOutOfException("index位置不合法！");
            }
            Node<T> cur = head;
            Node<T> newNode = new Node<>(data);
            if (index == 0){
        
                addHead(data);
                return;
            }
            if (index == size()){
        
                add(data);
                return;
            }
            while (cur.next != null && index-1 != 0){
        
                --index;
                cur = cur.next;
            }
            newNode.next = cur.next;
            cur.next = newNode;
        }
    
        /**
         * 根据key删除，删除第一个出现的key
         * @param key
         */
        public void remove(T key){
        
            //判断链表是否为空
            if (head == null){
        
                System.out.println("当前链表为空，无法删除！");
                return;
            }
            // 如果要删的是第一个节点
            if (head.val.equals(key)){
        
                head = head.next;
                return;
            }
            Node<T> cur = head;
            while (cur != null && !cur.next.val.equals(key)){
        
                cur = cur.next;
            }
            if (cur == null){
        
                System.out.println("待删除的元素不存在，无法删除！");
                return;
            }
            // 常规情况
            cur.next = cur.next.next;
        }
    
        /**
         * 删除所有的key
         * @param key
         */
        public void removeAll(T key){
        
            // 判空
            if (head == null){
        
                return;
            }
            // 使用双指针法删除
            Node<T> pre = head;
            Node<T> cur = head.next;
            while (cur != null){
        
                if(cur.val == key){
        
                    pre.next = cur.next;
                }else {
        
                    pre = cur;
                }
                cur = cur.next;
            }
            // 处理第一个元素
            if (head.val == key){
        
                head = head.next;
            }
        }
    }

## 3.2 测试 ##

public class Main {
        
    
        public static void main(String[] args) {
        
            MyLinkedList<Integer> myList = new MyLinkedList<>();
            System.out.println("==========测试尾插法=========");
            myList.add(1);
            myList.add(2);
            myList.add(3);
            myList.add(4);
            myList.display();
            myList.clear();
    
            System.out.println("==========测试头插法=========");
            myList.addHead(1);
            myList.addHead(2);
            myList.addHead(3);
            myList.addHead(4);
            myList.display();
            System.out.println("在第4个位置处插入99");
            myList.insertByIndex(4, 99);
            myList.display();
            System.out.println("在第0个位置处插入100");
            myList.insertByIndex(0, 100);
            myList.display();
    
            System.out.println("==========测试删除=========");
            System.out.println("删除第一个100：");
            myList.remove(100);
            myList.display();
            System.out.println("删除第一个99：");
            myList.remove(99);
            myList.display();
            System.out.println("插入一个4");
            myList.add(4);
            myList.display();
            System.out.println("删除所有的4");
            myList.removeAll(4);
            myList.display();
        }
    }

![在这里插入图片描述][8f7ca5f967b44a358ae4dce605a8eb0c.png]

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

# 写在最后 #

**本文被 [Java数据结构][Java] 收录[点击订阅专栏][Java]** ， 持续更新中。  
 创作不易，如果你有任何问题，欢迎私信，感谢您的支持！  
![在这里插入图片描述][33ad3bfbfa084fe792cdcea04e64ede9.gif_pic_center]  
![在这里插入图片描述][ad16d93416c74666a97b046cb173134c.gif_pic_center]

[a0563d26c829447293c1921a20a2afac.png]: https://img-blog.csdnimg.cn/a0563d26c829447293c1921a20a2afac.png
[5ef0d9708db942d1bf857474864d727f.png]: https://img-blog.csdnimg.cn/5ef0d9708db942d1bf857474864d727f.png
[61b4858afd664b3ebdcb7fc2e049ef76.png]: https://img-blog.csdnimg.cn/61b4858afd664b3ebdcb7fc2e049ef76.png
[8b497f0943714f0db0171d84fb20db48.png]: https://img-blog.csdnimg.cn/8b497f0943714f0db0171d84fb20db48.png
[bea704baea544d0893c7817ce9f4ab34.png]: https://img-blog.csdnimg.cn/bea704baea544d0893c7817ce9f4ab34.png
[8f7ca5f967b44a358ae4dce605a8eb0c.png]: https://img-blog.csdnimg.cn/8f7ca5f967b44a358ae4dce605a8eb0c.png
[Java]: https://blog.csdn.net/m0_60353039/category_12062687.html
[33ad3bfbfa084fe792cdcea04e64ede9.gif_pic_center]: https://img-blog.csdnimg.cn/33ad3bfbfa084fe792cdcea04e64ede9.gif#pic_center
[ad16d93416c74666a97b046cb173134c.gif_pic_center]: https://img-blog.csdnimg.cn/ad16d93416c74666a97b046cb173134c.gif#pic_center