深入学习链表实现原理

以你之姓@ 2022-12-27 14:03 89阅读 0赞

### 文章目录 ###

*   *  链表
     *  链表实现
     *   *  结点类
         *  属性及构造方法
         *  getSize()方法
         *  isEmpty()方法
         *  traverse()方法
         *  add(Object data)方法
         *  addLast(Object data)方法
         *  insertNode(int index, Object data)方法
         *  deleteNode(Integer index)方法
         *  findNode(Integer index)方法
         *  updateNode(Integer index, Object data)
     *  完整代码

## 链表 ##

链表是一种线性结构，结构如下下图所示  
![在这里插入图片描述][20201211151939357.png]  
链表的每个结点分为两部分，结点的元素值data以及结点的指针，指向下一个结点，从而实现相互关联。

上图为单链表，只向一个方向遍历，所有操作中间结点效率比较低。链表为是链式存储，所以长度没有限制，不会浪费空间。

## 链表实现 ##

通过上面对链表的了解，下面我们来看看链表一些基本方法的实现。

### 结点类 ###

链表是由多个结点组成的，结点中包含了元素值和结点的指针，这里先定义一个声明结点的类。代码如下

public class Node{
        public Object data; //链表数据
        public Node next;   //链表指针，指向下一个结点
    
        public Node() {
        }
    
        public Node(Object data) {
            this.data = data;
        }
    
        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

结点类中包含了两个属性，元素值和结点指针；以及构造方法。

### 属性及构造方法 ###

在编写方法之前需要先声明两个属性，链表的头指针和结点的数量；以及构造方法，代码如下

//定义链表的头指针
    public Node head;
    
    //结点数量
    public Integer size;
    
    //构造函数
    public LinkList() {
        this.head = null;
        this.size = 0;
    }

### getSize()方法 ###

getSize()方法返回结点数量，在属性中定义了一个结点数量的属性size，所以这里直接返回size属性即可。

public Integer getSize(){
       	return size;
    }

### isEmpty()方法 ###

isEmpty()方法判断链表是否为空，如果size结点的数量等于0即链表为空。

public Boolean isEmpty(){
        return size == 0;
    }

### traverse()方法 ###

traverse()方法遍历链表中的所有结点数据。利用while循环依次遍历，直到结点为空结束。

**代码实现**

//遍历结点
    public void traverse(){
        //创建一个临时结点，赋值为链表头
        Node temp = head;
        //遍历链表
        while(temp != null){
            System.out.println("编程小马：" + temp.data);
            //指向下一个结点
            temp = temp.next;
        }
    }

### add(Object data)方法 ###

add()方法添加结点在链表头。定义属性时定义了链表头属性，所以在链表头添加结点效率很高，也很简单，只需要将新结点的指针指向原链表头结点即可。示意图如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70]  
将新结点的指针指向原链表头结点，新结点变为链表头。

**代码实现**

/**
     * 添加结点，在链表头
     * @param data 添加结点的元素值
     * @return Boolean
     */
    public Boolean add(Object data){
        try{
            //实例一个新结点，添加的结点
            Node newNode = new Node(data);
            //新结点的指针指向原链表头结点
            newNode.next = head;
            //改变头结点
            head = newNode;
            //结点数量自增
            size++;
            return true;
        }catch (Exception e){
            return false;
        }
    }

**注意：因为在链表头添加结点，所以先添加的结点在链表的后面。**

**add()方法测试**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 1]

### addLast(Object data)方法 ###

addLast(Object data)方法在链表的末尾添加结点，在链表的末尾添加结点，要先找到最后一个结点，需要访问整个链表，所以效率比较低。找到最后一个结点，把最后一个结点的指针指向新结点即可。示意图如下  
![在这里插入图片描述][2020121116384112.png]  
**代码实现**

/**
     * 添加结点，添加在链表尾
     * @param data 添加的元素值
     * @return  返回Boolean
     */
    public Boolean addLast(Object data){
        try {
            //实例一个新结点，添加的结点
            Node newNode = new Node(data);
            //创建一个临时结点，赋值为链表头
            Node temp = head;
            //如果链表为空，则把新结点插入到链表头
            if(size == 0){
                head = newNode;
            }else{
                //如果链表不为空，则找到链表尾结点
                while(temp.next != null){
                    //获取下一个结点
                    temp = temp.next;
                }
                //将尾结点指针指向新结点，添加结点
                temp.next = newNode;
            }
            //结点数量自增
            size++;
            return true;
        }catch (Exception e){
            return false;
        }
    }

在链表尾添加结点可以分为以下几步

