Класс LinkedList<E>

Реализация двусвязного списка интерфейсов List и Deque. Реализует все необязательные операции со списком и допускает все элементы (включая null).

Все операции выполняются так, как ожидается для двусвязного списка. Операции, индексирующие в список, будут проходить по списку с начала или конца, в зависимости от того, какой из них ближе к указанному индексу.

Обратите внимание, что эта реализация не синхронизирована. Если несколько потоков одновременно обращаются к связанному списку, и по крайней мере один из потоков изменяет структуру списка, то обязательно необходимо выполнить внешнюю синхронизацию. (Структурное изменение — это любая операция, добавляющая или удаляющая один или несколько элементов; простое изменение значения элемента не является структурным изменением.) Обычно это достигается синхронизацией на некотором объекте, естественным образом инкапсулирующем список. Если такого объекта не существует, список следует «оборачивать» с помощью метода Collections.synchronizedList. Это лучше всего делать на этапе создания, чтобы предотвратить случайный несинхронизированный доступ к списку:

List list = Collections.synchronizedList(new LinkedList(...));

Итераторы, возвращаемые методами iterator и listIterator этого класса, являются быстропроверяющими: если список изменяется структурно в любое время после создания итератора, каким-либо способом, кроме как через собственные методы итератора remove или add, итератор выбросит исключение ConcurrentModificationException. Таким образом, при одновременном изменении итератор быстро и корректно завершит работу, а не рискует произвести произвольное, непредсказуемое поведение в неопределенное время в будущем.

Обратите внимание, что поведение быстропроверяющего итератора не гарантируется, поскольку, как правило, невозможно дать какие-либо гарантии при одновременном изменении без синхронизации. Быстропроверяющие итераторы выбрасывают ConcurrentModificationException в лучшем случае. Поэтому неправильно создавать программу, которая полагалась бы на это исключение для корректности: поведение быстропроверяющих итераторов следует использовать только для обнаружения ошибок.

Этот класс является членом Java Collections Framework.

Краткое описание конструкторов

LinkedList

public LinkedList()

Создает пустой список.

LinkedList

public LinkedList(Collection<? extends E> c)

Создает список, содержащий элементы указанной коллекции, в том порядке, в котором они возвращаются итератором коллекции.

Параметры:

c - коллекция, элементы которой должны быть помещены в этот список

Исключения:

NullPointerException - если указанная коллекция равна null

Краткое описание методов

getFirst

public E getFirst()

Возвращает первый элемент в этом списке.

Указано в:

getFirst в интерфейсе Deque<E>

Возвращает:

первый элемент в этом списке

Исключения:

NoSuchElementException - если этот список пуст

getLast

public E getLast()

Возвращает последний элемент в этом списке.

Указано в:

getLast в интерфейсе Deque<E>

Возвращает:

последний элемент в этом списке

Исключения:

NoSuchElementException - если этот список пуст

removeFirst

public E removeFirst()

Удаляет и возвращает первый элемент из этого списка.

Указано в:

removeFirst в интерфейсе Deque<E>

Возвращает:

первый элемент из этого списка

Исключения:

NoSuchElementException - если этот список пуст

removeLast

public E removeLast()

Удаляет и возвращает последний элемент из этого списка.

Указано в:

removeLast в интерфейсе Deque<E>

Возвращает:

последний элемент из этого списка

Исключения:

NoSuchElementException - если этот список пуст

addFirst

public void addFirst(E e)

Вставляет указанный элемент в начало этого списка.

Указано в:

addFirst в интерфейсе Deque<E>

Параметры:

e - элемент для добавления

addLast

public void addLast(E e)

Указано в:

addLast в интерфейсе Deque<E>

Параметры:

e - элемент для добавления

contains

public boolean contains(Object o)

Возвращает true если этот список содержит указанный элемент. Более формально, возвращает true тогда и только тогда, когда этот список содержит хотя бы один элемент e такой, что (o==null ? e==null : o.equals(e)).

Указано в:

contains в интерфейсе Collection<E>

Указано в:

contains в интерфейсе Deque<E>

Указано в:

contains в интерфейсе List<E>

Переопределяет:

contains в классе AbstractCollection<E>

Параметры:

o - элемент, наличие которого в этом списке должно быть проверено

Возвращает:

true если этот список содержит указанный элемент

size

public int size()

Возвращает количество элементов в этом списке.

Указано в:

size в интерфейсе Collection<E>

Указано в:

size в интерфейсе Deque<E>

Указано в:

size в интерфейсе List<E>

