【数据结构与算法之线性结构】链表

╰半橙微兮° 2024-03-25 12:35 33阅读 0赞

#### 【数据结构与算法之线性结构】链表 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之线性结构】链表
         *   *   *  1 链表的基本概念
                 *  2 链表的定义
                 *  3 链表的基本操作
                 *   *  向链表中插入节点
                     *  从链表中删除节点
                 *  4 链表的性能分析
                 *  5 不同形态的链表结构
                 *   *  循环链表
                     *  双向链表
                     *  双向循环链表
                 *  6 案例
                 *   *  链表的综合操作
                     *  将两个有序链表归并

###### 1 链表的基本概念 ######

链表也是一种线性数据结构，与数组不同的是，链表的存储空间并不连续。

链表的节点：地址分散的存储单元，每个节点都有一个“指针域”成员，存储着下一个节点的内存地址。

每个链表都会有一个链表头，用于存放链表的第一个节点的地址，链表的最后一个节点的指针域通常会置空null，用于表示是最后一个节点了，没有后继了。

![在这里插入图片描述][90d65f62e1824f16844b88ce62cdde7f.png_pic_center]

【链表特征】

*  逻辑连续，物理不一定连续
 *  每个链表节点都必须包含指针域，存放下一个节点的内存地址。
 *  只要有了链表头head，就可以遍历整个链表。

###### 2 链表的定义 ######

节点类：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: Node
     * @Author: Ding Jiaxiong
     * @Data:2023/3/12 20:25
     */
    
    public class Node {
        
        int data; // 数据域
        Node next; // 指针域，指向下一个节点
    
        public Node(int data) {
        
            this.data = data;
        }
    }

自定义链表类：

###### 3 链表的基本操作 ######

###### 向链表中插入节点 ######

1.  通过循环操作找到要插入位置的前一个节点，用指针p指向该节点
2.  创建一个新节点，赋值data，同时用指针node 指向它
3.  将p指向节点的next域值赋给node节点的next域
4.  再将node赋值给p节点的next域

运行结果

![在这里插入图片描述][950ba580bb984e32a0a4ce80c1427622.png_pic_center]

###### 从链表中删除节点 ######

*  首先通过循环操作找到要删除节点的前一个节点，指针p指向该节点
 *  执行`p.next = p.next.next`，完成删除

public boolean deleteNode(int index) {
         // index非索引, 单纯代表第几个位置, 从1开始
        // 判断删除位置是否合法
        if (index < 1 || index > length) {
        
            System.out.println("删除节点位置错误");
            return false;
        }
    
        // 删除第一个节点(head), 特判
        if (index == 1) {
        
            head = head.next;
            length--;
            return true;
        }
    
        Node p = head; // 指向第一个节点
        int i = 1;
        while (i < index - 1 && p != null) {
         // 找到删除位置前一个节点位置
            p = p.next;
            i++;
        }
    
        p.next = p.next.next;
        length--;
        return true;
    }

测试

![在这里插入图片描述][e16aeab36c034bdbbab20283ad4e2fc8.png_pic_center]

###### 4 链表的性能分析 ######

*  在链表中定位一个元素的时间复杂度是 O ( n ) O(n) O(n)
 *  如果已知要插入或者删除节点之前节点的指针，那么插入或删除的时间复杂度为 O ( 1 ) O(1) O(1)

###### 5 不同形态的链表结构 ######

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

![在这里插入图片描述][827ff0ebc064435f979d6c13ab3d5a92.png_pic_center]

最后一个节点的指针域不为null，而指向链表的第一个节点。

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

![在这里插入图片描述][ec65baef747740a5aaabdfd2115406ef.png_pic_center]

双向链表的节点中存在两个指针域，一个指向前驱，一个指向后继。

###### 双向循环链表 ######

![在这里插入图片描述][79efeca0fe2b4d949b7231abb2a48e69.png_pic_center]

= 循环链表 + 双向链表。

###### 6 案例 ######

###### 链表的综合操作 ######

