开发者

Java数据结构和算法之链表详解

开发者 https://www.devze.com 2024-01-05 10:18 出处：网络 作者： 權sir
目录前言一、链表的概念及结构二、单向不带头非循坏链表的实现2.1打印链表2.2求链表的长度2.3头插法2.4尾插法2.5任意位置插入2.6查找是否包含某个元素的节点2.7删除第一次出现这个元素的节点2.8删除包含这个元素的所
相关专题：java 链表实现Java链表实现java链表怎么实现
目录
  • 前言
  • 一、链表的概念及结构
  • 二、单向不带头非循坏链表的实现
    • 2.1打印链表
    • 2.2求链表的长度
    • 2.3头插法
    • 2.4尾插法
    • 2.5任意位置插入
    • 2.6查找是否包含某个元素的节点
    • 2.7删除第一次出现这个元素的节点
    • 2.8删除包含这个元素的所以节点
    • 2.9清空链表
      • 单向链表的测试
  • 三、双向不带头非循坏链表的实现
    • 3.1打印双向链表
      • 3.2求双向链表的长度
        • 3.3头插法
          • 3.4尾插法
            • 3.5任意位置插入
              • 3.6查找是否包含某个元素的节点
                • 3.7删除第一次出现这个元素的节点
                  • 3.7删除包含这个元素的所有节点
                    • 3.9清空双向链表
                      • 双向链表的测试
                      • LinkedList的遍历方式
                  • 四、ArrayList和LinkedList的区别

                    前言

                    在前面我们已经学习了关于顺序表ArrayList的一些基本操作。通过源码知道，ArrayList底层使用数组来存储元素，由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：Java集合中又引入了LinkedList，即链表结构

                    一、链表的概念及结构

                    链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的

                    注意：

                    1.链式结构在逻辑上是连续的，但是在物理上不一定连续

                    2.现实中的结点一般都是从堆上申请出来的

                    3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能是连续，也可能不连续

                    链表的结构有8种样式：

                    • 单向带头循坏、单向带头非循坏、单向不带头循坏、单向不带头非循坏
                    • 双向带头循坏、双向带头非循坏、双向不带头循坏、双向不带头非循坏

                    这里我们主要学习以下两中结构：

                    单向不带头非循坏

                    Java数据结构和算法之链表详解

                    LinkedList底层使用的就是双向不带头非循坏

                    Java数据结构和算法之链表详解

                    二、单向不带头非循坏链表的实现

                    创建一个类：

                    public class MySingleList {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    //链表的头节点
    public ListNode head;
}

                    2.1打印链表

                    不带参数的打印

                    public void display() {
    ListNode cur = head;
    if(cur != null) {//遍历完所以节点
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

                    带参数的打印

                    public void display(ListNode newHead) {
    ListNode cur = newHead;
    if(cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

                    2.2求链表的长度

                    public int size(){
    ListNode cur = head;
    int count = 0;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

                    2.3头插法

                    public void addFirst(int data){
    ListNode node = new ListNode(data);
    node.next = head;
    head = node;
}

                    2.4尾插法

                    public void addLast(int data){
    ListNode node = new ListNode(data);
    if(head == null) {
        head = node;
    }else {
        ListNode cur = head;
        while (cur.next != null) {//走到最后一个节点的位置
            cur = cur.next;
        }
        cur.next = node;
    }
}

                    2.5任意位置插入

                    在任意位置插入时我们要判断该位置是否合法，不合法的时候要抛一个异常

                      public void addIndex(int index,int data){
      if(index < 0 || index > size()) {
          throw new IndexException("index位置不合法："+index);
      }
      ListNode node = new ListNode(data);
      if(head == null) {
          head = node;
          return;
      }
      if(index == 0) {
          addFirst(data);
          return;
      }
      if(index == size()) {
          addLast(data);
          return;
      }
      //中间插入
      ListNode cur = serchIndex(index);
      node.next = cur.next;
      cur.next = node;
}

                    找要添加节点位置的前一个节点

                    public ListNode serchIndex(int index) {
    ListNode cur = head;
    int count = 0;
    while (count != index-1) {
        cur = cur.next;
        count++;
    }
    return cur;
}

                    2.6查找是否包含某个元素的节点

                    遍历这个链表找是否与这个元素相同

                    public boolean contains(int key){
    ListNode cur = head;
    while (cur != null) {
        if(cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

                    2.7删除第一次出现这个元素的节点

                    public void remove(int key){
    if(head == null) {
        return;
    }
    if(head.val == key) {
        head = head.next;
        return;
    }
    ListNode cur = findKey(key);
    if(cur == null) {
        return;//没有要删除的元素
    }
    ListNode del = cur.next;
    cur.next = del.next;
}

                    要删除节点的前一个节点

                    public ListNode findKey(int key) {
    ListNode cur = head;
    while (cur.next != null) {
        if(cur.next.val == key) {
            return cur;
        }else {
            cur = cur.next;
        }
    }
    return null;
}

                    2.8删除包含这个元素的所以节点

                    public void removeAllKey(int key){
    if(head == null) {
        return;
    }
    ListNode prev = head;
    ListNode cur = head.next;
    while (cur != null){
        if(cur.val == key) {
            prev.next = cur.next;
            cur = cur.next;
        }else {
            prev = cur;
            cur = cur.next;
        }
    }
    //除了头节点外，其余都删完了
    if(head.val == key) {
        head = head.next;
    }
}

                    2.9清空链表

                    清空链表只需要把头节点置为空

                    public void clear() {
    head = null;
}

                    单向链表的测试

                    public class Test {
    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(30);//尾插
        list.addLast(20);
        list.addLast(30);
        list.addLast(40);
        list.addLast(50);
        list.addFirst(100);//头插
        list.addIndex(2,15);//任意位置插入
        list.display();
        System.out.println("*****");
        System.out.println(list.contains(20));//查看是否包含某个节点
        System.out.println("*****");
        System.out.println(list.size());//求链表长度
        System.out.println("*****");
        list.remove(30);//删除第一个出现的节点
        list.display();
        list.removeAllKey(30);//删除包含这个元素的所以节点
        System.out.println("*****");
        list.display();
        System.out.println("*****");
        list.clear();//清空链表
        list.display();
    }
}

                    Java数据结构和算法之链表详解

                    三、双向不带头非循坏链表的实现

                    创建一个类：

                    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode prev;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;
}

                    3.1打印双向链表

                    public void display(){
    ListNode cur = head;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

                    3.2求双向链表的长度

                    public int size(){
    int count = 0;
    ListNode cur = head;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

                    3.3头插法

                    public void addFist(int data) {
    ListNode node = new ListNode(data);
    if(head == null) {//一个节点都没有的情况
        head = node;
        last = node;
    }else {
        node.next = head;
        head.prev = node;
        head = node;
    }
}

                    3.4尾插法

                    public void addLast(int data) {
    ListNode node = new ListNode(data);
    if(head == null) {//一个节点都没有的情况
        head = node;
        last = node;
    }else {
        last.next = node;
        node.prev = last;
        last = node;
    }
}

                    3.5任意位置插入

                    这里的插入与单向链表一样也需要判断该位置的合法性，不合法时抛一个异常

                    public void addIndex(int index,int data) {
    if(index <android 0 || index > size()) {
        throw new IndexException("双向链表中index的位置不合法："+index);
    }
    if(index == 0) {
        addFist(data);
    }
    if(index == size()) {
        addLast(data);
    }
    ListNode cur = findIndex(index);
    ListNode node = new ListNode(data);
    node.next = cur;
    cur.prev.next = node;
    node.prev = cur.prev;
    cur.prev = node;
}

                    要添加节点的位置

                    public ListNode findIndex(int index) {
    ListNode cur = head;
    if(index != 0) {
        cur = cur.next;
        index --;
    }
    return cur;
}

                    3.6查找是否包含某个元素的节点

                    public boolean contains(int key){
    ListNode cur = head;
    while (cur != null) {
        if(cur.val == key) {
  http://www.devze.com          return true;
        }
        cur = cur.next;
    }
    return false;
}

                    3.7删除第一次出现这个元素的节点

                    因为数据结构是一门逻辑性非常严谨的学科，所以这里的删除需要考虑多种因素

                    public void remove(int key){
    ListNode cur = head;
    while (cur != null) {
        if(cur.val == key) {
            if(cur == head) {
                head = head.next;
                if (head != null) {
                    head.prev = null;
                }else {
                    //只有一个节点，而且是需要删除的节点
                    last = null;
                }
            }else {
                //删除中间节点
                if(cur.next != null) {
                    cur.next.prev = cur.prev;
                    cur.prev.next = cur.next;
                }else {
                    //删除尾巴节点
                    cur.prev.next = cur.next;
                    last = last.prev;
                }
            }
            return;
        }
        cur = cur.next;
    }
}

                    3.7删除包含这个元素的所有节点

                    public void remove(int key){
    ListNode cur = head;
    while (cur != null) {
        if(cur.val == key) {
            if(cur == head) {
                head = head.next;
                if (head != null) {
                    head.prev = null;
                }else {
                    //只有一个节点，而且是需要删除的节点
                    last = null;
                }
            }else {
                //删除中间节点
                if(cur.next != null) {
                    cur.next.prev = cur.prev;
                    cur.prev.next = cur.next;
                }else {
                    //删除尾巴节点
                    cur.prev.next = cur.next;
                    last = last.prev;
                }
            }
        }
        cur = cur.next;
    }
}

                    3.9清空双向链表

                    public void clear(){
    ListNode cur = head;
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.prev = null;
        cur.next = null;
        cur = cur.next;
    }
    head = null;//头节点置空
    last = null;//尾巴节点置空
}

                    双向链表的测试

                    public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);//尾插法
        myLinkedList.addLast(45);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addFist(56);//头插法
        myLinkedList.addIndex(2,15);//任意位置插入
        myLinkedList.display();
        System.out.println(myLinkedList.size());//求双向链表的长度
        System.out.println("******");
        System.out.println(myLinkedList.contains(23));//查找是否包含某个元素的www.devze.com节点
        System.out.println("******");
        myLinkedList.remove(45);//删除第一次出现这个元素的节点
        myLinkedList.display();
        System.out.println("******");
        myLinkedList.removeAllKey(45);//删除包含这个元素的所以节点
        myLinked编程客栈List.display();
        System.out.println("******");
        myLinkedList.clear();//清空链表
        myLinkedList.display();
    }
}

                    Java数据结构和算法之链表详解

                    LinkedList的遍历方式

                    关于LinkedList的遍历方式有四种：

                    public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println(list);
        //for循坏遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        System.out.println("*******");
        //foreach遍历
        for (int m : list) {
            System.out.print(m +" ");
        }
        System.out.println();
        System.out.println("*******");
        //使用迭代器——正向遍历
        ListIterator<编程客栈;Integer> it = list.listIterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();
        System.out.println("*******");
        //使用迭代器——反向遍历
        ListIterator<Integer> it2 = list.listIterator(list.size());
        while (it2.hASPrevious()) {
            System.out.print(it2.previous()+" ");
        }
        System.out.println();
    }
}

                    Java数据结构和算法之链表详解

                    四、ArrayList和LinkedList的区别

                    1.ArrayList在物理上是连续的，LinkedList在逻辑上连续，但在物理上不一定连续

                    2.ArrayList和LinkedList是两种不同的数据结构。ArrayList是基于动态数组的，而LinkedList则是基于链表的

                    3.当需要随机访问元素（如get和set操作）时，ArrayList效率更高，因为LinkedList需要逐个查找。但当进行数据的增加和删除操作（如add和remove操作）时，LinkedList效率更高，因为ArrayList在进行这些操作时需要移动大量数据

                    4.ArrayList需要手动设置固定大小的容量，使用方便但自由性低；而LinkedList能够随数据量变化而动态调整，自由性较高但使用较为复杂

                    到此这篇关于Java数据结构和算法之链表的文章就介绍到这了,更多相关Java链表内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！

                    0

                    上一篇:

                    :下一篇

                    更多 开发 相关资讯：

                    精彩评论

                    暂无评论...
                    登录 注册
                    Qedev.com
                    验证码 换一张
                    取 消

                    关注公众号

                    热门标签

                    图文推荐

                    SpringBoot整合Liquibase实现对数据库管理和迁移

                    SpringBoot整合Liquibase实现对数据库管理和迁移
                    javacv ffmpeg使用原生ffmpeg命令方式

                    javacv ffmpeg使用原生ffmpeg命令方式
                    Linux管道揭秘之匿名管道连接进程世界的方法

                    Linux管道揭秘之匿名管道连接进程世界的方法
                    SpringBoot配置文件启动加载顺序的方法步骤

                    SpringBoot配置文件启动加载顺序的方法步骤
                    SpringBoot前后端传输加密设计实现方案

                    SpringBoot前后端传输加密设计实现方案
                    SpringBoot参数校验的一些实战应用

                    SpringBoot参数校验的一些实战应用
                    Springboot3集成Knife4j的步骤以及使用(最完整版)

                    Springboot3集成Knife4j的步骤以及使用(最完整版)
                    SpringBoot中的@Configuration、@MapperScan注解

                    SpringBoot中的@Configuration、@MapperScan注解

                    开发者开发者网给大家分享系统运维,大数据运维,云计算,编程开发技巧,路由交换,运维和开发相关的资讯及技术文章，同时StackOverflow中文社区，知识经验交流分享。

                    法律声明：本站内容均为网友上传，网站举办方负责审核和监督，如存在版权或非法内容，欢迎举报，我们将尽快予以删除。邮箱：devze@qq.com

                    Copyright © 2018-2020 开发者. All rights reserved. Powered by 开发者ICP备案号: 京ICP备10032868号-9