LinkedList与ArrayList有这很大的区别,前者是由链组合而成,每个链表的节点持有前、后节点的信息。用下面这副图可以简单描述处链表的结构:
链表有三个非常重要的属性,节点总个数、链表头元素、链表为元素。
链表有三个非常重要的属性,节点总个数、链表头元素、链表为元素。
transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ 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; } }
一、初始化
分别是无参的构造以及带有集合参数的构造方法。
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }二、添加元素
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++; }看代码很简单:
1、首先将last节点赋值给临时节点l,声明新的节点newNode,新元素所标示的下一节点为空。
2、添加元素默认是从尾部添加,更新newNode为last节点。
3、然后判断是不是空链表,如果是则更新newNode为首节点,否则将原来未节点的下一节点更新为newNode。
4、同时更新链表总条数、结构的修改次数。
三、添加头部元素
private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }代码逻辑也是非常简单。
1、将首节点指向临时节点l。
2、声明新的首节点newNode,且该节点的上一个节点为空。
3、将newNode指定为首节点,同时判断链表是否为,如果为空则那么newNode同时也是尾节点;如果不为空则将之前首节点的上一元素指向newNode。
4、同时更新链表总条数、结构的修改次数
四、添加集合
添加集合包含两个方法,添加到尾部、添加到指定索引点。其实底层都是调用的同一个方法即添加到指定索引点,那么添加到尾部的方法就是添加到index索引点。
private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; }1、首先判断了插入的索引点是否在区间[0,size],如果不在直接抛出下标越界异常,则直接返回不再执行后面代码。
public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; 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; }2、将集合转化为对象数组,并判断数字长度是否等于0,如果等于0则直接退出
3、声明两个节点pred,succ。如果插入索引点等于size,说明是尾部插入,succ=null,pred=last;否则,将节点定位到index处,注意该处的小技巧:判断index在前半边还是后半边,然后以最快的速度定位,不过由此也可以看出链表是多么的不适合检索啊。将succ=node(index),pred=succ.prev。
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; } }
4、将步骤2的数组循环组装为节点信息并放入index为起始点处。实际就是将数组放以index节点的前一节点为尾节点的链表进行尾追加,而pre就标示尾节点。
5、如果是尾部插入则设置last;如果不是则处理新追加数组的尾节点的下一结点,以及index节点的前一节点。6、同时更新链表总条数、结构的修改次数
五、移除指定元素
public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
1、从first节点开始遍历,且节点不为空。首先判断移除的对象是否为空,如果元素节点值为空,移除该元素;如果不为空,选择节点值等于移除对象的节点,移除该节点。
E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> 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; }
2、移除节点,将该节点的上一节点的next节点设置为该节点的下以节点;将该节点的下一节点的pre节点设置为该节点的上一节点;同时设置该节点的值为null。
3、同时更新链表总条数、结构的修改次数
六、移除指定索引的元素
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
1、首先判断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; } }
2、这个步骤是不是看着很熟悉,跟步骤四相同。然后移除元素。
还有其他的操作添加集合、指定位置添加集合、是否包含元素、pop等等操作,源码相对来说还是比较简单。
总结:linkedList是由链表组成的。从上述部分代码中可以看出,linkedList在添加、删除元素的时候是非常简捷的,无非就是修改前一节点的next以及后一节点的pre,同时设置本节点的pre和next。但是在搜索的时候按照源码的写法要遍历一般的元素才可以,就这点来说跟由数组组成的ArrayList相比是比较低效的。
链表在日常开发中经常用到,下篇对链表做下扩展介绍。
相关推荐
LinkedList源码
这是我从JDK中拿出的Arraylist,Vector,LinkedList源码,自己看源码的时候弄出来的,并写了一点自己的分析,仅供源码分析者使用
学习linkedList源码,数据结构是链表。模仿LinkedList集合自己写一个
LinkedList源码分析_016.pdf
第三章 LinkedList源码解析一、对于LinkedList需要掌握的八点内容LinkedList的创建:即构造器往LinkedList中添加对象:即add
LinkedList的部分源码解析 包括部分常用的方法: add() ,remove(),get(),set()
LinkedList源码分析,java作业,主要是对rar包中的LinkedList分析
主要给大家介绍了关于Java基于JDK 1.8的LinkedList源码的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
主要介绍了java LinkedList源码详解及实例的相关资料,需要的朋友可以参考下
主要为大家详细介绍了Java集合系列之LinkedList源码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
单双链表的创建,节点的添加与删除,链表逆序,链表遍历。
LinkedList 是一个常用的集合类,用于顺序存储元素。 LinkedList 经常和 ArrayList 一起被提及。大部分人应该都知道 ArrayList 内部采用数组保存元素,适合用于随机访问比较多的场景,而随机插入、删除等操作因为...
LinkedList是通过节点的连接实现链表的数据结构,向linkedList中插入或删除元素的速度是特别快,而随机访问的速度相对较慢,这个是由于链表本身的性质造成的,在链表中,每个节点都包含了前一个节点的引用,后一个...
LINKED LISTS 15 source codes
ArrayList-LinkedList-源码.rar
Map+List+ArrayList+LinkedList Java源代码,适合初学者
计算机后端-Java-Java核心基础-第24章 集合01 15. LinkedList的源码分析.avi
源码解析jdk7.0集合:LinkedList的底层实现原理.pdf
java list 源码
能学到什么:ArrayList的源码分析,自动扩容和自动缩容的源码分析,相关参数的深度解析,从是什么,为什么,怎么做三个角度进行讲解,用通俗易懂的白话进行介绍,LinkedList和Vector以及ArrayList的区别以及使用场景...