LinkedList

java.lang.Object
- ptolemy.backtrack.util.java.util.AbstractCollection
- - ptolemy.backtrack.util.java.util.AbstractList
  - - ptolemy.backtrack.util.java.util.AbstractSequentialList
    - - ptolemy.backtrack.util.java.util.LinkedList

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, Rollbackable, Collection, List
```
public class LinkedList
extends AbstractSequentialList
implements List, java.lang.Cloneable, java.io.Serializable, Rollbackable
```
Linked list implementation of the List interface. In addition to the methods of the List interface, this class provides access to the first and last list elements in O(1) time for easy stack, queue, or double-ended queue (deque) creation. The list is doubly-linked, with traversal to a given index starting from the end closest to the element.
LinkedList is not synchronized, so if you need multi-threaded access, consider using:
List l = Collections.synchronizedList(new LinkedList(...));
The iterators are fail-fast, meaning that any structural modification, except for remove() called on the iterator itself, cause the iterator to throw a{

Since:

1.2

Author:

Original author unknown, Bryce McKinlay, Eric Blake (ebb9@email.byu.edu)

See Also:

List, ArrayList, Vector, Collections.synchronizedList(List), Serialized Form

Status

missing javadoc, but complete to 1.4

Field Summary
- Fields inherited from class ptolemy.backtrack.util.java.util.AbstractCollection
  $CHECKPOINT, $RECORD$$CHECKPOINT

Constructor Summary

Constructors
Constructor and Description

LinkedList()
Create an empty linked list.

LinkedList(Collection c)
Create a linked list containing the elements, in order, of a given collection.

Constructors
Constructor and Description
`LinkedList()` Create an empty linked list.
`LinkedList(Collection c)` Create a linked list containing the elements, in order, of a given collection.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`$COMMIT(long timestamp)` Commit changes up to the given timestamp, but not including changes made at timestamp and afterward.
`void`	`$RESTORE(long timestamp, boolean trim)` Restore a previous state to all the private fields of this rollbackable object.
`void`	`add(int index, java.lang.Object o)` Inserts an element in the given position in the list.
`boolean`	`add(java.lang.Object o)` Adds an element to the end of the list.
`boolean`	`addAll(Collection c)` Append the elements of the collection in iteration order to the end of this list.
`boolean`	`addAll(int index, Collection c)` Insert the elements of the collection in iteration order at the given index of this list.
`void`	`addFirst(java.lang.Object o)` Insert an element at the first of the list.
`void`	`addLast(java.lang.Object o)` Insert an element at the last of the list.
`void`	`clear()` Remove all elements from this list.
`java.lang.Object`	`clone()` Create a shallow copy of this LinkedList (the elements are not cloned).
`boolean`	`contains(java.lang.Object o)` Returns true if the list contains the given object.
`java.lang.Object`	`get(int index)` Return the element at index.
`java.lang.Object`	`getFirst()` Returns the first element in the list.
`java.lang.Object`	`getLast()` Returns the last element in the list.
`int`	`indexOf(java.lang.Object o)` Returns the first index where the element is located in the list, or -1.
`int`	`lastIndexOf(java.lang.Object o)` Returns the last index where the element is located in the list, or -1.
`java.util.ListIterator`	`listIterator(int index)` Obtain a ListIterator over this list, starting at a given index.
`java.lang.Object`	`remove(int index)` Removes the element at the given position from the list.
`boolean`	`remove(java.lang.Object o)` Removes the entry at the lowest index in the list that matches the given object, comparing by `o == null ? e = null : o.equals(e)`.
`java.lang.Object`	`removeFirst()` Remove and return the first element in the list.
`java.lang.Object`	`removeLast()` Remove and return the last element in the list.
`java.lang.Object`	`set(int index, java.lang.Object o)` Replace the element at the given location in the list.
`int`	`size()` Returns the size of the list.
`java.lang.Object[]`	`toArray()` Returns an array which contains the elements of the list in order.
`java.lang.Object[]`	`toArray(java.lang.Object[] a)` Returns an Array whose component type is the runtime component type of the passed-in Array.

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractSequentialList
iterator

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractList
equals, getModCount, hashCode, listIterator, removeRange, setModCount, subList

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractCollection
$GET$CHECKPOINT, $SET$CHECKPOINT, containsAll, isEmpty, removeAll, retainAll, toString

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface ptolemy.backtrack.util.java.util.List
$GET$CHECKPOINT, $SET$CHECKPOINT, containsAll, equals, hashCode, isEmpty, iterator, listIterator, removeAll, retainAll, subList

- Constructor Detail
  - LinkedList
```
public LinkedList()
```
    Create an empty linked list.
  - LinkedList
```
public LinkedList(Collection c)
```
    Create a linked list containing the elements, in order, of a given collection.
    
    Parameters:
    
    c - the collection to populate this list from
    
    Throws:
    
    java.lang.NullPointerException - if c is null
- Method Detail
  - getFirst
```
public java.lang.Object getFirst()
```
    Returns the first element in the list.
    
    Returns:
    
    the first list element
    
    Throws:
    
    java.util.NoSuchElementException - if the list is empty
  - getLast
```
public java.lang.Object getLast()
```
    Returns the last element in the list.
    
    Returns:
    
    the last list element
    
    Throws:
    
    java.util.NoSuchElementException - if the list is empty
  - removeFirst
```
public java.lang.Object removeFirst()
```
    Remove and return the first element in the list.
    
    Returns:
    
    the former first element in the list
    
    Throws:
    
    java.util.NoSuchElementException - if the list is empty
  - removeLast
```
public java.lang.Object removeLast()
```
    Remove and return the last element in the list.
    
    Returns:
    
    the former last element in the list
    
    Throws:
    
    java.util.NoSuchElementException - if the list is empty
  - addFirst
```
public void addFirst(java.lang.Object o)
```
    Insert an element at the first of the list.
    
    Parameters:
    
    o - the element to insert
  - addLast
```
public void addLast(java.lang.Object o)
```
    Insert an element at the last of the list.
    
    Parameters:
    
    o - the element to insert
  - contains
```
public boolean contains(java.lang.Object o)
```
    Returns true if the list contains the given object. Comparison is done by o == null ? e = null : o.equals(e).
    
    Specified by:
    
    contains in interface Collection
    
    Specified by:
    
    contains in interface List
    
    Overrides:
    
    contains in class AbstractCollection
    
    Parameters:
    
    o - the element to look for
    
    Returns:
    
    true if it is found
  - size
```
public int size()
```
    Returns the size of the list.
    
    Specified by:
    
    size in interface Collection
    
    Specified by:
    
    size in interface List
    
    Specified by:
    
    size in class AbstractCollection
    
    Returns:
    
    the list size
  - add
```
public boolean add(java.lang.Object o)
```
    Adds an element to the end of the list.
    
    Specified by:
    
    add in interface Collection
    
    Specified by:
    
    add in interface List
    
    Overrides:
    
    add in class AbstractList
    
    Parameters:
    
    o - the entry to add
    
    Returns:
    
    true, as it always succeeds
    
    See Also:
    
    AbstractList.add(int, Object)
  - remove
```
public boolean remove(java.lang.Object o)
```
    Removes the entry at the lowest index in the list that matches the given object, comparing by o == null ? e = null : o.equals(e).
    
    Specified by:
    
    remove in interface Collection
    
    Specified by:
    
    remove in interface List
    
    Overrides:
    
    remove in class AbstractCollection
    
    Parameters:
    
    o - the object to remove
    
    Returns:
    
    true if an instance of the object was removed
    
    See Also:
    
    Iterator.remove()
  - addAll
```
public boolean addAll(Collection c)
```
    Append the elements of the collection in iteration order to the end of this list. If this list is modified externally (for example, if this list is the collection), behavior is unspecified.
    
    Specified by:
    
    addAll in interface Collection
    
    Specified by:
    
    addAll in interface List
    
    Overrides:
    
    addAll in class AbstractCollection
    
    Parameters:
    
    c - the collection to append
    
    Returns:
    
    true if the list was modified
    
    Throws:
    
    java.lang.NullPointerException - if c is null
    
    See Also:
    
    AbstractCollection.add(Object)
  - addAll
```
public boolean addAll(int index,
                      Collection c)
```
    Insert the elements of the collection in iteration order at the given index of this list. If this list is modified externally (for example, if this list is the collection), behavior is unspecified.
    
    Specified by:
    
    addAll in interface List
    
    Overrides:
    
    addAll in class AbstractSequentialList
    
    Parameters:
    
    c - the collection to append
    
    index - the location to insert the collection
    
    Returns:
    
    true if the list was modified
    
    Throws:
    
    java.lang.NullPointerException - if c is null
    
    java.lang.IndexOutOfBoundsException - if index < 0 || index > size()
    
    See Also:
    
    AbstractSequentialList.add(int, Object)
  - clear
```
public void clear()
```
    Remove all elements from this list.
    
    Specified by:
    
    clear in interface Collection
    
    Specified by:
    
    clear in interface List
    
    Overrides:
    
    clear in class AbstractList
    
    See Also:
    
    AbstractList.remove(int), AbstractList.removeRange(int, int)
  - get
```
public java.lang.Object get(int index)
```
    Return the element at index.
    
    Specified by:
    
    get in interface List
    
    Overrides:
    
    get in class AbstractSequentialList
    
    Parameters:
    
    index - the place to look
    
    Returns:
    
    the element at index
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if index < 0 || index >= size()
  - set
```
public java.lang.Object set(int index,
                            java.lang.Object o)
```
    Replace the element at the given location in the list.
    
    Specified by:
    
    set in interface List
    
    Overrides:
    
    set in class AbstractSequentialList
    
    Parameters:
    
    index - which index to change
    
    o - the new element
    
    Returns:
    
    the prior element
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if index < 0 || index >= size()
  - add
```
public void add(int index,
                java.lang.Object o)
```
    Inserts an element in the given position in the list.
    
    Specified by:
    
    add in interface List
    
    Overrides:
    
    add in class AbstractSequentialList
    
    Parameters:
    
    index - where to insert the element
    
    o - the element to insert
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if index < 0 || index > size()
    
    See Also:
    
    AbstractList.modCount
  - remove
```
public java.lang.Object remove(int index)
```
    Removes the element at the given position from the list.
    
    Specified by:
    
    remove in interface List
    
    Overrides:
    
    remove in class AbstractSequentialList
    
    Parameters:
    
    index - the location of the element to remove
    
    Returns:
    
    the removed element
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if index < 0 || index > size()
    
    See Also:
    
    AbstractList.modCount
  - indexOf
```
public int indexOf(java.lang.Object o)
```
    Returns the first index where the element is located in the list, or -1.
    
    Specified by:
    
    indexOf in interface List
    
    Overrides:
    
    indexOf in class AbstractList
    
    Parameters:
    
    o - the element to look for
    
    Returns:
    
    its position, or -1 if not found
  - lastIndexOf
```
public int lastIndexOf(java.lang.Object o)
```
    Returns the last index where the element is located in the list, or -1.
    
    Specified by:
    
    lastIndexOf in interface List
    
    Overrides:
    
    lastIndexOf in class AbstractList
    
    Parameters:
    
    o - the element to look for
    
    Returns:
    
    its position, or -1 if not found
  - listIterator
```
public java.util.ListIterator listIterator(int index)
```
    Obtain a ListIterator over this list, starting at a given index. The ListIterator returned by this method supports the add, remove and set methods.
    
    Specified by:
    
    listIterator in interface List
    
    Specified by:
    
    listIterator in class AbstractSequentialList
    
    Parameters:
    
    index - the index of the element to be returned by the first call to next(), or size() to be initially positioned at the end of the list
    
    Returns:
    
    the list iterator
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if index < 0 || index > size()
    
    See Also:
    
    AbstractList.modCount
  - clone
```
public java.lang.Object clone()
```
    Create a shallow copy of this LinkedList (the elements are not cloned).
    
    Overrides:
    
    clone in class java.lang.Object
    
    Returns:
    
    an object of the same class as this object, containing the same elements in the same order
  - toArray
```
public java.lang.Object[] toArray()
```
    Returns an array which contains the elements of the list in order.
    
    Specified by:
    
    toArray in interface Collection
    
    Specified by:
    
    toArray in interface List
    
    Overrides:
    
    toArray in class AbstractCollection
    
    Returns:
    
    an array containing the list elements
  - toArray
```
public java.lang.Object[] toArray(java.lang.Object[] a)
```
    Returns an Array whose component type is the runtime component type of the passed-in Array. The returned Array is populated with all of the elements in this LinkedList. If the passed-in Array is not large enough to store all of the elements in this List, a new Array will be created and returned; if the passed-in Array is larger than the size of this List, then size() index will be set to null.
    
    Specified by:
    
    toArray in interface Collection
    
    Specified by:
    
    toArray in interface List
    
    Overrides:
    
    toArray in class AbstractCollection
    
    Parameters:
    
    a - the passed-in Array
    
    Returns:
    
    an array representation of this list
    
    Throws:
    
    java.lang.ArrayStoreException - if the runtime type of a does not allow an element in this list
    
    java.lang.NullPointerException - if a is null
  - $COMMIT
```
public void $COMMIT(long timestamp)
```
    Description copied from interface: Rollbackable
    
    Commit changes up to the given timestamp, but not including changes made at timestamp and afterward.
    
    Specified by:
    
    $COMMIT in interface Rollbackable
    
    Specified by:
    
    $COMMIT in interface Collection
    
    Specified by:
    
    $COMMIT in interface List
    
    Overrides:
    
    $COMMIT in class AbstractSequentialList
    
    Parameters:
    
    timestamp - The timestamp.
  - $RESTORE
```
public void $RESTORE(long timestamp,
                     boolean trim)
```
    Description copied from interface: Rollbackable
    
    Restore a previous state to all the private fields of this rollbackable object.
    
    Specified by:
    
    $RESTORE in interface Rollbackable
    
    Specified by:
    
    $RESTORE in interface Collection
    
    Specified by:
    
    $RESTORE in interface List
    
    Overrides:
    
    $RESTORE in class AbstractSequentialList
    
    Parameters:
    
    timestamp - The timestamp taken at the time when the previous state was recorded.
    
    trim - Whether to delete the records used for the rollback.
    
    See Also:
    
    Checkpoint.rollback(long, boolean)

Class LinkedList

Field Summary

Fields inherited from class ptolemy.backtrack.util.java.util.AbstractCollection

Constructor Summary

Method Summary

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractSequentialList

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractList

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractCollection

Methods inherited from class java.lang.Object

Methods inherited from interface ptolemy.backtrack.util.java.util.List

Constructor Detail

LinkedList

LinkedList

Method Detail

getFirst

getLast

removeFirst

removeLast

addFirst

addLast

contains

size

add

remove

addAll

addAll

clear

get

set

add

remove

indexOf

lastIndexOf

listIterator

clone

toArray

toArray

$COMMIT

$RESTORE