数据结构与算法-单链表（Linked List）

偏执的太偏执、 2022-12-12 15:13 226阅读 0赞

# 链表（Linked List） #

## 1、链表介绍 ##

链表是有序的列表，但是他在内存中的存储结构如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0p1bHlfd2hq_size_16_color_FFFFFF_t_70_pic_center]

*  链表是以节点的方式来存储的，是链式存储
 *  每个节点包含`data`域、`next`域:指向下一个节点
 *  **链表的各个节点不一定是连续存储**。
 *  链表分**带头节点的链表和不带头节点的链表**，根据实际情况来确定  
    单链表（带头节点）逻辑结构示意图  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0p1bHlfd2hq_size_16_color_FFFFFF_t_70_pic_center 1]

## 2、单链表应用 ##

使用带头节点的单向链表实现-开发语言排行榜管理，完成对语言的增删改查操作。

### 2.1、定义链表结构 ###

分析：

*  使用带头节点的链表，我们需要定义头节点属性；
 *  链表包涵`data`域和`next`域，我们这里需要排序新增`no`排序属性、`name`语言名称属性  
    我们定义如下Node结构：

/**
         * 单链表节点
         */
        public class LanguageNode {
            /**
             * 排序
             */
            private int no;
            /**
             * 语言名称
             */
            private String language;
            /**
             * 语言描述
             */
            private String languageDescribe;
            /**
             * 下个节点
             */
            private LanguageNode next;
    
    
            public LanguageNode(int no, String language, String languageDescribe, LanguageNode next) {
                this.no = no;
                this.language = language;
                this.languageDescribe = languageDescribe;
                this.next = next;
            }
    
            @Override
            public String toString() {
                return "LanguageNode{" +
                        "no=" + no +
                        ", language='" + language + '\'' +
                        ", languageDescribe='" + languageDescribe + '\'' +
                        '}';
            }
    
        }

### 2.2 新增节点 ###

我们定义个`SingleLinkedList`链表管理器，在链表管理器中完成链表的增删改查操作。

下面我们实现链表的新增操作：

*  第一种方式在添加语言时，直接添加在链表的尾部

思路分析示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0p1bHlfd2hq_size_16_color_FFFFFF_t_70_pic_center 2]

*  第二种在添加语言时，根据**排名**将语言插入到相应的位置（如果有这个排名，则添加失败，并给出提示）

思路分析示意图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0p1bHlfd2hq_size_16_color_FFFFFF_t_70_pic_center 3]

代码实现：

/**
         * 根据顺序添加节点
         *
         * @param node 添加数据
         * @return 当前节点
         */
        public LanguageNode addByOrder(LanguageNode node) {
            //因为头节点不能移动，定义临时变量tmp
            LanguageNode tmp = this.head;
            //定义链表添加标识符
            boolean flag = false;
            while (true) {
                if (tmp.next == null) {
                    break;
                }
                if (tmp.next.no > node.no) {
                    break;
                } else if (tmp.next.no == node.no) {
                    //说明该顺序已经存在
                    flag = true;
                    break;
                }
                tmp = tmp.next;
            }
            if (flag) {
                System.out.printf("插入的位置%d已存在，不能插入\n", node.no);
            } else {
                node.next = tmp.next;
                tmp.next = node;
            }
            return node;
        }
    
        /**
         * 添加节点
         *
         * @param node 添加数据
         * @return
         */
        public LanguageNode add(LanguageNode node) {
            //因为头节点不能移动，定义临时变量tmp
            LanguageNode tmp = this.head;
            //将数据添加到最后，便利链表
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = node;
            return node;
        }

测试：

*  首先使用add尾部添加

执行结果如下：  
![在这里插入图片描述][2020100808090043.jpg_pic_center]

从结果看出：**打印的顺序和我们插入的顺序一致，没有按照no进行排序操作**

*  使用addByOrder测试

执行结果如下：  
![在这里插入图片描述][20201008080924985.jpg_pic_center]

从结果看出：**打印的顺序和我们插入的顺序不致，按照no进行排序插入**。

### 2.3 修改节点信息 ###

