ArrayList的介绍
1、LinkedList的简介
List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
2、ArrayList的构造函数
//构造一个默认函数
public LinkedList()
//构造一个构造函数，并添加数据
public LinkedList(Collection<? extends E> c)
ArrayList的数据结构
LinkedList的重要字段说明
first：双向列表的表头
last：双向列表的尾
size：列表的大小
modCount：实现fail-fast机制，不同线程对同一个集合进行操作是的错误机制
LinkedList的重要方法源码解析
LinkedList实际上是通过双向链表去实现的。既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。但是它也实现了List接口，也可以用索引值的方式获取数据
//添加数据到链表中
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) { //根据下标查询节点
if (index < (size >> 1)) { // size/2<下标从末尾往前递归 index < size/2 从表前往后递归
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 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++;
}
//先把succ的前节点设置为新节点，然后判断succ的前节点是否为空，为空就把新节点赋值为表头，否则置为succ最开始前节点的下一个子节点
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++;
}
public boolean addAll(Collection<? extends E> c) { //添加一组数据到链表中
return addAll(size, c);
}
//添加一组数据到指定位置
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;
}
//从链表获取数据
public E get(int index) { //通过下标获取数据 先检测是否下标越界 然后通过node(index)获取节点，并获取节点的数据
checkElementIndex(index);
return node(index).item;
}
//获取头节点
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//获取尾节点
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
//节点的删除
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;
}
public E remove() { //删除表头
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast() { //删除表尾
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
public E remove(int index) { //删除下标数据
checkElementIndex(index);
return unlink(node(index));
}
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;
}
public boolean removeLastOccurrence(Object o) { //删除相同数据的末尾一个
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
private E unlinkLast(Node<E> l) { //删除末尾数据
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
public boolean removeFirstOccurrence(Object o) { //删除第一个数据
return remove(o);
}
//实现Deque接口其中的重要方法源码
public E peek() { //只是返回节点
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E pop() { //返回并删除节点
return removeFirst();
}
public E poll() { //返回并删除头节点
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
从它的数据结构可以知道，它是没有容量限制的，它的克隆函数，就是把LinkedList克隆到一个新的LinkedList中，subList调用的AbstractList中的方法，返回不是一个拥有LinkedList所有方法和功能的对象，是一个继承了AbstractList重写的对象,LinkedList可以作为队列（先进先出），也可以做为栈（先进后出）
LinkedList的遍历方式
1、通过迭代器的方式去实现，既Iterator的方式
Iterator iterator = list.iterator;
while(iterator.hasNext()){
String value = iterator.next();
}
2、通过索引随机访问，ArrayList默认实现了RandomAccess
for(int i = 0;i<size;i++){
String value = list.get(i);
}
3、通过ForEach循环遍历
for(String str:list){
String value = str;
}
4、通过pollFirst()来遍历
white(list.pollFirst() != null){
}
5、通过PollLast来遍历
white(list.pollLast() != null){
}
6、通过removeFirst()来遍历
white(list.removeFirst() != null){
}
6、通过removeLast()来遍历
white(list.removeLast() != null){
}
4、5、6、7的效率会高点(他们的实现方式基本相同) 他们会删除原始数据 如果只想去除数据3的效率会高点
网友评论