Коллекции. Списки. Интерфейс List

1.

2.

Коллекции
5. Списки
2

3. Списки

3

4. Интерфейс List

public
public interface
interface List<E>
List<E> extends
extends Collection<E>
Collection<E> {{
}}
boolean
boolean add(E
add(E e);
e);
void
add(int
index,
void add(int index, EE element);
element);
boolean
boolean addAll(Collection<?
addAll(Collection<? extends
extends E>
E> c);
c);
void
void addAll(int
addAll(int index,
index, Collection<?
Collection<? extends
extends E>
E> c);
c);
EE set(int
index,
E
element);
set(int index, E element);
EE get(int
get(int index);
index);
boolean
contains(Object
boolean contains(Object o);
o);
boolean
boolean containsAll(Collection<?>
containsAll(Collection<?> c);
c);
int
int indexOf(Object
indexOf(Object o);
o);
int
lastIndexOf(Object
int lastIndexOf(Object o);
o);
int
size();
int size();
boolean
boolean isEmpty();
isEmpty();
boolean
boolean remove(Object
remove(Object o);
o);
EE remove(int
index);
remove(int index);
boolean
boolean removeAll(Collection<?>
removeAll(Collection<?> c);
c);
boolean
boolean retainAll(Collection<?>
retainAll(Collection<?> c);
c);
void
void clear();
clear();
Iterator<E>
Iterator<E> iterator();
iterator();
ListIterator<E>
ListIterator<E> listIterator();
listIterator();
ListIterator<E>
listIterator(int
ListIterator<E> listIterator(int index);
index);
List<E>
List<E> subList(int
subList(int fromIndex,
fromIndex, int
int toIndex);
toIndex);
Object[]
Object[] toArray();
toArray();
<T>
T[]
toArray(T[]
<T> T[] toArray(T[] a);
a);
boolean
equals(Object
boolean equals(Object o);
o);
int
int hashCode();
hashCode();
I
Интерфейс List<E> определяет поведение коллекций, которые служат для хранения упорядоченного набора
объектов с позиционным доступом. При простом добавлении порядок в котором хранятся элементы определяется
порядком их добавления в список. Коллекции реализующие этот интерфейс могут хранить несколько копий одного
и того же объекта. Есть возможность доступа к элементам и добавления элементов по индексу. Для получения
индекса первого и последнего вхождения объекта в список можно использовать методы indexOf и lastIndexOf
соответственно.
4

5. Интерфейс RandomAccess

public
public interface
interface RandomAccess
RandomAccess {{
}}
I
Интерфейс RandomAccess – маркерный интерфейс он говорит о том что список использует хранилище данных с
произвольным доступом. Таким образом операции получения значения по индексу и изменения значения по
индексу требуют постоянное время.
5

6. Реализации интерфейса List<E>

Реализации интерфейса List<E>
Тип коллекции
get(int i)
set(int i, E e)
add
remove
Iterator.remove
ArrayList<E>
O(1)
O(1)
O(1)
O(N)
O(N)
LinkedList<E>
O(N)
O(N)
O(1)
O(N)
O(1)
SingletonList<E>
O(1)
-
-
-
-
EmptyList<E>
-
-
-
-
-
Две часто используемые реализации интерфейса List<E> - ArrayList<E> и
LinkedList<E>. Наиболее часто используется ArrayList<E>, поскольку он
предоставляет позиционный доступ за постоянное время в то время как
LinkedList<E> требует линейного времени. LinkedList<E> выгоднее использовать
когда необходимо часто добавлять значения в начало списка или удалять из начала
списка. Эти операции требуют постоянного времени в LinkedList<E> и линейного
времени в ArrayList<E>.

7.

Класс EmptyList<E>
7

8. Класс EmptyList<E>

Класс EmptyList<E>
public
public class
class Collections
Collections {{
public
new
EmptyList();
EMPTY_LIST == new
new
EmptyList()
public static
static final
final List
List EMPTY_LIST
new EmptyList()
EmptyList();
public
emptyList() {{
public static
static final
final <T>
<T> List<T>
List<T> emptyList()
return
(List<T>)
EMPTY_LIST;
return (List<T>) EMPTY_LIST
EMPTY_LIST;
EMPTY_LIST
}}
private
AbstractList<Object>
private static
static class
class EmptyList
EmptyList extends
extends AbstractList<Object>
AbstractList<Object> implements
implements RandomAccess,
RandomAccess, Serializable
Serializable {{
private
private static
static final
final long
long serialVersionUID
serialVersionUID == 8842843931221139166L;
8842843931221139166L;
return
public
0;}
return 00
public int
int size()
size() {return
{return
0;}
public
public boolean
boolean contains(Object
contains(Object obj)
obj) {return
{return false;}
false;}
public
public Object
Object get(int
get(int index)
index) {{
throw
throw new
new IndexOutOfBoundsException("Index:
IndexOutOfBoundsException("Index: "+index);
"+index);
}}
}}
}}
//
// Preserves
Preserves singleton
singleton property
property
private
private Object
Object readResolve()
readResolve() {{
return
EMPTY_LIST;
return EMPTY_LIST;
}}
C
Класс EmptyList<E> реализует интерфейс List для пустого списка. Для получение ссылки на
объект класса EmptyList используется метод emptyList из класса Collections.
8

9. Использование EmptyList<E>

Использование EmptyList<E>
public
public class
class EmptyListDemo
EmptyListDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
List<String>
List<String> staff
staff == Collections.emptyList();
Collections.emptyList();
System.out.println("\nList
System.out.println("\nList contents:
contents: ");
");
for
for (String
(String value
value :: staff)
staff) {{
System.out.println("name
System.out.println("name == "" ++ value);
value);
}}
}}
}}
System.out.println("\nList
System.out.println("\nList size:
size: "" ++ staff.size());
staff.size());
List
List contents:
contents:
List
List size:
size: 00
9