思路：修改节点功能比较简单，通过遍历先找到该节点信息，在对该节点内容进行修改即可。  
代码实现

public void update(LanguageNode node) {
            LanguageNode tmp = this.head;
            if (tmp.next == null) {
                System.out.println("链表为空");
                return;
            }
            while (true) {
                if (tmp.next == null) {
                    System.out.println("被修改的数据不存在");
                    break;
                }
                if (tmp.next.no == node.no) {
                    node.next = tmp.next.next;
                    tmp.next = node;
                    break;
                }
                tmp = tmp.next;
            }
        }

### 2.4 删除节点 ###

思路：先找到被删除的节点的前一个节点，定义为temp,我们将temp.next=temp.next.next将节点的饮用指要删除的向下个节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0p1bHlfd2hq_size_16_color_FFFFFF_t_70_pic_center 4]

代码实现：

public void delete(LanguageNode node) {
            LanguageNode tmp = this.head;
            if (tmp.next == null) {
                System.out.println("链表为空");
                return;
            }
            while (true) {
                if (tmp.next == null) {
                    System.out.println("被删除的数据不存在");
                    break;
                }
                if (tmp.next.no == node.no) {
                    tmp.next = tmp.next.next;
                    break;
                }
                tmp = tmp.next;
            }
    }

以上完成了链表的增删改查；

## 附录：完整代码 ##

public class SingleLinkedList {
        /**
         * 定义头节点
         */
        private LanguageNode head = new LanguageNode(0, "", "");
    
    
        public static void main(String[] args) {
            SingleLinkedList linkedList = new SingleLinkedList();
            LanguageNode java = new LanguageNode(1, "java", "超级好用");
            LanguageNode python = new LanguageNode(2, "python", "python");
            LanguageNode goLang = new LanguageNode(3, "goLang", "goLang");
            LanguageNode js = new LanguageNode(4, "js", "js");
            LanguageNode php = new LanguageNode(5, "php", "php是世界上最好的语言");
            LanguageNode node = new LanguageNode(4, "node", "node");
            linkedList.addByOrder(python);
            linkedList.addByOrder(java);
            linkedList.addByOrder(js);
            linkedList.addByOrder(php);
            linkedList.addByOrder(goLang);
            linkedList.update(node);
            linkedList.delete(node);
            linkedList.list();
        }
    
        public void delete(LanguageNode node) {
            LanguageNode tmp = this.head;
            if (tmp.next == null) {
                System.out.println("链表为空");
                return;
            }
            while (true) {
                if (tmp.next == null) {
                    System.out.println("被删除的数据不存在");
                    break;
                }
                if (tmp.next.no == node.no) {
                    tmp.next = tmp.next.next;
                    break;
                }
                tmp = tmp.next;
            }
        }
    
    
        public void update(LanguageNode node) {
            LanguageNode tmp = this.head;
            if (tmp.next == null) {
                System.out.println("链表为空");
                return;
            }
            while (true) {
                if (tmp.next == null) {
                    System.out.println("被修改的数据不存在");
                    break;
                }
                if (tmp.next.no == node.no) {
                    node.next = tmp.next.next;
                    tmp.next = node;
                    break;
                }
                tmp = tmp.next;
            }
        }
    
    
        /**
         * 根据顺序添加节点
         *
         * @param node 添加数据
         * @return 当前节点
         */
        public LanguageNode addByOrder(LanguageNode node) {
            //因为头节点不能移动，定义临时变量tmp
            LanguageNode tmp = this.head;
            //定义链表添加标识符
            boolean flag = false;
            while (true) {
                if (tmp.next == null) {
                    break;
                }
                if (tmp.next.no > node.no) {
                    break;
                } else if (tmp.next.no == node.no) {
                    //说明该顺序已经存在
                    flag = true;
                    break;
                }
                tmp = tmp.next;
            }
            if (flag) {
                System.out.printf("插入的位置%d已存在，不能插入\n", node.no);
            } else {
                node.next = tmp.next;
                tmp.next = node;
            }
            return node;
        }
    
        /**
         * 添加节点
         *
         * @param node 添加数据
         * @return
         */
        public LanguageNode add(LanguageNode node) {
            //因为头节点不能移动，定义临时变量tmp
            LanguageNode tmp = this.head;
            //将数据添加到最后，便利链表
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = node;
            return node;
        }
    