创建一个包含10个节点的单链表保存1-10，打印链表，在第1、3、5、20个位置上分别插入一个节点，数据均为0，每插入一个，打印一次，接着将插入的节点全部删除，再打印，最后销毁链表。

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyLinkedList
     * @Author: Ding Jiaxiong
     * @Data:2023/3/12 20:26
     */
    
    public class MyLinkedList {
        
    
        Node head = null; // 链表头
        int length; // 链表的长度
    
        public boolean insertNode(int data, int index) {
        
            // 在链表的第index位置上插入一个data节点
            // 判断index是否合法
            if (index < 1 || index > (length + 1)) {
        
                System.out.println("插入节点index不合法");
                return false;
            }
    
            // 如果index = 1, 即链表还啥也没有, 单独考虑
            if (index == 1) {
        
                if (head == null) {
        
                    head = new Node(data);  //创建第一个节点，并赋值给head
                } else {
        
                    Node node = new Node(data); // 创建一个新节点node
                    node.next = head; // 将head 赋值给node的next
                    head = node;
                }
                length++;
                return true;
            }
    
            // 插入位置不是1
            Node p = head; // p指向链表第一个节点
            int i = 1;
            while (i < index - 1 && p != null) {
        
                p = p.next;
                i++;
            }
    
            Node node = new Node(data);
            Node q = p.next;
            p.next = node;
            node.next = q;
            length++;
            return true;
        }
    
        // 打印链表
        public void printLinkedLst() {
        
            Node p = head;
            while (p != null) {
        
                System.out.print(p.data + " → ");
                p = p.next;
            }
            System.out.print("null\n");
        }
    
        // 销毁链表[自动GC]
        public void destroyLinkedList() {
        
            head = null;
            length = 0;
        }
    
        public boolean deleteNode(int index) {
         // index非索引, 单纯代表第几个位置, 从1开始
            // 判断删除位置是否合法
            if (index < 1 || index > length) {
        
                System.out.println("删除节点位置错误");
                return false;
            }
    
            // 删除第一个节点(head), 特判
            if (index == 1) {
        
                head = head.next;
                length--;
                return true;
            }
    
            Node p = head; // 指向第一个节点
            int i = 1;
            while (i < index - 1 && p != null) {
         // 找到删除位置前一个节点位置
                p = p.next;
                i++;
            }
    
            p.next = p.next.next;
            length--;
            return true;
        }
    
        public static void main(String[] args) {
        
    
            MyLinkedList list = new MyLinkedList();
            for (int i = 1; i <= 10; i++) {
        
                list.insertNode(i, i);
            }
    
            list.printLinkedLst();
            list.insertNode(0, 1);
            list.printLinkedLst();
            list.insertNode(0, 3);
            list.printLinkedLst();
            list.insertNode(0, 5);
            list.printLinkedLst();
            list.insertNode(0, 20);
            list.printLinkedLst();
    
            list.deleteNode(1);
            list.deleteNode(2);
            list.deleteNode(3);
            list.deleteNode(20);
            list.printLinkedLst();
            list.destroyLinkedList();
            list.printLinkedLst();
    
        }
    
    }

运行结果

![在这里插入图片描述][7937db0137934ebd94c702c2c6244a31.png_pic_center]

###### 将两个有序链表归并 ######

要求不开辟额外内存空间。

例如：list1: ① → ③ → ⑤ ， list2：② → ④ → ⑥ → ⑦，合并后 list3 = ① → ② → ③ → ④ → ⑤ → ⑥ → ⑦

步骤分析：

1.  定义一个Node头head3指向list3 的第一个节点，同时定义Node指针变量p、q、r辅助
2.  将head3 指向head1和head2中的较小者，∴ head3 指向 head1，r始终指向list3 最后一个节点，∴ 开始时r 指向 head1，同时规定指针p和q分别指向list1和list2中的待合并节点，所以p指向3，q指向2.
3.  循环不断比较p和q指向的节点值，如果p小，则将p指向的节点插入r指向的节点后，然后移动p和r，如果p大，则将q指向的节点插入到r指向的节点后，并移动q和r。
4.  不断重复3，当p等于null或者q等于null时结束循环，此时list1和list2中至少有一个链表已经全部合并到list3中
5.  将剩余节点整体插入r后

代码实现：