*  实例一个新结点
 *  创建一个临时结点，赋值为链表头
 *  判断链表是否为空，如果链表为空，则把新结点插入到链表头；如果链表不为空，则找到链表尾结点，将尾结点指针指向新结点，添加结点
 *  结点数量自增

**addLast()方法测试**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 2]  
可以看出addLast()方法和add()方法插入的数据顺序是相反方向的，一个从链表头插入一个从链表尾插入。

### insertNode(int index, Object data)方法 ###

insertNode(int index, Object data)方法在指定位置插入结点。在指定位置插入结点，需要先判断位置参数是否合法；如果指定的位置为第一个结点位置，则直接将新结点的指针指向链表头，新结点作为新的链表头即可；如果指定的位置不为第一个结点位置，则先找到插入位置的前一个结点，在进行插入操作。示意图如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 3]  
**代码实现**

/**
     * 在指定位置插入结点
     * @param index 插入的位置
     * @param data  //插入的元素值
     * @return  返回Boolean
     */
    public Boolean insertNode(int index, Object data){
        try{
            //判断位置是否合法
            if(index < 1 || index > size){
                System.out.println("插入位置不合法！");
                return false;
            }
            //创建一个临时结点，赋值为链表头
            Node temp = head;
            //实例一个新结点，添加的结点
            Node newNode = new Node(data);
    
            //如果插入的位置是在第一个结点位置
            if (index == 1){
                //新结点的指针指向原链表头结点
                newNode.next = head;
                //改变头结点
                head = newNode;
            }else {
                for (int i = 1; i < size; i++) {
                    //找到插入位置的前一个结点
                    if (i == index - 1) {
                        //temp为插入位置的前一个结点
                        //新结点的指针指向插入位置的结点
                        newNode.next = temp.next;
                        //插入位置的前一个结点指针指向新结点
                        temp.next = newNode;
                        break;
                    }
                    //指向下一个结点
                    temp = temp.next;
                }
            }
            size++;
            return true;
        }catch (Exception e){
            return false;
        }
    }

在链表指定位置插入结点可以分为以下几步

*  判断位置是否合法
 *  创建一个临时结点，赋值为链表头
 *  实例一个新结点，添加的结点
 *  判断插入的位置是否是第一个结点位置，如果插入的位置是在第一个结点位置，则直接将新结点的指针指向链表头，新结点作为新的链表头即可；如果插入的位置不是第一个结点位置，则找到插入位置的前一个结点，新结点的指针指向插入位置的结点、插入位置的前一个结点指针指向新结点。
 *  结点数量自增

**insertNode()方法测试**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 4]

### deleteNode(Integer index)方法 ###

deleteNode(Integer index)方法删除index位置的结点，deleteNode(Integer index)方法和insertNode(int index, Object data)方法很相似，删除方法示意图如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 5]  
如上图所示，删除结点只需要改变删除结点的前结点指针指向删除结点的后一个指针即可。

**代码实现**

/**
     * 删除指定位置的结点
     * @param index 删除的结点位置索引
     * @return  Boolean
     */
    public Boolean deleteNode(Integer index){
        try{
            //判断位置是否合法
            if(index < 1 || index > size){
                System.out.println("插入位置不合法！");
                return false;
            }
            //创建一个临时结点，赋值为链表头
            Node temp = head;
            //判断删除的是否为第一个结点
            if(index == 1){
                //将头结点的下一个结点作为新的头结点
                Node newHead = head.next;
                //改变头结点
                head = newHead;
            }else{
                for(int i = 1; i < size; i++){
                    //找到删除结点位置的前一个结点
                    if(i == index - 1){
                        //temp为删除位置的前一个结点
                        //保存将要删除的结点
                        Node delNode = temp.next;
                        //将删除结点的前一个结点指针指向删除结点的下一个结点
                        temp.next = delNode.next;
                        //将删除结点置为空
                        delNode = null;
                        break;
                    }
                    temp = temp.next;
                }
            }
            size--;
            return true;
        }catch (Exception e){
            return false;
        }
    }

删除指定位置的结点可分为以下几步

*  判断位置是否合法
 *  创建一个临时结点，赋值为链表头
 *  判断删除的是否为第一个结点，如果删除的是第一个结点，则将头结点的下一个结点作为新的头结点；如果删除的不是第一个结点，则找到删除结点位置的前一个结点，将删除结点的前一个结点指针指向删除结点的下一个结点
 *  结点数量自减

**deleteNode()方法测试**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 6]

### findNode(Integer index)方法 ###

