Detailed explanation of LinkedList in Java collections
- 黄舟Original
- 2017-03-13 17:30:431519browse
LinkedList is a doubly linked list that inherits AbstractSequentialList. It can also be operated as a stack, queue or double-ended queue.
LinkedList implements the List interface and can perform queue operations on it.
LinkedList implements the Seque interface and can use LinkedList as a double-ended queue.
LinkedList implements Cloneable, covers the clone function, and can be cloned.
LinkedList implements Serializable and can be serialized.
LinkedList is not thread-safe.
LinkedList sample program:
public class Hello {
public static void main(String[] args) {
testLinkedListAPIs() ;
useLinkedListAsLIFO();
useLinkedListAsFIFO();
}
private static void testLinkedListAPIs()
{
String val = null;
LinkedList llist = new LinkedList();
//添加是哪个元素
llist.add("1");
llist.add("2");
llist.add("3");
llist.add(1, "4");//在第一个元素后面插入4
System.out.println("\nTest \"addFirst(), removeFirst(), getFirst()\"");
llist.addFirst("10");//将10插入并作为第一个元素
System.out.println("llist:"+llist);
System.out.println("llist.removeFirst():"+llist.removeFirst());//删除掉第一个元素
System.out.println("llist:"+llist);
System.out.println("llist.getFirst():"+llist.getFirst());//获得第一个元素
System.out.println("\nTest \"offerFirst(), pollFirst(), peekFirst()\"");
llist.offerFirst("10");//添加第一个元素
System.out.println("llist:"+llist);
System.out.println("llist.pollFirst():"+llist.pollFirst());//去掉第一个元素
System.out.println("llist:"+llist);
System.out.println("llist.peekFirst():"+llist.peekFirst());//读取第一个元素
System.out.println("\nTest \"addLast(), removeLast(), getLast()\"");
llist.addLast("20");//链尾添加元素20
System.out.println("llist:"+llist);
System.out.println("llist.removeLast():"+llist.removeLast());//删掉链尾元素20
System.out.println("llist:"+llist);
System.out.println("llist.getLast():"+llist.getLast());//读取链尾元素
System.out.println("\nTest \"offerLast(), pollLast(), peekLast()\"");
llist.offerLast("20");//添加链尾元素20
System.out.println("llist:"+llist);
System.out.println("llist.pollLast():"+llist.pollLast());//删掉链尾元素20
System.out.println("llist:"+llist);
System.out.println("llist.peekLast():"+llist.peekLast());//读取链尾元素
llist.set(2, "300");//替换第三个元素
System.out.println("\nget(3):"+llist.get(2));//获得第三个元素
String[] arr = (String[])llist.toArray(new String[0]);//得到数组
for (String str:arr)
{
System.out.println("str:"+str);
System.out.println("size:"+llist.size());
llist.clear();
System.out.println("isEmpty():"+llist.isEmpty()+"\n");
}
}
private static void useLinkedListAsLIFO()
{
System.out.println("\nuseLinkedListAsLIFO");
LinkedList stack = new LinkedList();
//类似于栈输入
stack.push("1");
stack.push("2");
stack.push("3");
stack.push("4");
System.out.println("stack:"+stack);
System.out.println("stack.pop():"+stack.pop());//出栈
System.out.println("stack.peek():"+stack.peek());//只输出栈顶元素并不出栈
System.out.println("stack:"+stack);
}
private static void useLinkedListAsFIFO()
{
System.out.println("\nuseLinkedListAsFIFO");
LinkedList queue = new LinkedList();
//类似于队列，入队
queue.add("10");
queue.add("20");
queue.add("30");
queue.add("40");
System.out.println("queue:"+queue);
System.out.println("queue.remove():"+queue.remove());//队列出队
System.out.println("queue.element():"+queue.element());//读取队头，并不删除元素
System.out.println("queue:"+queue);
}
}Output result:
Test "offerLast(), pollLast(), peekLast()" llist:[1, 4, 2, 3, 20] llist.pollLast():20 llist:[1, 4, 2, 3] llist.peekLast():3 get(3):300 str:1 size:4 isEmpty():true str:4 size:0 isEmpty():true str:300 size:0 isEmpty():true str:3 size:0 isEmpty():true useLinkedListAsLIFO stack:[4, 3, 2, 1] stack.pop():4 stack.peek():3 stack:[3, 2, 1] useLinkedListAsFIFO queue:[10, 20, 30, 40] queue.remove():10 queue.element():20 queue:[20, 30, 40]
LinkedList source code:
public class LinkedList1a4db2c2c2313771e5742b6debf617a1 extends AbstractSequentialList1a4db2c2c2313771e5742b6debf617a1
implements List1a4db2c2c2313771e5742b6debf617a1, Deque1a4db2c2c2313771e5742b6debf617a1, Cloneable, java.io.Serializable
{
transient int size = 0; //其实大小为0
transient Node1a4db2c2c2313771e5742b6debf617a1 first; //第一个节点
transient Node1a4db2c2c2313771e5742b6debf617a1 last; //最后一个节点
public LinkedList() { //构造一个空LinkedList
}
public LinkedList(Collection216930c0ab3d232ff5eb2d5ba8cef959 c) { //构造一个带有输入集合的
this();
addAll(c);
}
private void linkFirst(E e) { //链接第一个节点
final Node1a4db2c2c2313771e5742b6debf617a1 f = first;
final Node1a4db2c2c2313771e5742b6debf617a1 newNode = new Nodea8093152e673feb7aba1828c43532094(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
void linkLast(E e) { //链接最后一个节点
final Node1a4db2c2c2313771e5742b6debf617a1 l = last;
final Node1a4db2c2c2313771e5742b6debf617a1 newNode = new Nodea8093152e673feb7aba1828c43532094(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node1a4db2c2c2313771e5742b6debf617a1 succ) { //在节点succ前插入一个e
// assert succ != null;
final Node1a4db2c2c2313771e5742b6debf617a1 pred = succ.prev;
final Node1a4db2c2c2313771e5742b6debf617a1 newNode = new Nodea8093152e673feb7aba1828c43532094(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
//不再链接第一个非空的节点
private E unlinkFirst(Node1a4db2c2c2313771e5742b6debf617a1 f) {
// assert f == first && f != null;
final E element = f.item;
final Node1a4db2c2c2313771e5742b6debf617a1 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;
}
//删掉最后一个节点
private E unlinkLast(Node1a4db2c2c2313771e5742b6debf617a1 l) {
// assert l == last && l != null;
final E element = l.item;
final Node1a4db2c2c2313771e5742b6debf617a1 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;
}
//删掉节点X
E unlink(Node1a4db2c2c2313771e5742b6debf617a1 x) {
// assert x != null;
final E element = x.item;
final Node1a4db2c2c2313771e5742b6debf617a1 next = x.next;
final Node1a4db2c2c2313771e5742b6debf617a1 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 E getFirst() {
final Node1a4db2c2c2313771e5742b6debf617a1 f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//获得最后一个节点
public E getLast() {
final Node1a4db2c2c2313771e5742b6debf617a1 l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
//删除第一个节点
public E removeFirst() {
final Node1a4db2c2c2313771e5742b6debf617a1 f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//删除最后一个节点
public E removeLast() {
final Node1a4db2c2c2313771e5742b6debf617a1 l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//在头节点插入E
public void addFirst(E e) {
linkFirst(e);
}
//在尾节点插入E
public void addLast(E e) {
linkLast(e);
}
//是否包含某个对象
public boolean contains(Object o) {
return indexOf(o) != -1;
}
//链表长度
public int size() {
return size;
}
//在链表中添加节点
public boolean add(E e) {
linkLast(e);
return true;
}
//删掉某个节点
public boolean remove(Object o) {
if (o == null) {
for (Node1a4db2c2c2313771e5742b6debf617a1 x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node1a4db2c2c2313771e5742b6debf617a1 x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//在链表尾追加集合
public boolean addAll(Collection216930c0ab3d232ff5eb2d5ba8cef959 c) {
return addAll(size, c);
}
//在某个节点之后追加集合
public boolean addAll(int index, Collection216930c0ab3d232ff5eb2d5ba8cef959 c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node1a4db2c2c2313771e5742b6debf617a1 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;
Node1a4db2c2c2313771e5742b6debf617a1 newNode = new Nodea8093152e673feb7aba1828c43532094(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 void clear() {
for (Node1a4db2c2c2313771e5742b6debf617a1 x = first; x != null; ) {
Node1a4db2c2c2313771e5742b6debf617a1 next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
//获得第几个节点
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//对某个节点修改
public E set(int index, E element) {
checkElementIndex(index);
Node1a4db2c2c2313771e5742b6debf617a1 x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//在index节点之前插入一个节点element
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//删除掉下标为index的节点
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//测试此index下是否有节点
private boolean isElementIndex(int index) {
return index >= 0 && index e23ea323b642db7571b4c3d5a240abe2= 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));
}
//返回下标节点
Node1a4db2c2c2313771e5742b6debf617a1 node(int index) {
// assert isElementIndex(index);
if (index 606c59f902c07a6006ed249a1edd7d00> 1)) {
Node1a4db2c2c2313771e5742b6debf617a1 x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node1a4db2c2c2313771e5742b6debf617a1 x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//查找是否存在节点并返回下标，不存在返回-1
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node1a4db2c2c2313771e5742b6debf617a1 x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node1a4db2c2c2313771e5742b6debf617a1 x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
//返回最后一个相同的节点的下标
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node1a4db2c2c2313771e5742b6debf617a1 x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node1a4db2c2c2313771e5742b6debf617a1 x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
//返回表头数据并不删除
public E peek() {
final Node1a4db2c2c2313771e5742b6debf617a1 f = first;
return (f == null) ? null : f.item;
}
//返回表头数据
public E element() {
return getFirst();
}
//获得表头数据，并删除表头
public E poll() {
final Node1a4db2c2c2313771e5742b6debf617a1 f = first;
return (f == null) ? null : unlinkFirst(f);
}
//删除表头
public E remove() {
return removeFirst();
}
//在表尾添加数据
public boolean offer(E e) {
return add(e);
}
//在表头添加数据
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//在表尾添加数据
public boolean offerLast(E e) {
addLast(e);
return true;
}
//获得第一个数据，并不删除
public E peekFirst() {
final Node1a4db2c2c2313771e5742b6debf617a1 f = first;
return (f == null) ? null : f.item;
}
//获得最后一个数据，并不删除
public E peekLast() {
final Node1a4db2c2c2313771e5742b6debf617a1 l = last;
return (l == null) ? null : l.item;
}
//获得第一个节点并删除
public E pollFirst() {
final Node1a4db2c2c2313771e5742b6debf617a1 f = first;
return (f == null) ? null : unlinkFirst(f);
}
//获得最后一个节点并删除
public E pollLast() {
final Node1a4db2c2c2313771e5742b6debf617a1 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 (Node1a4db2c2c2313771e5742b6debf617a1 x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node1a4db2c2c2313771e5742b6debf617a1 x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//迭代器
public ListIterator1a4db2c2c2313771e5742b6debf617a1 listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator1a4db2c2c2313771e5742b6debf617a1 {
private Node1a4db2c2c2313771e5742b6debf617a1 lastReturned;
private Node1a4db2c2c2313771e5742b6debf617a1 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 83f0e65bc9aa40da94512f2113df57b1 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node1a4db2c2c2313771e5742b6debf617a1 lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumerdc5aa4f4a38f04210c53c469d00050f9 action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
private static class Node1a4db2c2c2313771e5742b6debf617a1 {
E item;
Node1a4db2c2c2313771e5742b6debf617a1 next;
Node1a4db2c2c2313771e5742b6debf617a1 prev;
Node(Node1a4db2c2c2313771e5742b6debf617a1 prev, E element, Node1a4db2c2c2313771e5742b6debf617a1 next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
/**
* @since 1.6
*/
public Iterator1a4db2c2c2313771e5742b6debf617a1 descendingIterator() {
return new DescendingIterator();
}
/**
* Adapter to provide descending iterators via ListItr.previous
*/
private class DescendingIterator implements Iterator1a4db2c2c2313771e5742b6debf617a1 {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
@SuppressWarnings("unchecked")
private LinkedList1a4db2c2c2313771e5742b6debf617a1 superClone() {
try {
return (LinkedList1a4db2c2c2313771e5742b6debf617a1) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
public Object clone() {
LinkedList1a4db2c2c2313771e5742b6debf617a1 clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node1a4db2c2c2313771e5742b6debf617a1 x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
//生成对象数组
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node1a4db2c2c2313771e5742b6debf617a1 x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
//泛型数组
@SuppressWarnings("unchecked")
public 8742468051c85b06f0a0af9e3e506b5c 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 (Node1a4db2c2c2313771e5742b6debf617a1 x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
private static final long serialVersionUID = 876323262645176354L;
//序列化写对象
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Node1a4db2c2c2313771e5742b6debf617a1 x = first; x != null; x = x.next)
s.writeObject(x.item);
}
//序列化读对象
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
@Override
public Spliterator1a4db2c2c2313771e5742b6debf617a1 spliterator() {
return new LLSpliterator1a4db2c2c2313771e5742b6debf617a1(this, -1, 0);
}
/** A customized variant of Spliterators.IteratorSpliterator */
static final class LLSpliterator1a4db2c2c2313771e5742b6debf617a1 implements Spliterator1a4db2c2c2313771e5742b6debf617a1 {
static final int BATCH_UNIT = 1 << 10; // batch array size increment
static final int MAX_BATCH = 1 << 25; // max batch array size;
final LinkedList1a4db2c2c2313771e5742b6debf617a1 list; // null OK unless traversed
Node1a4db2c2c2313771e5742b6debf617a1 current; // current node; null until initialized
int est; // size estimate; -1 until first needed
int expectedModCount; // initialized when est set
int batch; // batch size for splits
LLSpliterator(LinkedList1a4db2c2c2313771e5742b6debf617a1 list, int est, int expectedModCount) {
this.list = list;
this.est = est;
this.expectedModCount = expectedModCount;
}
final int getEst() {
int s; // force initialization
final LinkedList1a4db2c2c2313771e5742b6debf617a1 lst;
if ((s = est) < 0) {
if ((lst = list) == null)
s = est = 0;
else {
expectedModCount = lst.modCount;
current = lst.first;
s = est = lst.size;
}
}
return s;
}
public long estimateSize() { return (long) getEst(); }
public Spliterator1a4db2c2c2313771e5742b6debf617a1 trySplit() {
Node1a4db2c2c2313771e5742b6debf617a1 p;
int s = getEst();
if (s > 1 && (p = current) != null) {
int n = batch + BATCH_UNIT;
if (n > s)
n = s;
if (n > MAX_BATCH)
n = MAX_BATCH;
Object[] a = new Object[n];
int j = 0;
do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
current = p;
batch = j;
est = s - j;
return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
}
return null;
}
public void forEachRemaining(Consumerdc5aa4f4a38f04210c53c469d00050f9 action) {
Node1a4db2c2c2313771e5742b6debf617a1 p; int n;
if (action == null) throw new NullPointerException();
if ((n = getEst()) > 0 && (p = current) != null) {
current = null;
est = 0;
do {
E e = p.item;
p = p.next;
action.accept(e);
} while (p != null && --n > 0);
}
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
}
public boolean tryAdvance(Consumerdc5aa4f4a38f04210c53c469d00050f9 action) {
Node1a4db2c2c2313771e5742b6debf617a1 p;
if (action == null) throw new NullPointerException();
if (getEst() > 0 && (p = current) != null) {
--est;
E e = p.item;
current = p.next;
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
}
The above is the detailed content of Detailed explanation of LinkedList in Java collections. For more information, please follow other related articles on the PHP Chinese website!
Statement：
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact [email protected]