链表类：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyLinkedList
     * @Author: Ding Jiaxiong
     * @Data:2023/3/12 20:26
     */
    
    public class MyLinkedList {
        
    
        Node head = null; // 链表头
        int length; // 链表的长度
    
        // 返回链表的头节点指针
        public Node getHead() {
        
            return head;
        }
    
        // 设置链表的头结点指针
        public void setHead(Node head) {
        
            this.head = head;
        }
    
        public boolean insertNode(int data, int index) {
        
            // 在链表的第index位置上插入一个data节点
            // 判断index是否合法
            if (index < 1 || index > (length + 1)) {
        
                System.out.println("插入节点index不合法");
                return false;
            }
    
            // 如果index = 1, 即链表还啥也没有, 单独考虑
            if (index == 1) {
        
                if (head == null) {
        
                    head = new Node(data);  //创建第一个节点，并赋值给head
                } else {
        
                    Node node = new Node(data); // 创建一个新节点node
                    node.next = head; // 将head 赋值给node的next
                    head = node;
                }
                length++;
                return true;
            }
    
            // 插入位置不是1
            Node p = head; // p指向链表第一个节点
            int i = 1;
            while (i < index - 1 && p != null) {
        
                p = p.next;
                i++;
            }
    
            Node node = new Node(data);
            Node q = p.next;
            p.next = node;
            node.next = q;
            length++;
            return true;
        }
    
        // 打印链表
        public void printLinkedLst() {
        
            Node p = head;
            while (p != null) {
        
                System.out.print(p.data + " → ");
                p = p.next;
            }
            System.out.print("null\n");
        }
    
        // 销毁链表[自动GC]
        public void destroyLinkedList() {
        
            head = null;
            length = 0;
        }
    
        public boolean deleteNode(int index) {
         // index非索引, 单纯代表第几个位置, 从1开始
            // 判断删除位置是否合法
            if (index < 1 || index > length) {
        
                System.out.println("删除节点位置错误");
                return false;
            }
    
            // 删除第一个节点(head), 特判
            if (index == 1) {
        
                head = head.next;
                length--;
                return true;
            }
    
            Node p = head; // 指向第一个节点
            int i = 1;
            while (i < index - 1 && p != null) {
         // 找到删除位置前一个节点位置
                p = p.next;
                i++;
            }
    
            p.next = p.next.next;
            length--;
            return true;
        }
    
        public static void main(String[] args) {
        
    
        }
    
    }

测试

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MergeLinkedListTest
     * @Author: Ding Jiaxiong
     * @Data:2023/3/12 21:19
     */
    
    public class MergeLinkedListTest {
        
    
        public static MyLinkedList MergeLinkedList(MyLinkedList list1, MyLinkedList list2) {
        
    
            Node head3;
            Node p = list1.getHead();
            Node q = list2.getHead();
            Node r;
    
            if (p.data <= q.data) {
        
                head3 = p;
                r = p;
                p = p.next;
            } else {
        
                head3 = q;
                r = q;
                q = q.next;
            }
    
            while (p != null && q != null) {
        
                if (p.data <= q.data) {
        
                    r.next = p;
                    r = p;
                    p = p.next;
                } else {
        
                    r.next = q;
                    r = q;
                    q = q.next;
                }
            }
    
            // 剩余链表连接到r后
            r.next = (p != null) ? p : q;
            MyLinkedList list3 = new MyLinkedList();
            list3.setHead(head3);
    
            return list3;
        }
    
        public static void main(String[] args) {
        
    
            MyLinkedList list1 = new MyLinkedList();
            MyLinkedList list2 = new MyLinkedList();
            MyLinkedList list3 = new MyLinkedList();
    
            for (int i = 0; i < 5; i++) {
        
                list1.insertNode(i * 2 + 1, i + 1);
            }
            list1.printLinkedLst();
            for (int i = 1; i <= 5; i++) {
        
                list2.insertNode(i * 2, i);
            }
            list2.printLinkedLst();
    
            list3 = MergeLinkedList(list1, list2);
            // 销毁list1
            list1 = null;
            // 销毁list2
            list2 = null;
    
            list3.printLinkedLst();
        }
    
    }

运行结果

![在这里插入图片描述][b2833ccb19ac4de2bcefdd893bba4aad.png_pic_center]

[90d65f62e1824f16844b88ce62cdde7f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f4f8039b4dac4b598ff9b9ee09cf27b3.png
[950ba580bb984e32a0a4ce80c1427622.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/21476624514e496381180a5fd333154c.png
[e16aeab36c034bdbbab20283ad4e2fc8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/384be54c0d364faaa2dc1f3c98e04a53.png
[827ff0ebc064435f979d6c13ab3d5a92.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1bb52f713fc04f3eb10a202503c50272.png
[ec65baef747740a5aaabdfd2115406ef.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3665848a0b8c4f02829a27246be107f0.png
[79efeca0fe2b4d949b7231abb2a48e69.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/83d9730a265d464cbb4e18b456189fbd.png
[7937db0137934ebd94c702c2c6244a31.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/dfd2766818c54114821bd17d67bdb76f.png
[b2833ccb19ac4de2bcefdd893bba4aad.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8c3b5b0fca5d4859a481ca282251a665.png