10. Сравнение производительности для пустого List<E>

Сравнение производительности для пустого List<E>
public
public class
class EmptyListsCompareDemo
EmptyListsCompareDemo {{
private
private static
static final
final int
int ITERATIONS
ITERATIONS == 10000000;
10000000;
public
public static
static void
void main(String[]
main(String[] args)
args) {{
List<String>
List<String> theList;
theList;
long
long now
now == System.currentTimeMillis();
System.currentTimeMillis();
for
for (int
(int ii == 0;
0; ii << ITERATIONS;
ITERATIONS; i++){
i++){
theList
theList == new
new ArrayList<String>();
ArrayList<String>();
}}
System.out.println("Time
System.out.println("Time using
using ArrayList():
ArrayList(): "" ++ (System.currentTimeMillis()
(System.currentTimeMillis() -- now)
now) ++ "" ms");
ms");
now
now == System.currentTimeMillis();
System.currentTimeMillis();
for
for (int
(int ii
theList
theList
}}
==
==
0;
0; ii << ITERATIONS;
ITERATIONS; i++){
i++){
new
ArrayList<String>(0);
new ArrayList<String>(0);
System.out.println("Time
System.out.println("Time using
using ArrayList(0):
ArrayList(0): "" ++ (System.currentTimeMillis()
(System.currentTimeMillis() -- now)
now) ++ "" ms");
ms");
now
now == System.currentTimeMillis();
System.currentTimeMillis();
for
for (int
(int ii == 0;
0; ii << ITERATIONS;
ITERATIONS; i++){
i++){
theList
theList == new
new LinkedList<String>();
LinkedList<String>();
}}
System.out.println("Time
System.out.println("Time using
using LinkedList():
LinkedList(): "" ++ (System.currentTimeMillis()
(System.currentTimeMillis() -- now)
now) ++ "" ms");
ms");
now
=
System.currentTimeMillis();
now = System.currentTimeMillis();
ms");
ms");
}}
}}
for
for (int
(int ii == 0;
0; ii << ITERATIONS;
ITERATIONS; i++){
i++){
theList
theList == Collections.emptyList();
Collections.emptyList();
}}
System.out.println("Time
System.out.println("Time using
using Collections.emptyList():
Collections.emptyList(): "" ++ (System.currentTimeMillis()
(System.currentTimeMillis() -- now)
now) ++ ""
10

11. Сравнение производительности для пустого List<E>

Сравнение производительности для пустого List<E>
Time
Time
Time
Time
Time
Time
Time
Time
using
using
using
using
using
using
using
using
ArrayList():
ArrayList(): 312
312 ms
ms
ArrayList(0):
ArrayList(0): 188
188 ms
ms
LinkedList():
1187
LinkedList(): 1187 ms
ms
Collections.emptyList():
Collections.emptyList(): 31
31 ms
ms
11

12.

Класс SingletonList<E>
12

13. Класс SingletonList<E>

Класс SingletonList<E>
public
public class
class Collections
Collections {{
public
public static
static <T>
<T> List<T>
List<T> singletonList(T
singletonList(T o)
o) {{
return
new
SingletonList<T>(o);
SingletonList<T>(o)
return new SingletonList<T>(o)
SingletonList<T>(o);
}}
private
AbstractList<E>
AbstractList<E>)
private static
static class
class SingletonList<E>
SingletonList<E> extends
extendsAbstractList<E>)
AbstractList<E> implements
implements RandomAccess,
RandomAccess, Serializable
Serializable {{
static
static final
final long
long serialVersionUID
serialVersionUID == 3093736618740652951L;
3093736618740652951L;
private
element;
private
final
element
private final
final EEE element
element;
SingletonList(E
SingletonList(E obj)
obj) {element
{element == obj;}
obj;}
public
return
return
public int
int size()
size() {{return
return111;}
1;}
public
public boolean
boolean contains(Object
contains(Object obj)
obj) {return
{return eq(obj,
eq(obj, element);}
element);}
}}
}}
...
...
public
public EE get(int
get(int index)
index) {{
if
if (index
(index !=
!= 0)
0)
throw
new
throw new IndexOutOfBoundsException("Index:
IndexOutOfBoundsException("Index: "+index+",
"+index+", Size:
Size: 1");
1");
return
element;
return element;
}}
C
Класс SingletonList<E> реализует интерфейс List для списка из одного значения. Для
получение ссылки на объект класса SingletonList используется метод singletonList из класса
Collections.
13

14. Использование SingletonList<E>

Использование SingletonList<E>
public
public class
class SingletonListDemo
SingletonListDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
List<String>
List<String> staff
staff == Collections.singletonList("Harry
Collections.singletonList("Harry Hacker");
Hacker");
System.out.println("\nList
System.out.println("\nList contents:
contents: ");
");
for
for (String
(String value
value :: staff)
staff) {{
System.out.println("name
System.out.println("name == "" ++ value);
value);
}}
}}
}}
List
List
name
name
System.out.println("\nList
System.out.println("\nList size:
size: "" ++ staff.size());
staff.size());
contents:
contents:
== Harry
Harry Hacker
Hacker
List
List size:
size: 11
14

15. Сравнение производительности для List<E> с одним элементом

Сравнение производительности для List<E> с одним
элементом
public
public class
class OneValueListsCompareDemo
OneValueListsCompareDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
List<String>
List<String> theList;
theList;
long
long now
now == System.currentTimeMillis();
System.currentTimeMillis();
for
for (int
(int ii == 0;
0; ii << 10000000;
10000000; i++){
i++){
theList
=
new
ArrayList<String>();
theList = new ArrayList<String>();
theList.add("Harry
theList.add("Harry Hacker");
Hacker");
}}
System.out.println("Time
System.out.println("Time using
using ArrayList():
ArrayList(): "" ++ (System.currentTimeMillis()
(System.currentTimeMillis() -- now)
now) ++ "" ms");
ms");
now
=
System.currentTimeMillis();
now = System.currentTimeMillis();
for
for (int
(int ii == 0;
0; ii << 10000000;
10000000; i++){
i++){
theList
theList == new
new ArrayList<String>(1);
ArrayList<String>(1);
theList.add("Harry
theList.add("Harry Hacker");
Hacker");
}}
System.out.println("Time
System.out.println("Time using
using ArrayList(1):
ArrayList(1): "" ++ (System.currentTimeMillis()
(System.currentTimeMillis() -- now)
now) ++ "" ms");
ms");
now
now == System.currentTimeMillis();
System.currentTimeMillis();
for
for (int
(int ii == 0;
0; ii << 10000000;
10000000; i++){
i++){
theList
theList == new
new LinkedList<String>();
LinkedList<String>();
theList.add("Harry
theList.add("Harry Hacker");
Hacker");
}}
System.out.println("Time
System.out.println("Time using
using LinkedList():
LinkedList(): "" ++ (System.currentTimeMillis()
(System.currentTimeMillis() -- now)
now) ++ "" ms");
ms");
now
now == System.currentTimeMillis();
System.currentTimeMillis();
}}
}}
for
for (int
(int ii == 0;
0; ii << 10000000;
10000000; i++){
i++){
theList
=
Collections.singletonList("Harry
theList = Collections.singletonList("Harry Hacker");
Hacker");
}}
System.out.println("Time
System.out.println("Time using
using SingletonList():
SingletonList(): "" ++ (System.currentTimeMillis()
(System.currentTimeMillis() -- now)
now) ++ "" ms");
ms");
15

16. Сравнение производительности для List<E> с одним элементом

Сравнение производительности для List<E> с одним
элементом
Time
Time
Time
Time
Time
Time
Time
Time
using
using
using
using
using
using
using
using
ArrayList():
ArrayList(): 359
359 ms
ms
ArrayList(1):
ArrayList(1): 266
266 ms
ms
LinkedList():
1406
LinkedList(): 1406 ms
ms
SingletonList():
78
SingletonList(): 78 ms
ms
16

17.

Класс ArrayList<E>
17

18. Класс ArrayList<E>

Класс ArrayList<E>
public
public class
class ArrayList<E>
ArrayList<E> extends
extends AbstractList<E>
AbstractList<E> implements
implements List<E>,
List<E>, RandomAccess,
RandomAccess, Cloneable,
Cloneable, Serializable
Serializable {{
private
Object[]
elementData;
elementData
private transient
transient Object[]
Object[] elementData
elementData;
private
int
size;
int
size
private int size
size;
public
public
public
public
public
public
ArrayList()
ArrayList()
ArrayList(int
ArrayList(int initialCapacity)
initialCapacity)
ArrayList(Collection<?
ArrayList(Collection<? extends
extends E>
E> c)
c)
public
public void
void trimToSize()
trimToSize()
public
public void
void ensureCapacity(int
ensureCapacity(int minCapacity)
minCapacity)
public
public
public
public
public
public
public
public
public
public
boolean
boolean add(E
add(E e)
e)
void
void add(int
add(int index,
index, EE element)
element)
boolean
boolean addAll(Collection<?
addAll(Collection<? extends
extends E>
E> c)
c)
EE set(int
index,
E
element)
set(int index, E element)
EE get(int
get(int index)
index)
public
public
public
public
public
public
boolean
boolean contains(Object
contains(Object o)
o)
int
indexOf(Object
o)
int indexOf(Object o)
int
int lastIndexOf(Object
lastIndexOf(Object o)
o)
public
public
public
public
public
public
EE remove(int
remove(int index)
index)
boolean
boolean remove(Object
remove(Object o)
o)
void
clear()
void clear()
public
public int
int size()
size()
public
public boolean
boolean isEmpty()
isEmpty()
}}
public
public
public
public
public
public
Object[]
Object[] toArray()
toArray()
E[]
E[] toArray(E[])
toArray(E[])
Object
Object clone()
clone()
C
Класс ArrayList<E> реализует интерфейс List<E> с помощью массива. Ссылка на массив хранится
в поле elementData. Размер массива называется ёмкостью ArrayList<E>. Количество используемых
элементов массива хранится в поле size. Если размер массива становится недостаточным
выделяется новый массив. Ёмкость больше или равна числу хранимых значений.
18

19.

Ёмкость и размер
19

20. Изменение ёмкости

public
public class
class ArrayListCapacityDemo
ArrayListCapacityDemo {{
private
private static
static final
final int
int ITERATIONS
ITERATIONS == 25000000;
25000000;
public
public static
static void
void main(String[]
main(String[] args)
args) {{
ArrayList<String>
ArrayList<String> arrayList
arrayList == new
new ArrayList<String>();
ArrayList<String>();
long
long startTime
startTime == System.currentTimeMillis();
System.currentTimeMillis();
arrayList.ensureCapacity(ITERATIONS);
arrayList.ensureCapacity(ITERATIONS);
for
for (int
(int ii == 0;
0; ii << ITERATIONS;
ITERATIONS; i++)
i++)
arrayList.add("");
arrayList.add("");
long
long endTime
endTime == System.currentTimeMillis();
System.currentTimeMillis();
System.out.println("ArrayList
System.out.println("ArrayList with
with ensureCapacity()
ensureCapacity() time:
time: "" ++ (endTime
(endTime -- startTime));
startTime));
arrayList
arrayList == new
new ArrayList<String>();
ArrayList<String>();
startTime
startTime == System.currentTimeMillis();
System.currentTimeMillis();
for
for (int
(int ii == 0;
0; ii << ITERATIONS;
ITERATIONS; i++)
i++)
arrayList.add("");
arrayList.add("");
}}
}}
endTime
endTime == System.currentTimeMillis();
System.currentTimeMillis();
System.out.println("ArrayList
System.out.println("ArrayList without
without ensureCapacity()
ensureCapacity() time:
time: "" ++ (endTime
(endTime -- startTime));
startTime));
ArrayList
ArrayList
ArrayList
ArrayList
with
with ensureCapacity()
ensureCapacity() time:
time: 312
312
without
ensureCapacity()
time:
without ensureCapacity() time: 641
641
20

21.

Добавление элементов
21

22. Добавление элементов

public
public class
class SimpleListAddDemo
SimpleListAddDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
List<String>
List<String> fruits
fruits == new
new ArrayList<String>();
ArrayList<String>();
fruits.add("apple");
fruits.add("apple");
fruits.add("orange");
fruits.add("orange");
fruits.add("kiwi");
fruits.add("kiwi");
fruits.add("apple");
fruits.add("apple");
fruits.add("apple");
fruits.add("apple");
fruits.add("mango");
fruits.add("mango");
fruits.add("pear");
fruits.add("pear");
fruits.add("pear");
fruits.add("pear");
fruits.add("apple");
fruits.add("apple");
fruits.add("orange");
fruits.add("orange");
}}
}}
System.out.println("List
System.out.println("List contents:
contents: "" ++ fruits);
fruits);
List
List contents:
contents: [apple,
[apple, orange,
orange, kiwi,
kiwi, apple,
apple, apple,
apple, mango,
mango, pear,
pear, pear,
pear, apple,
apple, orange]
orange]
22

23. Добавление элементов по индексу

public
public class
class ListInsertDemo
ListInsertDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
List<String>
List<String> fruits
fruits == new
new ArrayList<String>();
ArrayList<String>();
fruits.add(0,"apple");
fruits.add(0,"apple");
fruits.add(0,"banana");
fruits.add(0,"banana");
fruits.add(0,"kiwi");
fruits.add(0,"kiwi");
fruits.add(0,"mango");
fruits.add(0,"mango");
fruits.add(0,"orange");
fruits.add(0,"orange");
fruits.add(0,"peach");
fruits.add(0,"peach");
fruits.add(0,"pear");
fruits.add(0,"pear");
System.out.println("List
System.out.println("List contents:
contents: "" ++ fruits);
fruits);
fruits.clear();
fruits.clear();
fruits.add(0,"apple");
fruits.add(0,"apple");
fruits.add(1,"banana");
fruits.add(1,"banana");
fruits.add(2,"kiwi");
fruits.add(2,"kiwi");
fruits.add(3,"mango");
fruits.add(3,"mango");
fruits.add(4,"orange");
fruits.add(4,"orange");
fruits.add(5,"peach");
fruits.add(5,"peach");
fruits.add(6,"pear");
fruits.add(6,"pear");
}}
}}
System.out.println("List
System.out.println("List contents:
contents: "" ++ fruits);
fruits);
List
List contents:
contents: [pear,
[pear, peach,
peach, orange,
orange, mango,
mango, kiwi,
kiwi, banana,
banana, apple]
apple]
List
List contents:
contents: [apple,
[apple, banana,
banana, kiwi,
kiwi, mango,
mango, orange,
orange, peach,
peach, pear]
pear]
23

24.

Удаление элементов
24

25. Удаление элементов

public
public class
class ListRemoveDemo
ListRemoveDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
String[]
String[] toAdd
toAdd == {{ "apple",
"apple", "cucumber",
"cucumber", "carrot",
"carrot", "kiwi",
"kiwi", "potato",
"potato",
"tomato",
"cucumber",
"orange",
"carrot",
"tomato"
};
"tomato", "cucumber", "orange", "carrot", "tomato" };
String[]
String[] toRemove
toRemove == {{ "carrot",
"carrot", "tomato",
"tomato", "onion",
"onion", "cucumber",
"cucumber", "potato"
"potato" };
};
List<String>
List<String> produce
produce == new
new ArrayList<String>();
ArrayList<String>();
Collections.addAll(produce,
Collections.addAll(produce, toAdd);
toAdd);
//
List<String>
produce
=
new
// List<String> produce = new ArrayList<String>(Arrays.asList(toAdd));
ArrayList<String>(Arrays.asList(toAdd));
System.out.println("List
System.out.println("List size:
size: "" ++ produce.size());
produce.size());
System.out.println("List
System.out.println("List contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
for
for (String
(String ff :: toRemove)
toRemove) {{
}}
}}
}}
if
if (produce.remove(f))
(produce.remove(f))
System.out.println(f
System.out.println(f
else
else
System.out.println(f
System.out.println(f
++ "" was
was removed.
removed. List
List contents:
contents: "" ++ produce);
produce);
++ "" was
was not
not removed");
removed");
System.out.println("\nFinal
System.out.println("\nFinal list
list size:
size: "" ++ produce.size());
produce.size());
System.out.println("Final
System.out.println("Final list
list contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
25

26. Удаление элементов

List
List
List
List
size:
size: 10
10
contents:
contents: [apple,
[apple, cucumber,
cucumber, carrot,
carrot, kiwi,
kiwi, potato,
potato, tomato,
tomato, cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
carrot
carrot was
was removed.
removed. List
List contents:
contents: [apple,
[apple, cucumber,
cucumber, kiwi,
kiwi,
tomato
tomato was
was removed.
removed. List
List contents:
contents: [apple,
[apple, cucumber,
cucumber, kiwi,
kiwi,
onion
onion was
was not
not removed
removed
cucumber
was
removed.
cucumber was removed. List
List contents:
contents: [apple,
[apple, kiwi,
kiwi, potato,
potato,
potato
was
removed.
List
contents:
[apple,
kiwi,
cucumber,
potato was removed. List contents: [apple, kiwi, cucumber,
potato,
potato, tomato,
tomato, cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
potato,
potato, cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
orange,
carrot,
tomato]
orange, carrot, tomato]
Final
Final list
list size:
size: 66
Final
Final list
list contents:
contents: [apple,
[apple, kiwi,
kiwi, cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
26

27. Удаление элементов по индексу

public
public class
class ListRemoveAtIndexDemo
ListRemoveAtIndexDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
String[]
String[] toAdd
toAdd == {{ "apple",
"apple",
"tomato",
"cucumber",
"tomato", "cucumber",
"cucumber",
"cucumber", "carrot",
"carrot", "kiwi",
"kiwi", "potato",
"potato",
"orange",
"carrot",
"tomato"
};
"orange", "carrot", "tomato" };
List<String>
List<String> produce
produce == new
new ArrayList<String>();
ArrayList<String>();
Collections.addAll(produce,
Collections.addAll(produce, toAdd);
toAdd);
//
List<String>
produce
=
new
// List<String> produce = new ArrayList<String>(Arrays.asList(toAdd));
ArrayList<String>(Arrays.asList(toAdd));
System.out.println("List
System.out.println("List size:
size: "" ++ produce.size());
produce.size());
System.out.println("List
System.out.println("List contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
for
for (int
(int ii == 0;
0; ii << toAdd.length;
toAdd.length; i++)
i++) {{
}}
}}
}}
String
String removed
removed == produce.remove(0);
produce.remove(0);
System.out.println(removed
System.out.println(removed ++ "" was
was removed.
removed. List
List contents:
contents: ""
++ produce);
produce);
System.out.println("\nFinal
System.out.println("\nFinal list
list size:
size: "" ++ produce.size());
produce.size());
System.out.println("Final
System.out.println("Final list
list contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
27

28. Удаление элементов по индексу

List
List
List
List
size:
size: 10
10
contents:
contents: [apple,
[apple, cucumber,
cucumber, carrot,
carrot, kiwi,
kiwi, potato,
potato, tomato,
tomato, cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
apple
apple was
was removed.
removed. List
List contents:
contents: [cucumber,
[cucumber, carrot,
carrot, kiwi,
kiwi, potato,
potato, tomato,
tomato, cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
cucumber
cucumber was
was removed.
removed. List
List contents:
contents: [carrot,
[carrot, kiwi,
kiwi, potato,
potato, tomato,
tomato, cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
carrot
carrot was
was removed.
removed. List
List contents:
contents: [kiwi,
[kiwi, potato,
potato, tomato,
tomato, cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
kiwi
was
removed.
List
contents:
[potato,
tomato,
cucumber,
orange,
carrot,
tomato]
kiwi was removed. List contents: [potato, tomato, cucumber, orange, carrot, tomato]
potato
potato was
was removed.
removed. List
List contents:
contents: [tomato,
[tomato, cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
tomato
tomato was
was removed.
removed. List
List contents:
contents: [cucumber,
[cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
cucumber
cucumber was
was removed.
removed. List
List contents:
contents: [orange,
[orange, carrot,
carrot, tomato]
tomato]
orange
orange was
was removed.
removed. List
List contents:
contents: [carrot,
[carrot, tomato]
tomato]
carrot
was
removed.
List
contents:
[tomato]
carrot was removed. List contents: [tomato]
tomato
tomato was
was removed.
removed. List
List contents:
contents: []
[]
Final
Final list
list size:
size: 00
Final
Final list
list contents:
contents: []
[]
28

29.

Позиционный доступ
29

30. Позиционный доступ

public
public class
class ListGetSetDemo
ListGetSetDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
String[]
String[] toAdd
toAdd == {{ "apple",
"apple", "carrot",
"carrot", "kiwi",
"kiwi", "potato",
"potato", "tomato",
"tomato", "pear",
"pear",
"cucumber",
"orange"
};
"cucumber", "orange" };
List<String>
List<String> produce
produce == new
new ArrayList<String>();
ArrayList<String>();
Collections.addAll(produce,
Collections.addAll(produce, toAdd);
toAdd);
//
List<String>
produce
=
new
// List<String> produce = new ArrayList<String>(Arrays.asList(toAdd));
ArrayList<String>(Arrays.asList(toAdd));
System.out.println("Set
System.out.println("Set size:
size: "" ++ produce.size());
produce.size());
System.out.println("Set
System.out.println("Set contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
for
for (int
(int ii == 0;
0; ii << produce.size();
produce.size(); i++)
i++) {{
String
String to
to == produce.get(i).toUpperCase();
produce.get(i).toUpperCase();
String
String prev
prev == produce.set(i,
produce.set(i, to);
to);
System.out.println("Changing
System.out.println("Changing "" ++ prev
prev ++ "" to
to "" ++ to);
to);
}}
}}
}}
System.out.println("\nSet
System.out.println("\nSet size:
size: "" ++ produce.size());
produce.size());
System.out.println("Set
System.out.println("Set contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
30

31. Позиционный доступ

Set
Set size:
size: 88
Set
Set contents:
contents: [apple,
[apple, carrot,
carrot, kiwi,
kiwi, potato,
potato, tomato,
tomato, pear,
pear, cucumber,
cucumber, orange]
orange]
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
apple
apple to
to APPLE
APPLE
carrot
to
carrot to CARROT
CARROT
kiwi
kiwi to
to KIWI
KIWI
potato
potato to
to POTATO
POTATO
tomato
tomato to
to TOMATO
TOMATO
pear
pear to
to PEAR
PEAR
cucumber
cucumber to
to CUCUMBER
CUCUMBER
orange
orange to
to ORANGE
ORANGE
Set
Set size:
size: 88
Set
Set contents:
contents: [APPLE,
[APPLE, CARROT,
CARROT, KIWI,
KIWI, POTATO,
POTATO, TOMATO,
TOMATO, PEAR,
PEAR, CUCUMBER,
CUCUMBER, ORANGE]
ORANGE]
31

32.

Поиск
32

33. Поиск первого и последнего вхождения

public
public class
class ListIndexOfDemo
ListIndexOfDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
String[]
String[] toAdd
toAdd == {{ "apple",
"apple", "cucumber",
"cucumber", "carrot",
"carrot", "kiwi",
"kiwi", "potato",
"potato", "tomato",
"tomato",
"pear",
"cucumber",
"orange",
"carrot"
,"tomato"
};
"pear", "cucumber", "orange", "carrot" ,"tomato" };
String[]
String[] toFind
toFind == {{ "carrot",
"carrot", "tomato",
"tomato", "onion",
"onion", "cucumber",
"cucumber", "potato"
"potato" };
};
List<String>
List<String> produce
produce == new
new ArrayList<String>();
ArrayList<String>();
Collections.addAll(produce,
Collections.addAll(produce, toAdd);
toAdd);
//List<String>
produce
=
new
//List<String> produce = new ArrayList<String>(Arrays.asList(toAdd));
ArrayList<String>(Arrays.asList(toAdd));
System.out.println("Set
System.out.println("Set size:
size: "" ++ produce.size());
produce.size());
System.out.println("Set
System.out.println("Set contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
for
for (String
(String ff :: toFind)
toFind) {{
int
int first
first == produce.indexOf(f);
produce.indexOf(f);
int
int last
last == produce.lastIndexOf(f);
produce.lastIndexOf(f);
}}
}}
}}
if
if (first
(first !=
!= -1)
-1)
System.out.println(f
System.out.println(f ++ "" is
is on
on the
the list,
list, first
first index:
index: "" ++ first
first ++ ",
", last
last index:
index: "" ++ last);
last);
else
else
System.out.println(f
System.out.println(f ++ "" is
is not
not on
on the
the list");
list");
33

34. Поиск первого и последнего вхождения

Set
Set size:
size: 11
11
Set
Set contents:
contents: [apple,
[apple, cucumber,
cucumber, carrot,
carrot, kiwi,
kiwi, potato,
potato, tomato,
tomato, pear,
pear, cucumber,
cucumber, orange,
orange, carrot,
carrot, tomato]
tomato]
carrot
carrot is
is on
on the
the list,
list, first
first index:
index: 2,
2, last
last index:
index: 99
tomato
tomato is
is on
on the
the list,
list, first
first index:
index: 5,
5, last
last index:
index: 10
10
onion
onion is
is not
not on
on the
the list
list
cucumber
cucumber is
is on
on the
the list,
list, first
first index:
index: 1,
1, last
last index:
index: 77
potato
potato is
is on
on the
the list,
list, first
first index:
index: 4,
4, last
last index:
index: 44
34

35. Поиск

public
public class
class ListContainsDemo
ListContainsDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
String[]
String[] toAdd
toAdd == {{ "apple",
"apple", "carrot",
"carrot", "kiwi",
"kiwi", "potato",
"potato", "tomato",
"tomato",
"pear",
"cucumber",
"orange"
};
"pear", "cucumber", "orange" };
String[]
String[] toFind
toFind == {{ "carrot",
"carrot", "tomato",
"tomato", "onion",
"onion", "cucumber",
"cucumber", "potato"
"potato" };
};
List<String>
List<String> produce
produce == new
new ArrayList<String>();
ArrayList<String>();
Collections.addAll(produce,
Collections.addAll(produce, toAdd);
toAdd);
//List<String>
produce
=
new
//List<String> produce = new ArrayList<String>(Arrays.asList(toAdd));
ArrayList<String>(Arrays.asList(toAdd));
System.out.println("Set
System.out.println("Set size:
size: "" ++ produce.size());
produce.size());
System.out.println("Set
System.out.println("Set contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
}}
}}
for
for (String
(String ff :: toFind)
toFind) {{
if
if (produce.contains(f))
(produce.contains(f))
System.out.println(f
System.out.println(f ++ "" is
is on
on the
the list");
list");
else
else
System.out.println(f
System.out.println(f ++ "" is
is not
not on
on the
the list");
list");
}}
35

36. Поиск

Set
Set size:
size: 88
Set
Set contents:
contents: [apple,
[apple, carrot,
carrot, kiwi,
kiwi, potato,
potato, tomato,
tomato, pear,
pear, cucumber,
cucumber, orange]
orange]
carrot
carrot is
is on
on the
the list
list
tomato
is
on
the
list
tomato is on the list
onion
onion is
is not
not on
on the
the list
list
cucumber
cucumber is
is on
on the
the list
list
potato
potato is
is on
on the
the list
list
36

37.

Класс LinkedList<E>
37

38. Класс LinkedList<E>

Класс LinkedList<E>
public
public class
class LinkedList<E>
LinkedList<E> extends
extends AbstractSequentialList<E>
AbstractSequentialList<E> implements
implements List<E>,...,
List<E>,..., Cloneable,
Cloneable, Serializable
Serializable
{{
private
private transient
transient Entry<E>
Entry<E> header
header == new
new Entry<E>(null,
Entry<E>(null, null,
null, null);
null);
private
private transient
transient int
int size
size == 0;
0;
public
public
public
public
LinkedList()
LinkedList()
LinkedList(Collection<?
LinkedList(Collection<? extends
extends E>
E> c)
c)
public
public boolean
boolean add(E
add(E element)
element)
public
void
add(int
index,
public void add(int index, EE element)
element)
boolean
addAll(int
index,
Collection<?
boolean addAll(int index, Collection<? extends
extends E>
E> c)
c)
public
public EE set(int
set(int index,
index, EE element)
element)
public
public EE get(int
get(int index)
index)
public
public
public
public
public
public
boolean
boolean contains(Object
contains(Object o)
o)
int
int indexOf(Object
indexOf(Object o)
o)
int
int lastIndexOf(Object
lastIndexOf(Object o)
o)
public
public
public
public
public
public
EE remove(int
remove(int index)
index)
boolean
boolean remove(Object
remove(Object o)
o)
void
void clear()
clear()
public
public
public
public
}}
ListIterator<E>
ListIterator<E>
ListIterator<E>
ListIterator<E>
listIterator()
listIterator()
listIterator(int
listIterator(int index)
index)
List<E>
List<E> subList(int
subList(int from,
from, int
int to)
to)
private
static
class
Entry<E>
{
private static class Entry<E> {
...
...
}}
C
Класс LinkedList реализует интерфейс List с помощью двусвязного
списка. Для элементов двусвязного списка используется внутренний
класс Entry<E>.
38

39.

Позиционный доступ
39

40. Позиционный доступ

public
public class
class ListGetSetDemo
ListGetSetDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
String[]
String[] toAdd
toAdd == {{ "apple",
"apple", "carrot",
"carrot", "kiwi",
"kiwi", "potato",
"potato", "tomato",
"tomato", "pear",
"pear",
"cucumber",
"orange"
};
"cucumber", "orange" };
List<String>
List<String> produce
produce == new
new LinkedList<String>();
LinkedList<String>();
Collections.addAll(produce,
Collections.addAll(produce, toAdd);
toAdd);
//
List<String>
produce
=
new
// List<String> produce = new ArrayList<String>(Arrays.asList(toAdd));
ArrayList<String>(Arrays.asList(toAdd));
System.out.println("Set
System.out.println("Set size:
size: "" ++ produce.size());
produce.size());
System.out.println("Set
System.out.println("Set contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
for
for (int
(int ii == 0;
0; ii << produce.size();
produce.size(); i++)
i++) {{
String
String to
to == produce.get(i).toUpperCase();
produce.get(i).toUpperCase();
String
String prev
prev == produce.set(i,
produce.set(i, to);
to);
System.out.println("Changing
System.out.println("Changing "" ++ prev
prev ++ "" to
to "" ++ to);
to);
}}
}}
}}
System.out.println("\nSet
System.out.println("\nSet size:
size: "" ++ produce.size());
produce.size());
System.out.println("Set
System.out.println("Set contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
40

41. Позиционный доступ

Set
Set size:
size: 88
Set
Set contents:
contents: [apple,
[apple, carrot,
carrot, kiwi,
kiwi, potato,
potato, tomato,
tomato, pear,
pear, cucumber,
cucumber, orange]
orange]
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
Changing
apple
apple to
to APPLE
APPLE
carrot
to
carrot to CARROT
CARROT
kiwi
kiwi to
to KIWI
KIWI
potato
potato to
to POTATO
POTATO
tomato
tomato to
to TOMATO
TOMATO
pear
pear to
to PEAR
PEAR
cucumber
cucumber to
to CUCUMBER
CUCUMBER
orange
orange to
to ORANGE
ORANGE
Set
Set size:
size: 88
Set
Set contents:
contents: [APPLE,
[APPLE, CARROT,
CARROT, KIWI,
KIWI, POTATO,
POTATO, TOMATO,
TOMATO, PEAR,
PEAR, CUCUMBER,
CUCUMBER, ORANGE]
ORANGE]
Позиционный доступ в LinkedList лучше
не использовать. Он требует затрат
O(N).
41

42.

Сортировка списков
42

43. Сортировка

Списки можно сортировать используя метод sort
из класса Collections. Для сортировки можно
использовать естественный порядок или объект
класса реализующего интерфейс Comparator<E>.
43

44. Сортировка

public
public class
class ListSortDemo
ListSortDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
String[]
String[] toAdd
toAdd == {{ "orange",
"orange", "apple",
"apple", "carrot",
"carrot", "kiwi",
"kiwi", "potato",
"potato", "banana",
"banana", "tomato",
"tomato",
"pear",
"cucumber"};
"pear", "cucumber"};
List<String>
List<String> produce
produce == new
new ArrayList<String>();
ArrayList<String>();
Collections.addAll(produce,
Collections.addAll(produce, toAdd);
toAdd);
//List<String>
produce
=
new
//List<String> produce = new ArrayList<String>(Arrays.asList(toAdd));
ArrayList<String>(Arrays.asList(toAdd));
System.out.println("Set
System.out.println("Set contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
System.out.println("Sorting
System.out.println("Sorting ...\n");
...\n");
Collections.sort(produce);
Collections.sort(produce);
}}
}}
System.out.println("Set
System.out.println("Set contents:
contents: "" ++ produce
produce ++ "\n");
"\n");
Set
Set contents:
contents: [orange,
[orange, apple,
apple, carrot,
carrot, kiwi,
kiwi, potato,
potato, banana,
banana, tomato,
tomato, pear,
pear, cucumber]
cucumber]
Sorting
Sorting ...
...
Set
Set contents:
contents: [apple,
[apple, banana,
banana, carrot,
carrot, cucumber,
cucumber, kiwi,
kiwi, orange,
orange, pear,
pear, potato,
potato, tomato]
tomato]
Класс String реализует интерфейс Comparable.
Эта реализация использует лексикографический
порядок.
44

45. Сортировка с Comparable

public
public class
class AnotherListSortDemo
AnotherListSortDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
List<Item>
List<Item> items
items == new
new ArrayList<Item>();
ArrayList<Item>();
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
Item("Toaster",
Item("Toaster", 1234));
1234));
Item("Kettle",
Item("Kettle", 4562));
4562));
Item("Microwave
Item("Microwave oven",
oven", 9912));
9912));
Item("Coffemaker",
Item("Coffemaker", 2912));
2912));
Item("Blender",
1231));
Item("Blender", 1231));
System.out.println("Set
System.out.println("Set contents:
contents: ");
");
for(Item
for(Item item
item :: items)
items)
System.out.println(item);
System.out.println(item);
System.out.println("\nSorting
System.out.println("\nSorting ...\n");
...\n");
Collections.sort(items);
Collections.sort(items);
}}
}}
System.out.println("Set
System.out.println("Set contents:
contents: ");
");
for(Item
for(Item item
item :: items)
items)
System.out.println(item);
System.out.println(item);
45

46. Сортировка с Comparable

Set
Set contents:
contents:
[name=Toaster,
[name=Toaster, number=1234]
number=1234]
[name=Kettle,
[name=Kettle, number=4562]
number=4562]
[name=Microwave
[name=Microwave oven,
oven, number=9912]
number=9912]
[name=Coffemaker,
number=2912]
[name=Coffemaker, number=2912]
[name=Blender,
[name=Blender, number=1231]
number=1231]
Sorting
Sorting ...
...
Set
Set contents:
contents:
[name=Blender,
[name=Blender, number=1231]
number=1231]
[name=Toaster,
[name=Toaster, number=1234]
number=1234]
[name=Coffemaker,
[name=Coffemaker, number=2912]
number=2912]
[name=Kettle,
[name=Kettle, number=4562]
number=4562]
[name=Microwave
[name=Microwave oven,
oven, number=9912]
number=9912]
46

47. Сортировка с Comparator

public
public class
class ComparatorListSortDemo
ComparatorListSortDemo {{
public
public static
static void
void main(String[]
main(String[] args)
args) {{
List<Item>
List<Item> items
items == new
new ArrayList<Item>();
ArrayList<Item>();
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
items.add(new
Item("Toaster",
Item("Toaster", 1234));
1234));
Item("Kettle",
Item("Kettle", 4562));
4562));
Item("Microwave
Item("Microwave oven",
oven", 9912));
9912));
Item("Coffemaker",
Item("Coffemaker", 2912));
2912));
Item("Blender",
1231));
Item("Blender", 1231));
System.out.println("Set
System.out.println("Set contents:
contents: ");
");
for(Item
for(Item item
item :: items)
items)
System.out.println(item);
System.out.println(item);
System.out.println("\nSorting
System.out.println("\nSorting ...\n");
...\n");
Collections.sort(items,
Collections.sort(items, new
new NameComparator());
NameComparator());
}}
}}
System.out.println("Set
System.out.println("Set contents:
contents: ");
");
for(Item
for(Item item
item :: items)
items)
System.out.println(item);
System.out.println(item);
47

48. Сортировка с Comparator

Set
Set contents:
contents:
[name=Toaster,
[name=Toaster, number=1234]
number=1234]
[name=Kettle,
[name=Kettle, number=4562]
number=4562]
[name=Microwave
[name=Microwave oven,
oven, number=9912]
number=9912]
[name=Coffemaker,
number=2912]
[name=Coffemaker, number=2912]
[name=Blender,
[name=Blender, number=1231]
number=1231]
Sorting
Sorting ...
...
Set
Set contents:
contents:
[name=Blender,
[name=Blender, number=1231]
number=1231]
[name=Coffemaker,
[name=Coffemaker, number=2912]
number=2912]
[name=Kettle,
[name=Kettle, number=4562]
number=4562]
[name=Microwave
[name=Microwave oven,
oven, number=9912]
number=9912]
[name=Toaster,
number=1234]
[name=Toaster, number=1234]
48

49.

Сравнение производительности
49

50. Сравнение производительности

public
public class
class ListsPerformanceDemo
ListsPerformanceDemo {{
private
private static
static final
final int
int ITERATIONS
ITERATIONS == 2000000;
2000000;
public
public static
static void
void main(String[]
main(String[] args)
args) {{
List<String>
List<String> linkedList
linkedList == new
new LinkedList<String>();
LinkedList<String>();
for
for (int
(int ii == 0;
0; ii << ITERATIONS;
ITERATIONS; i++)
i++) {{
linkedList.add(""
linkedList.add("" ++ (i
(i %% 10));
10));
}}
long
long startTime
startTime == System.currentTimeMillis();
System.currentTimeMillis();
for
for (int
(int ii == 0;
0; ii << 1000;
1000; i++)
i++)
linkedList.add(0,"");
linkedList.add(0,"");
long
long endTime
endTime == System.currentTimeMillis();
System.currentTimeMillis();
System.out.println("LinkedList
System.out.println("LinkedList time:
time: "" ++ (endTime
(endTime -- startTime));
startTime));
List<String>
List<String> arrayList
arrayList == new
new ArrayList<String>();
ArrayList<String>();
for
for (int
(int ii == 0;
0; ii <<
arrayList.add(""
arrayList.add(""
}}
ITERATIONS;
ITERATIONS; i++)
i++) {{
++ (i
(i %% 10));
10));
startTime
startTime == System.currentTimeMillis();
System.currentTimeMillis();
for
for (int
(int ii == 0;
0; ii << 1000;
1000; i++)
i++)
arrayList.add(0,"");
arrayList.add(0,"");
}}
}}
endTime
endTime == System.currentTimeMillis();
System.currentTimeMillis();
System.out.println("ArrayList
System.out.println("ArrayList time:
time: "" ++ (endTime
(endTime -- startTime));
startTime));
50

51. Сравнение производительности

LinkedList
LinkedList time:
time: 00
ArrayList
ArrayList time:
time: 10484
10484
Как правило использование ArrayList быстрее чем LinkedList. В данном примере
специально был выбран самый неподходящий вариант использования ArrayList.
51