Указано в:

size в классе AbstractCollection<E>

Возвращает:

количество элементов в этом списке

add

public boolean add(E e)

Указано в:

add в интерфейсе Collection<E>

Указано в:

add в интерфейсе Deque<E>

Указано в:

add в интерфейсе List<E>

Указано в:

add в интерфейсе Queue<E>

Переопределяет:

add в классе AbstractList<E>

Параметры:

e - элемент, который нужно добавить в этот список

Возвращает:

true (как указано в Collection.add(E))

remove

public boolean remove(Object o)

Удаляет первое вхождение указанного элемента из этого списка, если он присутствует. Если этот список не содержит элемент, он остается неизменным. Более формально, удаляет элемент с наименьшим индексом i такой, что (o==null ? get(i)==null : o.equals(get(i))) (если такой элемент существует). Возвращает true если этот список содержал указанный элемент (или эквивалентно, если этот список изменился в результате вызова).

Указано в:

remove в интерфейсе Collection<E>

Указано в:

remove в интерфейсе Deque<E>

Указано в:

remove в интерфейсе List<E>

Переопределяет:

remove в классе AbstractCollection<E>

Параметры:

o - элемент, который нужно удалить из этого списка, если он присутствует

Возвращает:

true если этот список содержал указанный элемент

addAll

public boolean addAll(Collection<? extends E> c)

Добавляет все элементы в указанную коллекцию в конец этого списка, в том порядке, в котором они возвращаются итератором указанной коллекции. Поведение этой операции не определено, если указанная коллекция изменяется во время выполнения операции. (Обратите внимание, что это произойдет, если указанная коллекция - это список, и она не пуста.)

Указано в:

addAll в интерфейсе Collection<E>

Указано в:

addAll в интерфейсе List<E>

Переопределяет:

addAll в классе AbstractCollection<E>

Параметры:

c - коллекция, содержащая элементы, которые должны быть добавлены в этот список

Возвращает:

true если этот список изменился в результате вызова

Исключения:

NullPointerException - если указанная коллекция равна null

См. также:

AbstractCollection.add(Object)

addAll

public boolean addAll(int index,
                      Collection<? extends E> c)

Вставляет все элементы в указанную коллекцию в этот список, начиная с указанной позиции. Сдвигает элемент, находящийся в данный момент на этой позиции (если таковой есть), и любые последующие элементы вправо (увеличивает их индексы). Новые элементы появятся в списке в том порядке, в котором они возвращаются итератором указанной коллекции.

Указано в:

addAll в интерфейсе List<E>

Переопределяет:

addAll в классе AbstractSequentialList<E>

Параметры:

index - индекс, в котором нужно вставить первый элемент из указанной коллекции

c - коллекция, содержащая элементы, которые нужно добавить в этот список

Возвращает:

true если этот список изменился в результате вызова

Исключения:

IndexOutOfBoundsException - если индекс находится за пределами допустимого диапазона (index < 0 || index > size())

NullPointerException - если указанная коллекция равна null

clear

public void clear()

Удаляет все элементы из этого списка. Список будет пуст после возврата этого вызова.

Указано в:

clear в интерфейсе Collection<E>

Указано в:

clear в интерфейсе List<E>

Переопределяет:

clear в классе AbstractList<E>

get

public E get(int index)

Возвращает элемент в указанной позиции в этом списке.

Указано в:

get в интерфейсе List<E>

Переопределяет:

get в классе AbstractSequentialList<E>

Параметры:

index - индекс элемента, который нужно вернуть

Возвращает:

элемент в указанной позиции в этом списке

Исключения:

IndexOutOfBoundsException - если индекс находится за пределами допустимого диапазона (index < 0 || index >= size())

set

public E set(int index,
             E element)

Заменяет элемент в указанной позиции в этом списке указанным элементом.

Указано в:

set в интерфейсе List<E>

Переопределяет:

set в классе AbstractSequentialList<E>

Параметры:

index - индекс элемента, который нужно заменить

element - элемент, который нужно сохранить в указанной позиции

Возвращает:

элемент, ранее находившийся в указанной позиции

Исключения:

IndexOutOfBoundsException - если индекс находится за пределами допустимого диапазона (index < 0 || index >= size())

add

public void add(int index,
                E element)

Вставляет указанный элемент в указанную позицию в этом списке. Сдвигает элемент, находящийся в данный момент на этой позиции (если таковой есть), и любые последующие элементы вправо (добавляет один к их индексам).

Указано в:

add в интерфейсе List<E>

Переопределяет:

add в классе AbstractSequentialList<E>

Параметры:

index - индекс, в котором указанный элемент должен быть вставлен

element - элемент для вставки

Исключения:

IndexOutOfBoundsException - если индекс находится за пределами допустимого диапазона (index < 0 || index > size())

remove

public E remove(int index)

Удаляет элемент в указанной позиции в этом списке. Сдвигает любые последующие элементы влево (вычитает один из их индексов). Возвращает элемент, который был удален из списка.

Определено в:

remove в интерфейсе List<E>

Переопределено в:

remove в классе AbstractSequentialList<E>

Параметры:

index - индекс элемента, который нужно удалить

Возвращает:

элемент, который ранее находился на указанной позиции

Исключения:

IndexOutOfBoundsException - если индекс вне диапазона (index < 0 || index >= size())

indexOf

public int indexOf(Object o)

Возвращает индекс первого вхождения указанного элемента в этот список, или -1, если этот список не содержит элемент. Более формально, возвращает наименьший индекс i такой, что (o==null ? get(i)==null : o.equals(get(i))), или -1, если такого индекса нет.

Определено в:

indexOf в интерфейсе List<E>

Переопределено в:

indexOf в классе AbstractList<E>

Параметры:

o - элемент для поиска

Возвращает:

индекс первого вхождения указанного элемента в этот список, или -1, если этот список не содержит элемент

lastIndexOf

public int lastIndexOf(Object o)

Возвращает индекс последнего вхождения указанного элемента в этот список, или -1, если этот список не содержит элемент. Более формально, возвращает наибольший индекс i такой, что (o==null ? get(i)==null : o.equals(get(i))), или -1, если такого индекса нет.

Определено в:

lastIndexOf в интерфейсе List<E>

Переопределено в:

lastIndexOf в классе AbstractList<E>

Параметры:

o - элемент для поиска

Возвращает:

индекс последнего вхождения указанного элемента в этот список, или -1, если этот список не содержит элемент

peek

public E peek()

Извлекает, но не удаляет, голову (первый элемент) этого списка.

Определено в:

peek в интерфейсе Deque<E>

Определено в:

peek в интерфейсе Queue<E>

Возвращает:

голову этого списка, или null если этот список пуст

С:

1.5

element

public E element()

Извлекает, но не удаляет, голову (первый элемент) этого списка.

Определено в:

element в интерфейсе Deque<E>

Определено в:

element в интерфейсе Queue<E>

Возвращает:

голову этого списка

Исключения:

NoSuchElementException - если этот список пуст

С:

1.5

poll

public E poll()

Извлекает и удаляет голову (первый элемент) этого списка.

Определено в:

poll в интерфейсе Deque<E>

Определено в:

poll в интерфейсе Queue<E>

Возвращает:

голову этого списка, или null если этот список пуст

С:

1.5

remove

public E remove()

Извлекает и удаляет голову (первый элемент) этого списка.

Определено в:

remove в интерфейсе Deque<E>

Определено в:

remove в интерфейсе Queue<E>

Возвращает:

голову этого списка

Исключения:

NoSuchElementException - если этот список пуст

С:

1.5

offer

public boolean offer(E e)

Добавляет указанный элемент в качестве хвоста (последнего элемента) этого списка.

Определено в:

offer в интерфейсе Deque<E>

Определено в:

offer в интерфейсе Queue<E>

Параметры:

e - добавляемый элемент

Возвращает:

true (как указано в Queue.offer(E))

С:

1.5

offerFirst

public boolean offerFirst(E e)

Вставляет указанный элемент в начало этого списка.

Определено в:

offerFirst в интерфейсе Deque<E>

Параметры:

e - вставляемый элемент

Возвращает:

true (как указано в Deque.offerFirst(E))

С:

1.6

offerLast

public boolean offerLast(E e)

Вставляет указанный элемент в конец этого списка.

Определено в:

offerLast в интерфейсе Deque<E>

Параметры:

e - вставляемый элемент

Возвращает:

true (как указано в Deque.offerLast(E))

С:

1.6

peekFirst

public E peekFirst()

Извлекает, но не удаляет, первый элемент этого списка, или возвращает null если этот список пуст.

Определено в:

peekFirst в интерфейсе Deque<E>

Возвращает:

первый элемент этого списка, или null если этот список пуст

С:

1.6

peekLast

public E peekLast()

Извлекает, но не удаляет, последний элемент этого списка, или возвращает null если этот список пуст.

Определено в:

peekLast в интерфейсе Deque<E>

Возвращает:

последний элемент этого списка, или null если этот список пуст

С:

1.6

pollFirst

public E pollFirst()

Извлекает и удаляет первый элемент этого списка, или возвращает null если этот список пуст.

Определено в:

pollFirst в интерфейсе Deque<E>

Возвращает:

первый элемент этого списка, или null если этот список пуст

С:

1.6

pollLast

public E pollLast()

Извлекает и удаляет последний элемент этого списка, или возвращает null если этот список пуст.

Определено в:

pollLast в интерфейсе Deque<E>

Возвращает:

последний элемент этого списка, или null если этот список пуст

С:

1.6

push

public void push(E e)

Определено в:

push в интерфейсе Deque<E>

Параметры:

e - элемент для добавления

С:

1.6

pop

public E pop()

Определено в:

pop в интерфейсе Deque<E>

Возвращает:

элемент в начале этого списка (который является вершиной стека, представленного этим списком)

Исключения:

NoSuchElementException - если этот список пуст

С:

1.6

removeFirstOccurrence

public boolean removeFirstOccurrence(Object o)

Удаляет первое вхождение указанного элемента в этот список (при обходе списка от головы к хвосту). Если список не содержит элемент, он не изменяется.

Определено в:

removeFirstOccurrence в интерфейсе Deque<E>

Параметры:

o - элемент, который нужно удалить из этого списка, если он присутствует

Возвращает:

true если список содержал указанный элемент

С:

1.6

removeLastOccurrence

public boolean removeLastOccurrence(Object o)

Удаляет последнее вхождение указанного элемента в этом списке (при обходе списка от головы к хвосту). Если список не содержит элемент, он не изменяется.

Определено в:

removeLastOccurrence в интерфейсе Deque<E>

Параметры:

o - элемент, который нужно удалить из этого списка, если он присутствует

Возвращает:

true если список содержал указанный элемент

С:

1.6

listIterator

public ListIterator<E> listIterator(int index)

Определено в:

listIterator в интерфейсе List<E>

Определено в:

listIterator в классе AbstractSequentialList<E>

Параметры:

index - индекс первого элемента, который будет возвращен итератором списка (вызовом next).

Возвращает:

итератор списка элементов в этом списке (в правильной последовательности), начиная с указанной позиции в списке

Исключения:

IndexOutOfBoundsException - если индекс вне диапазона (index < 0 || index > size())

См. также:

List.listIterator(int)

descendingIterator

public Iterator<E> descendingIterator()

Описание скопировано из интерфейса: Deque

Возвращает итератор по элементам в этой очереди в обратном порядке. Элементы будут возвращаться в порядке от последнего (хвоста) к первому (голове).

Определено в:

descendingIterator в интерфейсе Deque<E>

Возвращает:

итератор по элементам в этой очереди в обратном порядке

С:

1.6

clone

public Object clone()

Возвращает поверхностную копию этого LinkedList. (Элементы сами не клонируются.)

Overrides:

clone в классе Object

Returns:

поверхностную копию этого LinkedList экземпляра

См. также:

Cloneable

toArray

public Object[] toArray()

Specified by:

toArray в интерфейсе Collection<E>

Specified by:

toArray в интерфейсе List<E>

Overrides:

toArray в классе AbstractCollection<E>

Returns:

массив, содержащий все элементы этого списка в правильной последовательности

См. также:

Arrays.asList(Object[])

toArray

public <T> T[] toArray(T[] a)

String[] y = x.toArray(new String[0]);

Specified by:

toArray в интерфейсе Collection<E>

Specified by:

toArray в интерфейсе List<E>

Overrides:

toArray в классе AbstractCollection<E>

Type Parameters:

T - тип времени выполнения массива для хранения коллекции

Parameters:

a - массив, в который должны быть помещены элементы списка, если он достаточно велик; в противном случае для этой цели выделяется новый массив того же типа времени выполнения.

Returns:

массив, содержащий элементы списка

Throws:

ArrayStoreException - если тип времени выполнения указанного массива не является супертипом типа времени выполнения каждого элемента в этом списке

NullPointerException - если указанный массив равен null

spliterator

public Spliterator<E> spliterator()

Specified by:

spliterator в интерфейсе Iterable<E>

Specified by:

spliterator в интерфейсе Collection<E>

Specified by:

spliterator в интерфейсе List<E>

Implementation Note:

Spliterator дополнительно сообщает о Spliterator.SUBSIZED и реализует trySplit для ограниченного параллелизма.

Returns:

Spliterator над элементами в этом списке

Since:

1.8