【Java 数据结构】双向链表(下)

简介: 上期我们实现了一下单链表,在Java(1.8)中,链表为 LinkedList,而底层是一个双向链表,跟 ArrayList 一样,LinkedList 也实现了 List 接口,这里我们画一个图,让大家简单见识下双向链表:

2.7 clear 方法

public void clear() {
    // 遍历链表
    ListNode cur = this.head;
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.prev = null;
        cur.next = null;
        cur = curNext;
    }
    this.head = null;
    this.last = null;
    this.size = 0;
}

双向链表的清空方法可不能直接头节点置空,因为直接头节点置空的话,别忘了Java中是某一块空间没有被引用的时候,才会被自动回收掉,但是这是双向链表,中间节点都是互相引用的,所以我们需要每个都手动置空,我们要定义一个curNext引用,指向cur的下一个,防止置空cur的指针域的时候,cur找不到下一个节点了!最后别忘了 size 要等于 0,不然会出问题的! ̄︶ ̄∗ ̄︶ ̄∗)

2.8 size 方法

这个方法还是很很简单的,直接 return this.size; 不就可以了吗?

3、LinkedList 的学习

3.1 认识下 LinkedList


  • LinkedList 并没有像 ArrayList 一样实现 RandomAccess 接口,所以 LinkedList 并不支持随机访问
  • LinkedList 实现了Cloneable接口,表明 LinkedList 是可以clone的
  • LinkedList 实现了Serializable接口,表明 LinkedList 是支持序列化的
  • LinkedList 在任意位置插入和删除时效率比较高,时间复杂度为O(1)


接着来看一看 LinkedList 里面的成员变量:

3.2 LinkedList 的构造方法

Java 中的 LinkedList 提供了两个构造方法:

image.png

使用构造方法例子:

public static void main(String[] args) {
    // 构造一个空的双向链表
    LinkedList<Integer> list1 = new LinkedList<>(); // 直接构造
    List<Integer> list2 = new LinkedList<>(); // 向上转型
    // 使用ArrayList构造LinkedList
    ArrayList<Integer> arrayList = new ArrayList<>();
    arrayList.add(1);
    arrayList.add(2);
    arrayList.add(3);
    LinkedList<Integer> list3 = new LinkedList<>(arrayList);
    List<Integer> list4 = new LinkedList<>(arrayList);
}

至于LinkedList当中还有特别多的方法,小伙伴们下去可以自行查阅手册,这里就不多讲述了!

3.3 LinkedList 的遍历

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    for (int i = 1; i <= 5; i++) {
        list.add(i); //add默认是尾插
    }
    // 方法1:使用foreach遍历
    for (int x : list) {
        System.out.print(x + " ");
    }
    System.out.println();
    // 方法2:使用迭代器遍历->正向遍历
    ListIterator<Integer> it = list.listIterator();
    while (it.hasNext()) {
        System.out.print(it.next() + " ");
    }
    System.out.println();
    // 方法3:使用迭代器遍历->反向遍历
    ListIterator<Integer> rit = list.listIterator(list.size());
    while (rit.hasPrevious()) {
        System.out.print(rit.previous() + " ");
    }
    System.out.println();
}

迭代器后期也会逐步接触到,这里能看得懂就ok了!

4、ArrayList 和 LinkedList 的区别

首先我们来说它们的相同点,都是Java中的集合,都是顺序结构,都实现了 List 接口等其他的接口。


重点是他们的区别,也就是不同点!


  • 从存储的角度来说,ArrayList 一定是空间连续的,因为底层是数组,数组是一块连续的存储空间,而 LinkedList 的空间不一定连续,每个节点是依靠节点的指针域进行连接起来的。
  • 从访问元素的角度来说,ArrayList 支持下标随机访问,而 LinkedList 并不支持,而且时间复杂度还是 O(n)。
  • 插入和删除的角度来说,ArrayList 尾插,尾删还好,其他都需要挪动元素了,效率低,时间复杂度是 O(n),而对于 LinkedList 来说,只需要修改指向即可,时间复杂度是 O(1)。
  • 从空间的角度来说,ArrayList 容量不够需要扩容,而 LinkedList 并没有扩容的概念,每次插入都会 new 一个新的节点。
  • 从应用场景的角度来说(目前的知识层面上),ArrayList 更适合频繁用到随机访问,而LinkedList 更适合频繁的插入和删除。
相关文章
|
1月前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
44 1
|
1月前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
82 2
|
1月前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
61 2
|
16天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
36 6
|
22天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
23天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
50 4
|
25天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
25天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
30天前
|
存储 算法 Java
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用,掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
30 6
|
1月前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
29 1
下一篇
无影云桌面