1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Licensed to the Apache Software Foundation (ASF) under one or more 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * contributor license agreements. See the NOTICE file distributed with 4adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this work for additional information regarding copyright ownership. 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The ASF licenses this file to You under the Apache License, Version 2.0 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (the "License"); you may not use this file except in compliance with 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the License. You may obtain a copy of the License at 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 9adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 10adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 11adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unless required by applicable law or agreed to in writing, software 12adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 13adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * See the License for the specific language governing permissions and 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * limitations under the License. 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util; 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.IOException; 21adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectInputStream; 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectOutputStream; 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.Serializable; 24adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.lang.reflect.Array; 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 27438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * LinkedList is an implementation of {@link List}, backed by a doubly-linked list. 28438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * All optional operations including adding, removing, and replacing elements are supported. 29f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 30438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * <p>All elements are permitted, including null. 31f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 32438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * <p>This class is primarily useful if you need queue-like behavior. It may also be useful 33438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * as a list if you expect your lists to contain zero or one element, but still require the 34438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * ability to scale to slightly larger numbers of elements. In general, though, you should 35438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * probably use {@link ArrayList} if you don't need the queue-like behavior. 36f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 37f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * @since 1.2 38adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 39adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class LinkedList<E> extends AbstractSequentialList<E> implements 40018b67accb28954d35f3cd697be3428e9b45b7d8Jesse Wilson List<E>, Deque<E>, Queue<E>, Cloneable, Serializable { 41f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 42adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = 876323262645176354L; 43adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project transient int size = 0; 45adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 46adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project transient Link<E> voidLink; 47adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 48adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final class Link<ET> { 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ET data; 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<ET> previous, next; 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link(ET o, Link<ET> p, Link<ET> n) { 54adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project data = o; 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous = p; 56adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project next = n; 57adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final class LinkIterator<ET> implements ListIterator<ET> { 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int pos, expectedModCount; 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final LinkedList<ET> list; 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 65adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<ET> link, lastLink; 66adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 67adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project LinkIterator(LinkedList<ET> object, int location) { 68adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project list = object; 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project expectedModCount = list.modCount; 70b46dab348e2007bc08abaf7ecae34d89a2474e50Elliott Hughes if (location >= 0 && location <= list.size) { 71adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // pos ends up as -1 if list is empty, it ranges from -1 to 72adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // list.size - 1 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // if link == voidLink then pos must == -1 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = list.voidLink; 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (location < list.size / 2) { 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (pos = -1; pos + 1 < location; pos++) { 77adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 79adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (pos = list.size; pos >= location; pos--) { 81adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.previous; 82adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 83adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 84adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 85adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IndexOutOfBoundsException(); 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 87adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 88adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void add(ET object) { 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (expectedModCount == list.modCount) { 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<ET> next = link.next; 92adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<ET> newLink = new Link<ET>(object, link, next); 93adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link.next = newLink; 94adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project next.previous = newLink; 95adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = newLink; 96adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastLink = null; 97adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project pos++; 98adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project expectedModCount++; 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project list.size++; 100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project list.modCount++; 101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new ConcurrentModificationException(); 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return link.next != list.voidLink; 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasPrevious() { 111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return link != list.voidLink; 112adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 113adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ET next() { 115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (expectedModCount == list.modCount) { 116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project LinkedList.Link<ET> next = link.next; 117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (next != list.voidLink) { 118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastLink = link = next; 119adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project pos++; 120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return link.data; 121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 124adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new ConcurrentModificationException(); 125adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int nextIndex() { 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return pos + 1; 129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ET previous() { 132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (expectedModCount == list.modCount) { 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (link != list.voidLink) { 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastLink = link; 135adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.previous; 136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project pos--; 137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return lastLink.data; 138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new ConcurrentModificationException(); 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 143adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int previousIndex() { 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return pos; 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (expectedModCount == list.modCount) { 150adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (lastLink != null) { 151adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<ET> next = lastLink.next; 152adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<ET> previous = lastLink.previous; 153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project next.previous = previous; 154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous.next = next; 155adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (lastLink == link) { 156adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project pos--; 157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 158adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = previous; 159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastLink = null; 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project expectedModCount++; 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project list.size--; 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project list.modCount++; 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalStateException(); 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 167adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new ConcurrentModificationException(); 168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 171adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void set(ET object) { 172adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (expectedModCount == list.modCount) { 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (lastLink != null) { 174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastLink.data = object; 175adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 176adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalStateException(); 177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new ConcurrentModificationException(); 180adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 181adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 184d21d78fd49a2d798218e8c8aefbddb26a0e71bbbElliott Hughes /* 185d21d78fd49a2d798218e8c8aefbddb26a0e71bbbElliott Hughes * NOTES:descendingIterator is not fail-fast, according to the documentation 186d21d78fd49a2d798218e8c8aefbddb26a0e71bbbElliott Hughes * and test case. 187d21d78fd49a2d798218e8c8aefbddb26a0e71bbbElliott Hughes */ 188d21d78fd49a2d798218e8c8aefbddb26a0e71bbbElliott Hughes private class ReverseLinkIterator<ET> implements Iterator<ET> { 189d21d78fd49a2d798218e8c8aefbddb26a0e71bbbElliott Hughes private int expectedModCount; 190d21d78fd49a2d798218e8c8aefbddb26a0e71bbbElliott Hughes 191d21d78fd49a2d798218e8c8aefbddb26a0e71bbbElliott Hughes private final LinkedList<ET> list; 192286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 193286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson private Link<ET> link; 194286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 195286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson private boolean canRemove; 196286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 197286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson ReverseLinkIterator(LinkedList<ET> linkedList) { 198286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson list = linkedList; 199286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson expectedModCount = list.modCount; 200286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson link = list.voidLink; 201286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson canRemove = false; 202286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 203286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 204286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public boolean hasNext() { 205286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return link.previous != list.voidLink; 206286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 207286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 208286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public ET next() { 209286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson if (expectedModCount == list.modCount) { 210286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson if (hasNext()) { 211286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson link = link.previous; 212286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson canRemove = true; 213286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return link.data; 214286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 215286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson throw new NoSuchElementException(); 216286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 217286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson throw new ConcurrentModificationException(); 218286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 219286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 220286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 221286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public void remove() { 222286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson if (expectedModCount == list.modCount) { 223286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson if (canRemove) { 224286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson Link<ET> next = link.previous; 225286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson Link<ET> previous = link.next; 226286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson next.next = previous; 227286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson previous.previous = next; 228286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson link = previous; 229286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson list.size--; 230286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson list.modCount++; 231286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson expectedModCount++; 232286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson canRemove = false; 233286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return; 234286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 235286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson throw new IllegalStateException(); 236286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 237286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson throw new ConcurrentModificationException(); 238286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 239286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 240286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 241adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 242adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new empty instance of {@code LinkedList}. 243adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 244adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedList() { 245adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink = new Link<E>(null, null, null); 246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink.previous = voidLink; 247adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink.next = voidLink; 248adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 249adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 250adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 251adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new instance of {@code LinkedList} that holds all of the 252adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * elements contained in the specified {@code collection}. The order of the 253adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * elements in this new {@code LinkedList} will be determined by the 254adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * iteration order of {@code collection}. 255f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 256adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param collection 257adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the collection of elements to add. 258adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 259adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedList(Collection<? extends E> collection) { 260adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(); 261adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project addAll(collection); 262adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 263adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 264adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 265adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Inserts the specified object into this {@code LinkedList} at the 266adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * specified location. The object is inserted before any previous element at 267adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the specified location. If the location is equal to the size of this 268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code LinkedList}, the object is added at the end. 269f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 270adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param location 271adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the index at which to insert. 272adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param object 273adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to add. 274adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 275de2ae30023028e82e4f5ae0c9e88b05649a4c1beElliott Hughes * if {@code location < 0 || location > size()} 276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 278adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void add(int location, E object) { 279b46dab348e2007bc08abaf7ecae34d89a2474e50Elliott Hughes if (location >= 0 && location <= size) { 280adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> link = voidLink; 281adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (location < (size / 2)) { 282adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i <= location; i++) { 283adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 284adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 285adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 286adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = size; i > location; i--) { 287adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.previous; 288adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 289adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> previous = link.previous; 291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> newLink = new Link<E>(object, previous, link); 292adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous.next = newLink; 293adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link.previous = newLink; 294adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project size++; 295adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 296adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 297adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IndexOutOfBoundsException(); 298adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 299adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 300adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 301adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 302adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Adds the specified object at the end of this {@code LinkedList}. 303f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 304adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param object 305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to add. 306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return always true 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean add(E object) { 310286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return addLastImpl(object); 311286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 312286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 313286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson private boolean addLastImpl(E object) { 314adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> oldLast = voidLink.previous; 315adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> newLink = new Link<E>(object, oldLast, voidLink); 316adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink.previous = newLink; 317adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project oldLast.next = newLink; 318adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project size++; 319adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 320adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 321adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 322adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 323adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 324adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Inserts the objects in the specified collection at the specified location 325adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * in this {@code LinkedList}. The objects are added in the order they are 326adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * returned from the collection's iterator. 327f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 328adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param location 329adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the index at which to insert. 330adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param collection 331adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the collection of objects 332adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if this {@code LinkedList} is modified, 333adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code false} otherwise. 334adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws ClassCastException 335adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if the class of an object is inappropriate for this list. 336adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalArgumentException 337adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if an object cannot be added to this list. 338adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 339de2ae30023028e82e4f5ae0c9e88b05649a4c1beElliott Hughes * if {@code location < 0 || location > size()} 340adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 341adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 342adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean addAll(int location, Collection<? extends E> collection) { 343adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (location < 0 || location > size) { 344adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IndexOutOfBoundsException(); 345adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 346adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int adding = collection.size(); 347adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (adding == 0) { 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 349adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 350f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson Collection<? extends E> elements = (collection == this) ? 351f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson new ArrayList<E>(collection) : collection; 352f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 353adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> previous = voidLink; 354adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (location < (size / 2)) { 355adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i < location; i++) { 356adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous = previous.next; 357adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 358adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 359adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = size; i >= location; i--) { 360adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous = previous.previous; 361adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 363adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> next = previous.next; 364f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson for (E e : elements) { 365adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> newLink = new Link<E>(e, previous, null); 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous.next = newLink; 367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous = newLink; 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous.next = next; 370adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project next.previous = previous; 371adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project size += adding; 372adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 373adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 374adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 375adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 376adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 377adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Adds the objects in the specified Collection to this {@code LinkedList}. 378f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 379adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param collection 380adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the collection of objects. 381adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if this {@code LinkedList} is modified, 382adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code false} otherwise. 383adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 384adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 385adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean addAll(Collection<? extends E> collection) { 386adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int adding = collection.size(); 387adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (adding == 0) { 388adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 390f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson Collection<? extends E> elements = (collection == this) ? 391f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson new ArrayList<E>(collection) : collection; 392f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 393adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> previous = voidLink.previous; 394f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson for (E e : elements) { 395adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> newLink = new Link<E>(e, previous, null); 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous.next = newLink; 397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous = newLink; 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous.next = voidLink; 400adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink.previous = previous; 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project size += adding; 402adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 403adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 404adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 405adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 406adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Adds the specified object at the beginning of this {@code LinkedList}. 408f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 409adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param object 410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to add. 411adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 412adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void addFirst(E object) { 413286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson addFirstImpl(object); 414286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 415286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 416286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson private boolean addFirstImpl(E object) { 417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> oldFirst = voidLink.next; 418adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> newLink = new Link<E>(object, voidLink, oldFirst); 419adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink.next = newLink; 420adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project oldFirst.previous = newLink; 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project size++; 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 423286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return true; 424adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 425adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 426adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 427adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Adds the specified object at the end of this {@code LinkedList}. 428f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 429adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param object 430adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to add. 431adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 432adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void addLast(E object) { 433286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson addLastImpl(object); 434adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 435adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 436adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Removes all elements from this {@code LinkedList}, leaving it empty. 438f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see List#isEmpty 440adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see #size 441adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 442adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 443adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 444adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (size > 0) { 445adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project size = 0; 446adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink.next = voidLink; 447adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink.previous = voidLink; 448adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 449adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 450adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 451adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 452adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 453adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a new {@code LinkedList} with the same elements and size as this 454adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code LinkedList}. 455f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 456adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a shallow copy of this {@code LinkedList}. 457adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see java.lang.Cloneable 458adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 459adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @SuppressWarnings("unchecked") 460adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 461adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Object clone() { 462adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 463adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project LinkedList<E> l = (LinkedList<E>) super.clone(); 464adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project l.size = 0; 465adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project l.voidLink = new Link<E>(null, null, null); 466adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project l.voidLink.previous = l.voidLink; 467adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project l.voidLink.next = l.voidLink; 468adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project l.addAll(this); 469adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return l; 470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } catch (CloneNotSupportedException e) { 471fb0ec0e650bf8be35acb0d47da0311a7c446aa33Elliott Hughes throw new AssertionError(e); 472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 473adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 474adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 475adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 476adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Searches this {@code LinkedList} for the specified object. 477f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 478adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param object 479adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to search for. 480adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if {@code object} is an element of this 481adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code LinkedList}, {@code false} otherwise 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 483adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 484adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean contains(Object object) { 485adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> link = voidLink.next; 486adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (object != null) { 487adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (link != voidLink) { 488adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (object.equals(link.data)) { 489adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 490adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 491adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 492adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 493adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 494adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (link != voidLink) { 495adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (link.data == null) { 496adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 497adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 499adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 500adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 501adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 502adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 503adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 504adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 505adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E get(int location) { 506b46dab348e2007bc08abaf7ecae34d89a2474e50Elliott Hughes if (location >= 0 && location < size) { 507adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> link = voidLink; 508adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (location < (size / 2)) { 509adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i <= location; i++) { 510adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 511adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 512adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 513adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = size; i > location; i--) { 514adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.previous; 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 516adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 517adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return link.data; 518adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 519adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IndexOutOfBoundsException(); 520adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 521adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 522adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 523adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the first element in this {@code LinkedList}. 524f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 525adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the first element. 526adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws NoSuchElementException 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if this {@code LinkedList} is empty. 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 529adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E getFirst() { 530286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return getFirstImpl(); 531286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 532286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 533286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson private E getFirstImpl() { 534adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> first = voidLink.next; 535adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (first != voidLink) { 536adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return first.data; 537adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 538adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 539adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 540adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 541adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 542adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the last element in this {@code LinkedList}. 543f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 544adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the last element 545adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws NoSuchElementException 546adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if this {@code LinkedList} is empty 547adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 548adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E getLast() { 549adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> last = voidLink.previous; 550adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (last != voidLink) { 551adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return last.data; 552adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 553adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 554adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 555adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 556adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 557adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int indexOf(Object object) { 558adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int pos = 0; 559adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> link = voidLink.next; 560adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (object != null) { 561adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (link != voidLink) { 562adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (object.equals(link.data)) { 563adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return pos; 564adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 565adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 566adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project pos++; 567adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 568adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 569adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (link != voidLink) { 570adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (link.data == null) { 571adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return pos; 572adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 573adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 574adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project pos++; 575adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 576adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 577adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return -1; 578adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 579adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 580adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 581adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Searches this {@code LinkedList} for the specified object and returns the 582adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * index of the last occurrence. 583f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 584adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param object 585adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to search for 586adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the index of the last occurrence of the object, or -1 if it was 587adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not found. 588adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 589adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 590adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int lastIndexOf(Object object) { 591adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int pos = size; 592adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> link = voidLink.previous; 593adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (object != null) { 594adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (link != voidLink) { 595adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project pos--; 596adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (object.equals(link.data)) { 597adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return pos; 598adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 599adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.previous; 600adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 601adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 602adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (link != voidLink) { 603adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project pos--; 604adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (link.data == null) { 605adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return pos; 606adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 607adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.previous; 608adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 609adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return -1; 611adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 612adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 613adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 614adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a ListIterator on the elements of this {@code LinkedList}. The 615adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * elements are iterated in the same order that they occur in the 616adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code LinkedList}. The iteration starts at the specified location. 617f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 618adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param location 619adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the index at which to start the iteration 620adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a ListIterator on the elements of this {@code LinkedList} 621adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 622de2ae30023028e82e4f5ae0c9e88b05649a4c1beElliott Hughes * if {@code location < 0 || location > size()} 623adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see ListIterator 624adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 625adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 626adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ListIterator<E> listIterator(int location) { 627adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new LinkIterator<E>(this, location); 628adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 629adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 630adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 631adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Removes the object at the specified location from this {@code LinkedList}. 632f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param location 634adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the index of the object to remove 635adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the removed object 636adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 637de2ae30023028e82e4f5ae0c9e88b05649a4c1beElliott Hughes * if {@code location < 0 || location >= size()} 638adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 639adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 640adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E remove(int location) { 641b46dab348e2007bc08abaf7ecae34d89a2474e50Elliott Hughes if (location >= 0 && location < size) { 642adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> link = voidLink; 643adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (location < (size / 2)) { 644adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i <= location; i++) { 645adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 646adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 647adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 648adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = size; i > location; i--) { 649adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.previous; 650adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 651adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> previous = link.previous; 653adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> next = link.next; 654adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous.next = next; 655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project next.previous = previous; 656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project size--; 657adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return link.data; 659adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IndexOutOfBoundsException(); 661adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 662adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean remove(Object object) { 665286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return removeFirstOccurrenceImpl(object); 666adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 667adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 668adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 669adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Removes the first object from this {@code LinkedList}. 670f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 671adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the removed object. 672adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws NoSuchElementException 673adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if this {@code LinkedList} is empty. 674adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 675adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E removeFirst() { 676286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return removeFirstImpl(); 677286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 678286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 679286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson private E removeFirstImpl() { 680adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> first = voidLink.next; 681adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (first != voidLink) { 682adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> next = first.next; 683adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink.next = next; 684adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project next.previous = voidLink; 685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project size--; 686adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 687adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return first.data; 688adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 689adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 690adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 691adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 692adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 693adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Removes the last object from this {@code LinkedList}. 694f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 695adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the removed object. 696adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws NoSuchElementException 697adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if this {@code LinkedList} is empty. 698adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 699adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E removeLast() { 700286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return removeLastImpl(); 701286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 702286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 703286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson private E removeLastImpl() { 704adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> last = voidLink.previous; 705adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (last != voidLink) { 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> previous = last.previous; 707adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink.previous = previous; 708adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project previous.next = voidLink; 709adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project size--; 710adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 711adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return last.data; 712adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 713adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 714adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 715adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 716adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 717286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 718286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 719286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#descendingIterator() 720286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 721286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 722286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public Iterator<E> descendingIterator() { 723286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return new ReverseLinkIterator<E>(this); 724286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 725286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 726286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 727286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 728286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 729286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#offerFirst(java.lang.Object) 730286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 731286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 732286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public boolean offerFirst(E e) { 733286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return addFirstImpl(e); 734286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 735286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 736286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 737286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 738286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 739286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#offerLast(java.lang.Object) 740286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 741286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 742286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public boolean offerLast(E e) { 743286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return addLastImpl(e); 744286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 745286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 746286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 747286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 748286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 749286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#peekFirst() 750286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 751286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 752286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public E peekFirst() { 753286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return peekFirstImpl(); 754286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 755286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 756286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 757286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 758286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 759286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#peekLast() 760286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 761286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 762286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public E peekLast() { 763286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson Link<E> last = voidLink.previous; 764286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return (last == voidLink) ? null : last.data; 765286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 766286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 767286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 768286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 769286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 770286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#pollFirst() 771286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 772286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 773286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public E pollFirst() { 774286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return (size == 0) ? null : removeFirstImpl(); 775286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 776286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 777286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 778286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 779286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 780286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#pollLast() 781286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 782286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 783286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public E pollLast() { 784286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return (size == 0) ? null : removeLastImpl(); 785286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 786286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 787286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 788286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 789286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 790286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#pop() 791286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 792286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 793286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public E pop() { 794286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return removeFirstImpl(); 795286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 796286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 797286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 798286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 799286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 800286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#push(java.lang.Object) 801286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 802286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 803286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public void push(E e) { 804286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson addFirstImpl(e); 805286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 806286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 807286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 808286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 809286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 810286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#removeFirstOccurrence(java.lang.Object) 811286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 812286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 813286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public boolean removeFirstOccurrence(Object o) { 814286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return removeFirstOccurrenceImpl(o); 815286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 816286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 817286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 818286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * {@inheritDoc} 819286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * 820286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @see java.util.Deque#removeLastOccurrence(java.lang.Object) 821286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson * @since 1.6 822286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson */ 823286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson public boolean removeLastOccurrence(Object o) { 824286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson Iterator<E> iter = new ReverseLinkIterator<E>(this); 825286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return removeOneOccurrence(o, iter); 826286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 827286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 828286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson private boolean removeFirstOccurrenceImpl(Object o) { 829286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson Iterator<E> iter = new LinkIterator<E>(this, 0); 830286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return removeOneOccurrence(o, iter); 831286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 832286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 833286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson private boolean removeOneOccurrence(Object o, Iterator<E> iter) { 834286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson while (iter.hasNext()) { 835286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson E element = iter.next(); 836286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson if (o == null ? element == null : o.equals(element)) { 837286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson iter.remove(); 838286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return true; 839286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 840286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 841286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return false; 842286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 843286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 844286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson /** 845adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Replaces the element at the specified location in this {@code LinkedList} 846adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * with the specified object. 847f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 848adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param location 849adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the index at which to put the specified object. 850adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param object 851adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to add. 852adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the previous element at the index. 853adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws ClassCastException 854adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if the class of an object is inappropriate for this list. 855adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalArgumentException 856adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if an object cannot be added to this list. 857adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 858de2ae30023028e82e4f5ae0c9e88b05649a4c1beElliott Hughes * if {@code location < 0 || location >= size()} 859adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 860adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 861adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E set(int location, E object) { 862b46dab348e2007bc08abaf7ecae34d89a2474e50Elliott Hughes if (location >= 0 && location < size) { 863adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> link = voidLink; 864adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (location < (size / 2)) { 865adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i <= location; i++) { 866adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 867adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 868adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 869adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = size; i > location; i--) { 870adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.previous; 871adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 872adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 873adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E result = link.data; 874adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link.data = object; 875adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return result; 876adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 877adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IndexOutOfBoundsException(); 878adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 879adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 880adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 881adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of elements in this {@code LinkedList}. 882f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 883adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the number of elements in this {@code LinkedList}. 884adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 885adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 886adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 887adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return size; 888adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 889f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 890adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean offer(E o) { 891286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return addLastImpl(o); 892adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 893adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 894adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll() { 895adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return size == 0 ? null : removeFirst(); 896adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 897adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 898adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E remove() { 899286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return removeFirstImpl(); 900adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 901adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 902adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E peek() { 903286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return peekFirstImpl(); 904286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson } 905286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson 906286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson private E peekFirstImpl() { 907adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> first = voidLink.next; 908adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return first == voidLink ? null : first.data; 909adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 910adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 911adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E element() { 912286772eb30e454847a7000b001529fca9cb65e6dJesse Wilson return getFirstImpl(); 913adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 914adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 915adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 916adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a new array containing all elements contained in this 917adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code LinkedList}. 918f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 919adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return an array of the elements from this {@code LinkedList}. 920adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 921adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 922adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Object[] toArray() { 923adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int index = 0; 924adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Object[] contents = new Object[size]; 925adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> link = voidLink.next; 926adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (link != voidLink) { 927adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project contents[index++] = link.data; 928adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 929adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 930adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return contents; 931adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 932adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 933adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 934adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an array containing all elements contained in this 935adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code LinkedList}. If the specified array is large enough to hold the 936adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * elements, the specified array is used, otherwise an array of the same 937adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * type is created. If the specified array is used and is larger than this 938adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code LinkedList}, the array element following the collection elements 939adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is set to null. 940f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 941adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param contents 942adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the array. 943adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return an array of the elements from this {@code LinkedList}. 944adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws ArrayStoreException 945adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if the type of an element in this {@code LinkedList} cannot 946adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * be stored in the type of the specified array. 947adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 948adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 949adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @SuppressWarnings("unchecked") 950adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public <T> T[] toArray(T[] contents) { 951adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int index = 0; 952adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (size > contents.length) { 953adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Class<?> ct = contents.getClass().getComponentType(); 954adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project contents = (T[]) Array.newInstance(ct, size); 955adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 956adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> link = voidLink.next; 957adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (link != voidLink) { 958f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson contents[index++] = (T) link.data; 959adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = link.next; 960adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 961adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (index < contents.length) { 962adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project contents[index] = null; 963adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 964adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return contents; 965adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 966adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 967adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void writeObject(ObjectOutputStream stream) throws IOException { 968adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project stream.defaultWriteObject(); 969adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project stream.writeInt(size); 970adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Iterator<E> it = iterator(); 971adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (it.hasNext()) { 972adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project stream.writeObject(it.next()); 973adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 974adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 975adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 976adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @SuppressWarnings("unchecked") 977adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void readObject(ObjectInputStream stream) throws IOException, 978adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ClassNotFoundException { 979adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project stream.defaultReadObject(); 980adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project size = stream.readInt(); 981adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink = new Link<E>(null, null, null); 982adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Link<E> link = voidLink; 983adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = size; --i >= 0;) { 984f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson Link<E> nextLink = new Link<E>((E) stream.readObject(), link, null); 985adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link.next = nextLink; 986adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link = nextLink; 987adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 988adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project link.next = voidLink; 989adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project voidLink.previous = link; 990adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 991adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 992