java源码-LinkedList
开篇
LinkedList基于链表实现,在List中间进行插入和删除的代价较低,提供了优化的顺序访问。LinkedList在随机访问方面相对比较慢,但是它的特性集较ArrayList更大。
LinkedList的实现是一个双向链表,LinkedList存储的Node节点包含指向前置后置节点的指针。
LinkedList类图
LinkedList类定义
LinkedList的类定义中包含first节点和last节点,通过first节点(指向头节点)和last节点(指向尾节点)将串联所有的list中的节点,看下Node的定义就知道了。
Node的prev和next节点分别指向前后节点。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; // 指向LinkedList的第一个节点 transient Node<E> first; // 指向LinkedList的最后一个节点 transient Node<E> last; private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } }
LinkedList构造函数
LinkedList的构造函数非常简单,关键是看下参数为Collection的构造函数,在该构造函数当中通过addAll()方法将元素通过尾插入法添加到LinkedList当中。allAll参数的index标记从哪个位置开始插入。
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); } public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { // 确定是否超过index的下标 checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; // 确定插入位置的前后节点位置,pred是前置节点,succ是后置节点 Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } // 直接采用链表插入法插入即可 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }
LinkedList常用操作
LinkedList的add方法
LinkedList的add()方法其实非常简单,就是在LinkedList的尾部进行插入,然后更新last节点就可以了。
public boolean add(E e) { linkLast(e); return true; } // 在尾部插入新的值 void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } // 设计巧妙,力求最少时间定为索引位置 Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } // 在合适的节点之前插入 void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
LinkedList的remove方法
LinkedList的remove()的方法也非常简单,通过移除头部节点即可,然后将first节点后移即可。
public E remove() { return removeFirst(); } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }
LinkedList的indexOf方法
LinkedList的indexOf()方法主要从first到last进行遍历依次比较即可。
public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
LinkedList迭代器
LinkedList的迭代器主要分为两个:
- iterator主要是在AbstractList类中定义,通过java的多态性调用LinkedList的size()方法和get()方法实现索引的比较和数据的获取等。
- listIterator在LinkedList类中实现,通过index指定迭代器开始遍历的位置,通过前后指针进行next移动,通过index和size比较是否遍历完成。
public Iterator<E> iterator() { return new Itr(); } private class Itr implements Iterator<E> { int cursor = 0; int lastRet = -1; int expectedModCount = modCount; // 调用LinkedList的size()方法 public boolean hasNext() { return cursor != size(); } public E next() { checkForComodification(); try { int i = cursor; // get()方法调用的是LinkedList的方法 E next = get(i); lastRet = i; cursor = i + 1; return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } }
public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } }

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Python全栈 MySQL 数据库 (索引、数据导入、导出)
ParisGabriel 每天坚持手写一天一篇 决定坚持几年 为了梦想为了信仰 开局一张图 表字段重命名(change) alter table 表名 change 原名 新名 数据类型; SQL查询 执行顺序: 3. select ...聚合函数 from 表名 1. where ... 2. group by... 4. having... 5. order by... 6. limit... group by 语句 作用:给查询结果进行 分组 注意: 1. group by之后的 字段必须要为 select之后的 字段名 2. 如果select之后的字段和group by 之后的 字段不一致,则 必须对 字段 进行聚合处理(聚合函数) having 语句 作用:对查询结果 进一步筛选 注意: 1. having语句通常和 group by联合使用, 过滤由 group by语句 返回的记录集 2. where只能操作表中 实际存在的 字段, having by可操作由聚合函数生成的显示列 di...
- 下一篇
用树莓派和DS18B20做个汽车温度记录仪
原文: 用树莓派和DS18B20做个汽车温度记录仪 用树莓派和DS18B20做个汽车温度记录仪[原创] 很想知道夏日阳光暴晒下,汽车内的最高温度以及温度的变化情况。觉得用树莓派和DS18B20来实现应该很简单,于是就尝试捣鼓了一下,半天时间就搞定了,写下来和大家分享。以下原创内容欢迎网友转载,但请注明出处:http://blog.163.com/he_lesheng 一、树莓派读取DS18B20的温度值 Raspbian系统已经能够支持DS18B20单总线(1-wire)温度传感器,只要简单配置就可以直接读取,无需自己编写底层驱动。 配置过程也很简单: 打开Raspbian系统的/boot/config.txt文件,在最后一行添加如下代码。 dtoverlay=w1-gpio-pullup,gpiopin=17 其中最后一个数字17表示:树莓派和DS18B20连接所使用的扩展引脚编号,即下表中BCM编码列中对应的数字。可根据需要选择树莓派40pin扩展口中的任意引脚。 图1 树莓派40Pin引脚对照表 修改完config.txt后关机,将DS18B20的数据脚(T...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS关闭SELinux安全模块
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装