        public void list() {
            LanguageNode tmp = this.head;
            if (tmp.next == null) {
                System.out.println("链表为空");
            }
            while (tmp.next != null) {
                System.out.println(tmp.next);
                tmp = tmp.next;
            }
        }
    
    
        /**
         * 单链表节点
         */
        public static class LanguageNode {
            /**
             * 排序
             */
            private int no;
            /**
             * 语言名称
             */
            private String language;
            /**
             * 语言描述
             */
            private String languageDescribe;
            /**
             * 下个节点
             */
            private LanguageNode next;
    
    
            public LanguageNode(int no, String language, String languageDescribe) {
                this.no = no;
                this.language = language;
                this.languageDescribe = languageDescribe;
                this.next = null;
            }
    
    
            public int getNo() {
                return no;
            }
    
            public String getLanguage() {
                return language;
            }
    
            public String getLanguageDescribe() {
                return languageDescribe;
            }
    
            public LanguageNode getNext() {
                return next;
            }
    
            @Override
            public String toString() {
                return "LanguageNode{" +
                        "no=" + no +
                        ", language='" + language + '\'' +
                        ", languageDescribe='" + languageDescribe + '\'' +
                        '}';
            }
    
        }
    }

# 3、关于单链表的经典面试题 #

## 3.1 求单链表中有效节点个数 ##

代码实现：

public static int getLength(LanguageNode head) {
            if (head.next == null) {
                return 0;
            }
            LanguageNode tmp = head;
            int length = 0;
            while (tmp.next != null) {
                length++;
                tmp = tmp.next;
            }
            return length;
        }

## 3.2 查找单链表中的倒数第K个节点 ##

解析思路：

*  编写一个方法同时接收`head`节点和`index`节点
 *  `index`表示倒数第`index`个节点
 *  先把链表从头遍历一遍，得到链表的总长度为`length`,这里可以使用上面的`getLength`函数
 *  得到`size`后，我们可以从链表的第一个开始遍历（size-index）个，就可以得到
 *  如果找到该节点就返回，否则返回null  
    代码实现：

public static LanguageNode findLastIndexNode(LanguageNode head, int index) {
            if (head.next == null) {
                return null;
            }
            int size = getLength(head);
            if (index < 0 || index > size) {
                return null;
            }
            LanguageNode tmp = head.next;
            for (int i = 0; i < size - index; i++) {
                tmp = tmp.next;
            }
            return tmp;
    }

## 3.3 单链表的反转 ##

实现思路：

*  先定义一个节点reverseHead = new LanguageNode();
 *  从头到尾遍历原来的链表，每个遍历节点，将其取出，并放在新的链表先定义一个节点reverseHead的最前端。
 *  原来的链表的head.next = reverseHead.next

![image][]

### 代码实现 ###

/**
     * 单链表反转
     *
     * @param head 原始链表
     * @return
     */
    static void reverseList(LanguageNode head) {
        //一个节点不需要转换
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义辅助变量
        LanguageNode reverseNode = new LanguageNode(0, "", "");
        LanguageNode cur = head.next;
        LanguageNode next = null;
        while (cur != null) {
            //保存当前节点的下一个节点
            next = cur.next;
            //将cut的下一个节点，指向新链表的最前端
            cur.next = reverseNode.next;
            //将 cur 连接到新的链表上
            reverseNode.next = cur;
            cur = next;
        }
        head.next = reverseNode.next;
    }