findNode(Integer index)方法查找链表中指定位置的结点对象，并返回。findNode相对来说，比前几个方法要简单一点。先判断位置是否合法，循环找到index位置的结点即可。

**代码实现**

/**
     * 查找链表中指定位置的结点，并返回
     * @param index 指定位置
     * @return  该位置的结点对象
     */
    public Node findNode(Integer index){
        try{
            //判断位置是否合法
            if(index < 1 || index > size){
                System.out.println("插入位置不合法！");
                return null;
            }
            //创建一个临时结点，赋值为链表头
            Node temp = head;
    
            for(int i = 1; i <= size; i++){
                //temp即当前位置的结点，找到index位置即返回该结点
                if(index == i){
                    return temp;
                }
                temp = temp.next;
            }
            return null;
        }catch (Exception e){
            return null;
        }
    }

**findNode()方法测试**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 7]

### updateNode(Integer index, Object data) ###

updateNode(Integer index, Object data)方法修改指定位置结点的元素值，利用上面的findNode(index)方法找到指定位置的结点对象，修改此对象的元素值即可。

**代码实现**

/**
     * 修改指定位置结点的元素值
     * @param index 指定位置
     * @param data  修改的元素值
     * @return  Boolean
     */
    public Boolean updateNode(Integer index, Object data){
        try{
            //根据findNode(Integer index)方法查找到index位置的结点
            Node node = findNode(index);
            //修改元素值
            node.data = data;
            return true;
        }catch (Exception e){
            return false;
        }
    }

**updateNode()方法测试**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 8]

## 完整代码 ##

> 以上就是单链表的一些常用方法。写的比较零散，下面是上述案例完整代码。有错误地方欢迎指出。

public class LinkList {
        //定义一个内部类，作为链表的结点
        public class Node{
            public Object data; //链表数据
            public Node next;   //链表指针，指向下一个结点
    
            public Node() {
            }
    
            public Node(Object data) {
                this.data = data;
            }
    
            public Node(Object data, Node next) {
                this.data = data;
                this.next = next;
            }
        }
    
        //定义链表的头指针
        public Node head;
    
        //结点数量
        public Integer size;
    
        //构造函数
        public LinkList() {
            this.head = null;
            this.size = 0;
        }
    
        //返回结点的数量
        public Integer getSize(){
            return size;
        }
    
        //链表是否为空
        public Boolean isEmpty(){
            return size == 0;
        }
    
        /**
         * 添加结点，添加在链表尾
         * @param data 添加的元素值
         * @return  返回Boolean
         */
        public Boolean addLast(Object data){
            try {
                //实例一个新结点，添加的结点
                Node newNode = new Node(data);
                //创建一个临时结点，赋值为链表头
                Node temp = head;
                //如果链表为空，则把新结点插入到链表头
                if(size == 0){
                    head = newNode;
                }else{
                    //如果链表不为空，则找到链表尾结点
                    while(temp.next != null){
                        //获取下一个结点
                        temp = temp.next;
                    }
                    //将尾结点指针指向新结点，添加结点
                    temp.next = newNode;
                }
                //结点数量自增
                size++;
                return true;
            }catch (Exception e){
                return false;
            }
        }
    
        /**
         * 添加结点，在链表头
         * @param data 添加结点的元素值
         * @return Boolean
         */
        public Boolean add(Object data){
            try{
                //实例一个新结点，添加的结点
                Node newNode = new Node(data);
                //新结点的指针指向原链表头结点
                newNode.next = head;
                //改变头结点
                head = newNode;
                //结点数量自增
                size++;
                return true;
            }catch (Exception e){
                return false;
            }
        }
    
        //遍历结点
        public void traverse(){
            //创建一个临时结点，赋值为链表头
            Node temp = head;
            //遍历链表
            while(temp != null){
                System.out.println("编程小马：" + temp.data);
                //指向下一个结点
                temp = temp.next;
            }
        }
    
        /**
         * 在指定位置插入结点
         * @param index 插入的位置
         * @param data  //插入的元素值
         * @return  返回Boolean
         */
        public Boolean insertNode(int index, Object data){
            try{
                //判断位置是否合法
                if(index < 1 || index > size){
                    System.out.println("插入位置不合法！");
                    return false;
                }
                //创建一个临时结点，赋值为链表头
                Node temp = head;
                //实例一个新结点，添加的结点
                Node newNode = new Node(data);
    
                //如果插入的位置是在第一个结点位置
                if (index == 1){
                    //新结点的指针指向原链表头结点
                    newNode.next = head;
                    //改变头结点
                    head = newNode;
                }else {
                    for (int i = 1; i < size; i++) {
                        //找到插入位置的前一个结点
                        if (i == index - 1) {
                            //temp为插入位置的前一个结点
                            //新结点的指针指向插入位置的结点
                            newNode.next = temp.next;
                            //插入位置的前一个结点指针指向新结点
                            temp.next = newNode;
                            break;
                        }
                        //指向下一个结点
                        temp = temp.next;
                    }
                }
                size++;
                return true;
            }catch (Exception e){
                return false;
            }
        }
    
