`
noble510520
  • 浏览: 56089 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

jdk链表笔记

    博客分类:
  • java
阅读更多

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集合框架,包括数组列表、链表、队列、栈、映射等数据结构,以及它们在实际问题中的应用。此外,多线程编程也是Java的一大亮点,笔记会介绍线程的创建与同步机制,如...

    java学习笔记JDK6课件之十三

    另一方面,`LinkedList`采用链表结构,对于频繁的元素插入和删除操作,其性能更好,但随机访问元素的速度相对较慢。 下面是一个简单的示例,展示了如何使用`ArrayList`和`Scanner`来创建和操作一个用户输入的名称...

    马士兵老师HashMap学习笔记

    在JDK 8中,HashMap进行了重大的优化,引入了红黑树(Red-Black Tree)的概念,当链表长度超过一定阈值(默认为8)时,会将链表转换为红黑树,以提高查找效率。在进行put操作时,首先计算键对象的哈希值,然后根据...

    jdk_source_learning:jdk原始码学习笔记,人话翻译

    jdk1.8源码学习笔记,人话翻译 前言:前预算开始学习了一些基本的数据结构和算法,算是被弥补了这方面的知识短板,但是可以对一些算法的了解,目前工作当中也并没有应用到这些,因此希望通过结合实际例子来学习,...

    尚硅谷大厂面试题第二季周阳主讲整理笔记

    在JDK1.8中,HashMap的初始化延迟到第一次put操作,底层结构变为Node数组,同时引入了红黑树,当链表长度达到8时,会转为红黑树以提高查询性能。 【JUC并发编程】 Java并发编程主要涉及java.util.concurrent包,...

    JAVA经典教材笔记

    - JDK(Java Development Kit)安装:包括JDK的下载、安装以及环境变量配置等步骤。 - 编写第一个Java程序:“Hello World”示例,用于验证Java环境是否搭建成功。 #### 第二章:简单Java程序 - 通过编写简单的...

    JAVA笔记(根据马士兵的java视频整理).pdf

    本资源摘要信息是根据马士兵的java视频整理的JAVA笔记,涵盖了JAVA基础知识、数据结构、语法基础、面向对象编程、异常处理、数组、集合类、线程、网络编程、图形化用户接口、元数据、正规表达式、JDK、Java Web编程...

    java面试笔记.pdf

    以下是对笔记中各个部分知识点的详细介绍: 1. Vector和ArrayList的区别: - Vector是同步的,适用于线程安全的环境,但因为同步的实现会导致性能损耗。 - Vector在扩容时将容量翻倍,而ArrayList的扩容方式是增加...

    毕老师javase基础班全程笔记

    8. 集合框架:Java集合框架提供了性能优异的数组、链表、映射和集合等数据结构。框架中的接口和类使程序员可以更方便地操作和管理大量数据。 9. IO流:Java的输入/输出流(IO)机制提供了对不同类型数据源和目的地...

    HashMap.pdf

    - JDK1.7中的HashMap基于数组+链表实现,插入元素时使用的是链表尾部插入。 - JDK1.8中,当链表长度达到8并且容量达到64时,链表会转换为红黑树,以优化搜索效率。当链表长度小于6时,树会转换回链表。如果容量...

    java实战经典学习笔记

    ### Java实战经典学习笔记知识点概览 #### 一、Java概述及开发环境搭建 - **Java概述** - Java是一种广泛使用的高级编程语言,由Sun Microsystems于1995年发布。 - Java的设计目标是“一次编写,到处运行”,这...

    java入门及教学案例及笔记

    - **JDK安装**:Java Development Kit(JDK)是编写Java程序所必需的,包含JRE(Java Runtime Environment)和开发工具。 - **环境变量设置**:配置JAVA_HOME、PATH和CLASSPATH环境变量,确保系统能正确找到Java...

    71-ConcurrentHashMap笔记1

    处理Node时,链表或红黑树会被拆分为两部分,分别放入nextTable的i和i+n位置。当所有数据迁移完成后,nextTable替换原table,然后清空nextTable,更新sizeCtl为新容量的0.75倍。 这种设计巧妙地实现了并发扩容,...

    Java基础(韩顺平版)笔记详

    ### Java基础(韩顺平版)笔记详 #### 一、Java语言概述与环境搭建 - **Java的历史与发展** - Java由Sun Microsystems公司在1995年发布,由James Gosling领导开发。 - 2009年,Oracle公司收购了Sun Microsystems...

    哈希表学习笔记.docx

    ### 哈希表学习笔记知识点详述 #### 一、什么是哈希表? 哈希表是一种高效的数据存储结构,其基本思想是通过一个特定的函数(哈希函数或散列函数)将输入的关键字映射到一个固定大小的空间内,从而实现数据的快速...

    传智播客视频JavaSE学习笔记

    以上是根据传智播客视频JavaSE学习笔记总结的关键知识点,覆盖了Java基础环境配置、字符串操作、多线程编程、集合框架、输入输出流、网络编程、反射机制、正则表达式等多个方面,希望对Java初学者和进阶者有所帮助。

    Java笔记与作业

    1. **环境配置**:安装JDK(Java Development Kit),配置JAVA_HOME环境变量,设置classpath,理解编译和运行Java程序的基本流程。 2. **基本语法**:变量、数据类型(包括基本类型和引用类型)、运算符、控制流...

    java基础 个人笔记

    开始Java编程前,需要安装Java Development Kit(JDK),设置好环境变量PATH和JAVA_HOME。同时,了解并掌握集成开发环境(IDE)如Eclipse或IntelliJ IDEA的使用,它们能提高开发效率。 3. **语法基础** - **数据...

    对你有用的JAVA笔记

    LinkedList基于链表,插入删除快但访问慢。 - **HashSet**和**HashMap**:无序不重复元素的集合和键值对的集合,HashMap允许快速查找。 - **ArrayList, LinkedList, HashSet, HashMap**等都实现了接口`List`, `Set...

    马士兵J2SE第七章容器个人学习笔记.pdf

    - 线程安全性:两者都不是线程安全的,但在JDK 1.0中,`Vector`(`ArrayList`的前身)是线程安全的,性能相对较差。 【HashMap与HashTable的区别】 1. 线程安全:`HashMap`是非线程安全的,`HashTable`是线程安全的...

Global site tag (gtag.js) - Google Analytics