public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        LanguageNode java = new LanguageNode(1, "java", "超级好用");
        LanguageNode python = new LanguageNode(2, "python", "python");
        LanguageNode goLang = new LanguageNode(3, "goLang", "goLang");
        LanguageNode js = new LanguageNode(4, "js", "js");
        LanguageNode php = new LanguageNode(5, "php", "php是世界上最好的语言");
        LanguageNode node = new LanguageNode(4, "node", "node");
        linkedList.addByOrder(python);
        linkedList.addByOrder(java);
        linkedList.addByOrder(js);
        linkedList.addByOrder(php);
        linkedList.addByOrder(goLang);
        linkedList.update(node);
        System.out.println("反转前链表：");
        linkedList.list();
        reverseList(linkedList.getHead());
        System.out.println("反转后链表：");
        linkedList.list();
    }
    //结果：
    反转前链表：
    LanguageNode{no=1, language='java', languageDescribe='超级好用'}
    LanguageNode{no=2, language='python', languageDescribe='python'}
    LanguageNode{no=3, language='goLang', languageDescribe='goLang'}
    LanguageNode{no=4, language='node', languageDescribe='node'}
    LanguageNode{no=5, language='php', languageDescribe='php是世界上最好的语言'}
    反转后链表：
    LanguageNode{no=5, language='php', languageDescribe='php是世界上最好的语言'}
    LanguageNode{no=4, language='node', languageDescribe='node'}
    LanguageNode{no=3, language='goLang', languageDescribe='goLang'}
    LanguageNode{no=2, language='python', languageDescribe='python'}
    LanguageNode{no=1, language='java', languageDescribe='超级好用'}

### 从尾到头打印单链表（方法1、反向遍历，2、Stack栈） ###

实现思路：

*  方式一
    
     *  可以先进行链表反转，在进行便利打印，反转会破坏原始链表结构，不推荐使用
 *  方式二
    
     *  可以利用栈的数据结构，将各个节点压入打栈中，然后利用栈的先进后出的特点，实现逆序打印。

#### 代码实现 ####

static void reversePrint(LanguageNode head) {
        if (head.next == null) {
            return;
        }
        Stack<LanguageNode> stack = new Stack<>();
        while (head.next != null) {
            stack.push(head.next);
            head = head.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
    
    
    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        LanguageNode java = new LanguageNode(1, "java", "超级好用");
        LanguageNode python = new LanguageNode(2, "python", "python");
        LanguageNode goLang = new LanguageNode(3, "goLang", "goLang");
        LanguageNode js = new LanguageNode(4, "js", "js");
        LanguageNode php = new LanguageNode(5, "php", "php是世界上最好的语言");
        LanguageNode node = new LanguageNode(4, "node", "node");
        linkedList.addByOrder(python);
        linkedList.addByOrder(java);
        linkedList.addByOrder(js);
        linkedList.addByOrder(php);
        linkedList.addByOrder(goLang);
        linkedList.update(node);
        System.out.println("正序打印：");
        linkedList.list();
        System.out.println("倒叙序打印：");
        reversePrint(linkedList.getHead());
    }
    //输出结果
    正序打印：
    LanguageNode{no=1, language='java', languageDescribe='超级好用'}
    LanguageNode{no=2, language='python', languageDescribe='python'}
    LanguageNode{no=3, language='goLang', languageDescribe='goLang'}
    LanguageNode{no=4, language='node', languageDescribe='node'}
    LanguageNode{no=5, language='php', languageDescribe='php是世界上最好的语言'}
    倒叙序打印：
    LanguageNode{no=5, language='php', languageDescribe='php是世界上最好的语言'}
    LanguageNode{no=4, language='node', languageDescribe='node'}
    LanguageNode{no=3, language='goLang', languageDescribe='goLang'}
    LanguageNode{no=2, language='python', languageDescribe='python'}
    LanguageNode{no=1, language='java', languageDescribe='超级好用'}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0p1bHlfd2hq_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/c65a6d6145f24acf9e5445bc71a232ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0p1bHlfd2hq_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/aff4ffb03a7c4e79886985caddfd3b1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0p1bHlfd2hq_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/71be98d294d8400ca6bff11adb8cd727.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0p1bHlfd2hq_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/105b4af3bebc4806ba740324cba6857b.png
[2020100808090043.jpg_pic_center]: /images/20221123/bd1ba3e75bcc4135bce13a5aaade68fb.png
[20201008080924985.jpg_pic_center]: /images/20221123/af9a507ff0bb4a0497e3f5bc2a91d017.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0p1bHlfd2hq_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/6adceffc51714362bdc69a4ac5ddef29.png
[image]: /images/20221123/5d5721d57e344e18ac25cce9dee75302.png