        /**
         * 删除指定位置的结点
         * @param index 删除的结点位置索引
         * @return  Boolean
         */
        public Boolean deleteNode(Integer index){
            try{
                //判断位置是否合法
                if(index < 1 || index > size){
                    System.out.println("插入位置不合法！");
                    return false;
                }
                //创建一个临时结点，赋值为链表头
                Node temp = head;
                //判断删除的是否为第一个结点
                if(index == 1){
                    //将头结点的下一个结点作为新的头结点
                    Node newHead = head.next;
                    //改变头结点
                    head = newHead;
                }else{
                    for(int i = 1; i < size; i++){
                        //找到删除结点位置的前一个结点
                        if(i == index - 1){
                            //temp为删除位置的前一个结点
                            //保存将要删除的结点
                            Node delNode = temp.next;
                            //将删除结点的前一个结点指针指向删除结点的下一个结点
                            temp.next = delNode.next;
                            //将删除结点置为空
                            delNode = null;
                            break;
                        }
                        temp = temp.next;
                    }
                }
                size--;
                return true;
            }catch (Exception e){
                return false;
            }
        }
    
        /**
         * 查找链表中指定位置的结点，并返回
         * @param index 指定位置
         * @return  该位置的结点对象
         */
        public Node findNode(Integer index){
            try{
                //判断位置是否合法
                if(index < 1 || index > size){
                    System.out.println("插入位置不合法！");
                    return null;
                }
                //创建一个临时结点，赋值为链表头
                Node temp = head;
    
                for(int i = 1; i <= size; i++){
                    //temp即当前位置的结点，找到index位置即返回该结点
                    if(index == i){
                        return temp;
                    }
                    temp = temp.next;
                }
                return null;
            }catch (Exception e){
                return null;
            }
        }
    
        /**
         * 修改指定位置结点的元素值
         * @param index 指定位置
         * @param data  修改的元素值
         * @return  Boolean
         */
        public Boolean updateNode(Integer index, Object data){
            try{
                //根据findNode(Integer index)方法查找到index位置的结点
                Node node = findNode(index);
                //修改元素值
                node.data = data;
                return true;
            }catch (Exception e){
                return false;
            }
        }
    
        public static void main(String[] args) {
            //实例一个链表
            LinkList linkList = new LinkList();
            //向链表中添加元素
            linkList.addLast(1);
            linkList.addLast(2);
            System.out.println("插入前的链表");
            //遍历链表
            linkList.traverse();
    
            Node node = linkList.findNode(2);
            System.out.println("修改前链表中第2个结点的元素为：" + node.data);
            linkList.updateNode(2, 10);
            node = linkList.findNode(2);
            System.out.println("修改后链表中第2个结点的元素为：" + node.data);
    
            System.out.println();
            System.out.println("插入后的链表");
            //插入结点
            linkList.insertNode(1, 4);
            linkList.insertNode(3, 5);
            linkList.traverse();
    
            System.out.println();
            System.out.println("删除后的链表");
            linkList.deleteNode(1);
            linkList.traverse();
    
            System.out.println();
            node = linkList.findNode(2);
            System.out.println("链表中第2个结点的元素为：" + node.data);
    
            System.out.println();
        }
    }

[20201211151939357.png]: /images/20221120/58e38f1df68540ab9d48181be1058f68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70]: /images/20221120/e2beb770aa4746e0890713fdb0887461.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 1]: /images/20221120/347463067ea14912bddc9de43b9b7184.png
[2020121116384112.png]: /images/20221120/8a0df3b538c84b31b2bdbca0c4b6b048.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 2]: /images/20221120/b4482dda0ce0452998fe7bb5baf35673.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 3]: /images/20221120/0559723f786348c7a437b5004167f600.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 4]: /images/20221120/3dc69fc07a1b4587bb93a99d78792d57.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 5]: /images/20221120/644dd5d6d63a4563b0eb9d86791f9339.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 6]: /images/20221120/de058cc3cdc64cc8871dc55254cff751.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 7]: /images/20221120/cd12643fff0c4f00afa8a77719bfb4fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 8]: /images/20221120/3fbe636c3f5647ab9328af216b4e373d.png