不同于单链表，这里没有头节点，所有的节点都是存数据的
// 存储数据结构
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;
}
}
transient int size = 0;
//头指针
transient Node first;
//尾指针
transient Node last;
构造函数
public linkedList() {
}
public linkedList(Collection c) {
this();
addAll(c);
}
add()
// 存储数据结构
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;
}
}
transient int size = 0;
//头指针
transient Node first;
//尾指针
transient Node last;
public boolean add(E e) {
linkLast(e);
return true;
}
//链表末尾添加元素
void linkLast(E e) {
//获取最后的节点
final Node l = last;
//新建节点，并且设置其的前驱节点为之前的尾节点
final Node newNode = new Node<>(l, e, null);
//更新尾结点变量
last = newNode;
//前面的节点是否为空要进行不同处理
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
linkLast()流程 add(int index)
- if (l == null) 这个判断是为了处理前面的节点可能为空的情况，如果为空要设置新增的这个节点为头节点（即它既是头指针也是尾指针所指向的元素），如果不为空的话，那么l所指向的节点是应该存储新节点的地址的。
- 总结得到在尾部新增元素的结论：
- 得到之前最尾部的元素(l)
- 新建节点(newNode)，设置新节点的前驱节点为(l)
- 设置指针记录变量(last)存储newNode的地址
- 考虑之前的节点l是否存在的情况，分开处理（见上1）
public void add(int index, E element) {
//越界检查
checkPositionIndex(index);
if (index == size)
//如果需要插入的位置在末尾
linkLast(element);
else
//需要插入的位置在之前
linkBefore(element, node(index));
}
void linkBefore(E e, Node succ) {
// assert succ != null;
//找到的节点的前驱节点(pred)-新节点(newNode)-找到的节点(succ)
final Node pred = succ.prev;
//新增节点，设置新增节点的前驱节点和后继节点
final Node newNode = new Node<>(pred, e, succ);
//设置找到节点(succ)的前驱节点为新节点，因为节点(succ)必会存在
succ.prev = newNode;
//(pred)可能会不存在
if (pred == null)
//(pred)不存在那头节点变量就应该是新建的节点（newNode）
first = newNode;
else
//(pred存在就设置为)
pred.next = newNode;
size++;
modCount++;
}
node(int index)
Node node(int index) {
// assert isElementIndex(index);
// 从前或者从后面取遍历寻找，(size >> 1)为size/2，非常巧妙
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;
}
//没有找到就返回最前或者最后的元素
}
get(int index)
// Positional Access Operations
public E get(int index) {
checkElementIndex(index);
//也是利用的node(index)
return node(index).item;
}
getFirst(), getLast()
获取第一个元素， 和获取最后一个元素:
public E getFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
removeFirest(), removeLast(), remove(e), remove(index)
remove()方法也有两个版本，一个是删除跟指定元素相等的第一个元素remove(Object o)，另一个是删除指定下标处的元素remove(int index)。
删除元素 - 指的是删除第一次出现的这个元素, 如果没有这个元素，则返回false；判断的依据是equals方法， 如果equals，则直接unlink这个node；由于linkedList可存放null元素，故也可以删除第一次出现null的元素；
public boolean remove(Object o) {
if (o == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
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; // GC
size--;
modCount++;
return element;
}
remove(int index)使用的是下标计数， 只需要判断该index是否有元素即可，如果有则直接unlink这个node。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
@pdai: 代码已经复制到剪贴板
删除head元素:
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node f) {
// assert f == first && f != null;
final E element = f.item;
final Node 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;
}
删除last元素:
public E removeLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node l) {
// assert l == last && l != null;
final E element = l.item;
final Node 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;
}
addAll()
addAll(index, c) 实现方式并不是直接调用add(index,e)来实现，主要是因为效率的问题，另一个是fail-fast中modCount只会增加1次；
public boolean addAll(Collection c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node 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 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;
}
clear()
为了让GC更快可以回收放置的元素，需要将node之间的引用关系赋空。
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node x = first; x != null; ) {
Node next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
Positional Access 方法
通过index获取元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
将某个位置的元素重新赋值:
public E set(int index, E element) {
checkElementIndex(index);
Node x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
将元素插入到指定index位置:
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
删除指定位置的元素:
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
其它位置的方法:
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
查找 *** 作的本质是查找元素的下标:
查找第一次出现的index, 如果找不到返回-1；
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
@pdai: 代码已经复制到剪贴板
查找最后一次出现的index, 如果找不到返回-1；
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
Queue 方法
public E peek() {
final Node f = first;
return (f == null) ? null : f.item;
}
public E element() {
return getFirst();
}
public E poll() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E remove() {
return removeFirst();
}
public boolean offer(E e) {
return add(e);
}
Deque 方法
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
public E peekFirst() {
final Node f = first;
return (f == null) ? null : f.item;
}
public E peekLast() {
final Node l = last;
return (l == null) ? null : l.item;
}
public E pollFirst() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollLast() {
final Node l = last;
return (l == null) ? null : unlinkLast(l);
}
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）