LinkedList是一个继承AbstractSequentialList的双向链表，它也可以被当做堆栈、队列或者双端队列进行操作。
LinkedList实现了List接口，能对它进行队列操作。
LinkedList实现了Seque接口，能将LinkedList当做双端队列进行使用。
LinkedList实现Cloneable，覆盖了clone函数，可以进行克隆。
LinkedList实现了Serializable，可以被序列化。
LinkedList是非线程安全的。
LinkedList示例程序：
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); }}
输出结果：
Test "offerLast(), pollLast(), peekLast()"llist:[1, 4, 2, 3, 20]llist.pollLast():20llist:[1, 4, 2, 3]llist.peekLast():3get(3):300str:1size:4isEmpty():truestr:4size:0isEmpty():truestr:300size:0isEmpty():truestr:3size:0isEmpty():trueuseLinkedListAsLIFOstack:[4, 3, 2, 1]stack.pop():4stack.peek():3stack:[3, 2, 1]useLinkedListAsFIFOqueue:[10, 20, 30, 40]queue.remove():10queue.element():20queue:[20, 30, 40]
LinkedList源代码：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ transient int size = 0; //其实大小为0 transient Node<E> first; //第一个节点 transient Node<E> last; //最后一个节点 public LinkedList() { //构造一个空LinkedList } public LinkedList(Collection<? extends E> c) { //构造一个带有输入集合的 this(); addAll(c); } 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++; } 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++; } void linkBefore(E e, Node<E> succ) { //在节点succ前插入一个e // 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++; } //不再链接第一个非空的节点 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; } //删掉最后一个节点 private E unlinkLast(Node<E> l) {// assert l == last && l != null; 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; } //删掉节点X 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 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 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); } //在头节点插入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 (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 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 void clear() { for (Node<E> x = first; x != null; ) { Node<E> 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); Node<E> 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)); 本文来源gaodaima#com搞(代@码$网6 } //删除掉下标为index的节点 public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } //测试此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)); } //返回下标节点 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; } } //查找是否存在节点并返回下标，不存在返回-1 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; } //返回最后一个相同的节点的下标 public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } //返回表头数据并不删除 public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } //返回表头数据 public E element() { return getFirst(); } //获得表头数据，并删除表头 public E poll() { final Node<E> 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 Node<E> f = first; return (f == null) ? null : f.item; } //获得最后一个数据，并不删除 public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; } //获得第一个节点并删除 public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } //获得最后一个节点并删除 public E pollLast() { final Node<E> 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<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; } //迭代器 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; } public boolean hasPrevious() { return nextIndex > 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(); Node<E> 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(Consumer<? super E> 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 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; } } /** * @since 1.6 */ public Iterator<E> descendingIterator() { return new DescendingIterator(); } /** * Adapter to provide descending iterators via ListItr.previous */ private class DescendingIterator implements Iterator<E> { 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 LinkedList<E> superClone() { try { return (LinkedList<E>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(e); } } public Object clone() { LinkedList<E> clone = superClone();// Put clone into "virgin" state clone.first = clone.last = null; clone.size = 0; clone.modCount = 0;// Initialize clone with our elements for (Node<E> 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 (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; } //泛型数组 @SuppressWarnings("unchecked") public <T> 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 (Node<E> 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 (Node<E> 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 Spliterator<E> spliterator() { return new LLSpliterator<E>(this, -1, 0); } /** A customized variant of Spliterators.IteratorSpliterator */ static final class LLSpliterator<E> implements Spliterator<E> { static final int BATCH_UNIT = 1 << 10; // batch array size increment static final int MAX_BATCH = 1 << 25; // max batch array size; final LinkedList<E> list; // null OK unless traversed Node<E> 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(LinkedList<E> list, int est, int expectedModCount) { this.list = list; this.est = est; this.expectedModCount = expectedModCount; } final int getEst() { int s; // force initialization final LinkedList<E> 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 Spliterator<E> trySplit() { Node<E> 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(Consumer<? super E> action) { Node<E> 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(Consumer<? super E> action) { Node<E> 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; } }}
以上就是Java集合之LinkedList详解的详细内容，更多请关注搞代码gaodaima其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：Java集合之LinkedList详解
转载请注明原文链接：Java集合之LinkedList详解
