LinkedList
LinkedList是双链表,并且有头尾指针
数据结构
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable { transient int size = 0; transient Node first; transient Node last; public LinkedList() { }
他持有头节点和未节点,并且初始的时候,这两个节点都为null
private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
这是节点的结构,有一个数据域和前后指针
功能实现
1.随机访问的优化node(index)
Node node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
该方法是随机访问的基础实现,用于获取根据下标获取节点,亮点在于,先判断index是size的前半段还是后半段,来决定是用头节点遍历还是为节点来遍历,这样会提高随机访问的效率
2.要有解除引用的习惯
unlinkFirst、unlinkLast、unlink、clear,这种删除节点的方法,都会把该节点的所有引用以及其他对象对该节点的引用都设为null,这样可以help gc
E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
我非常喜欢这个方法,他非常灵活,他是remove操作的基础实现,他的亮点在于最大限度的help gc,减小了内存的损耗。在有些数据结构的书中,remove完,没有把相关舍弃的引用设为null,这给gc加大了难度
3.只在迭代器中持有游标
4.hasNext和next
习惯上,人们会先调用hasNext(),再调用next(),但是jdk中对于next()中的实现,也会调用一次hasNext(),如果false则会抛出NoSuchElementException,防止被意外调用(因为这个方法暴露了)
5.迭代器中remove和set是对最后一个从迭代器返回的元素进行操作
6.针对foreach
凡事实现了Iterator都可以使用foreach语句
因为foreach进过jvm编译了之后,其实就是调用了Iterator的hasNext()和next()
那么为什么foreach只能改变引用不能改变值呢?
因为next()返回的是一个Node中的数据域,而不是Node
7.toArray(T[] a)
如果a的容量不够的话,会创建一个泛型数组
具体方法:
@SuppressWarnings("unchecked") public T[] toArray(T[] a) { if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; Object[] result = a; for (Node x = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; }
查看原文:http://blog.zswlib.com/2016/10/26/jdk%e4%b8%ad%e9%93%be%e8%a1%a8%e7%ac%94%e8%ae%b0/
相关推荐
随着对基础知识的掌握,笔记会进一步带你探索Java集合框架,包括数组列表、链表、队列、栈、映射等数据结构,以及它们在实际问题中的应用。此外,多线程编程也是Java的一大亮点,笔记会介绍线程的创建与同步机制,如...
另一方面,`LinkedList`采用链表结构,对于频繁的元素插入和删除操作,其性能更好,但随机访问元素的速度相对较慢。 下面是一个简单的示例,展示了如何使用`ArrayList`和`Scanner`来创建和操作一个用户输入的名称...
在JDK 8中,HashMap进行了重大的优化,引入了红黑树(Red-Black Tree)的概念,当链表长度超过一定阈值(默认为8)时,会将链表转换为红黑树,以提高查找效率。在进行put操作时,首先计算键对象的哈希值,然后根据...
jdk1.8源码学习笔记,人话翻译 前言:前预算开始学习了一些基本的数据结构和算法,算是被弥补了这方面的知识短板,但是可以对一些算法的了解,目前工作当中也并没有应用到这些,因此希望通过结合实际例子来学习,...
在JDK1.8中,HashMap的初始化延迟到第一次put操作,底层结构变为Node数组,同时引入了红黑树,当链表长度达到8时,会转为红黑树以提高查询性能。 【JUC并发编程】 Java并发编程主要涉及java.util.concurrent包,...
- JDK(Java Development Kit)安装:包括JDK的下载、安装以及环境变量配置等步骤。 - 编写第一个Java程序:“Hello World”示例,用于验证Java环境是否搭建成功。 #### 第二章:简单Java程序 - 通过编写简单的...
本资源摘要信息是根据马士兵的java视频整理的JAVA笔记,涵盖了JAVA基础知识、数据结构、语法基础、面向对象编程、异常处理、数组、集合类、线程、网络编程、图形化用户接口、元数据、正规表达式、JDK、Java Web编程...
以下是对笔记中各个部分知识点的详细介绍: 1. Vector和ArrayList的区别: - Vector是同步的,适用于线程安全的环境,但因为同步的实现会导致性能损耗。 - Vector在扩容时将容量翻倍,而ArrayList的扩容方式是增加...
8. 集合框架:Java集合框架提供了性能优异的数组、链表、映射和集合等数据结构。框架中的接口和类使程序员可以更方便地操作和管理大量数据。 9. IO流:Java的输入/输出流(IO)机制提供了对不同类型数据源和目的地...
- JDK1.7中的HashMap基于数组+链表实现,插入元素时使用的是链表尾部插入。 - JDK1.8中,当链表长度达到8并且容量达到64时,链表会转换为红黑树,以优化搜索效率。当链表长度小于6时,树会转换回链表。如果容量...
### Java实战经典学习笔记知识点概览 #### 一、Java概述及开发环境搭建 - **Java概述** - Java是一种广泛使用的高级编程语言,由Sun Microsystems于1995年发布。 - Java的设计目标是“一次编写,到处运行”,这...
- **JDK安装**:Java Development Kit(JDK)是编写Java程序所必需的,包含JRE(Java Runtime Environment)和开发工具。 - **环境变量设置**:配置JAVA_HOME、PATH和CLASSPATH环境变量,确保系统能正确找到Java...
处理Node时,链表或红黑树会被拆分为两部分,分别放入nextTable的i和i+n位置。当所有数据迁移完成后,nextTable替换原table,然后清空nextTable,更新sizeCtl为新容量的0.75倍。 这种设计巧妙地实现了并发扩容,...
### Java基础(韩顺平版)笔记详 #### 一、Java语言概述与环境搭建 - **Java的历史与发展** - Java由Sun Microsystems公司在1995年发布,由James Gosling领导开发。 - 2009年,Oracle公司收购了Sun Microsystems...
### 哈希表学习笔记知识点详述 #### 一、什么是哈希表? 哈希表是一种高效的数据存储结构,其基本思想是通过一个特定的函数(哈希函数或散列函数)将输入的关键字映射到一个固定大小的空间内,从而实现数据的快速...
以上是根据传智播客视频JavaSE学习笔记总结的关键知识点,覆盖了Java基础环境配置、字符串操作、多线程编程、集合框架、输入输出流、网络编程、反射机制、正则表达式等多个方面,希望对Java初学者和进阶者有所帮助。
1. **环境配置**:安装JDK(Java Development Kit),配置JAVA_HOME环境变量,设置classpath,理解编译和运行Java程序的基本流程。 2. **基本语法**:变量、数据类型(包括基本类型和引用类型)、运算符、控制流...
开始Java编程前,需要安装Java Development Kit(JDK),设置好环境变量PATH和JAVA_HOME。同时,了解并掌握集成开发环境(IDE)如Eclipse或IntelliJ IDEA的使用,它们能提高开发效率。 3. **语法基础** - **数据...
LinkedList基于链表,插入删除快但访问慢。 - **HashSet**和**HashMap**:无序不重复元素的集合和键值对的集合,HashMap允许快速查找。 - **ArrayList, LinkedList, HashSet, HashMap**等都实现了接口`List`, `Set...
- 线程安全性:两者都不是线程安全的,但在JDK 1.0中,`Vector`(`ArrayList`的前身)是线程安全的,性能相对较差。 【HashMap与HashTable的区别】 1. 线程安全:`HashMap`是非线程安全的,`HashTable`是线程安全的...