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

Содержание

Слайд 2

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

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


Слайд 3

Списки

Списки

Слайд 4

Интерфейс List public interface List extends Collection { boolean add(E e);

Интерфейс List

public interface List extends Collection {
boolean add(E e);
void

add(int index, E element);
boolean addAll(Collection c);
void addAll(int index, Collection c);
E set(int index, E element);
E get(int index);
boolean contains(Object o);
boolean containsAll(Collection c);
int indexOf(Object o);
int lastIndexOf(Object o);
int size();
boolean isEmpty();
boolean remove(Object o);
E remove(int index);
boolean removeAll(Collection c);
boolean retainAll(Collection c);
void clear();
Iterator iterator();
ListIterator listIterator();
ListIterator listIterator(int index);
List subList(int fromIndex, int toIndex);
Object[] toArray();
T[] toArray(T[] a);
boolean equals(Object o);
int hashCode();
}

I

Слайд 5

Интерфейс RandomAccess public interface RandomAccess { } I

Интерфейс RandomAccess

public interface RandomAccess {
}

I

Слайд 6

Реализации интерфейса List

Реализации интерфейса List




Слайд 7

Класс EmptyList


Класс EmptyList

Слайд 8

Класс EmptyList public class Collections { public static final List EMPTY_LIST

Класс EmptyList

public class Collections {
public static final List EMPTY_LIST = new

EmptyList();
public static final List emptyList() {
return (List) EMPTY_LIST;
}
private static class EmptyList extends AbstractList implements RandomAccess, Serializable {
private static final long serialVersionUID = 8842843931221139166L;
public int size() {return 0;}
public boolean contains(Object obj) {return false;}
public Object get(int index) {
throw new IndexOutOfBoundsException("Index: "+index);
}
// Preserves singleton property
private Object readResolve() {
return EMPTY_LIST;
}
}
}

emptyList()

new EmptyList()

return 0

AbstractList

EMPTY_LIST

EMPTY_LIST

C

Слайд 9

Использование EmptyList public class EmptyListDemo { public static void main(String[] args)

Использование EmptyList

public class EmptyListDemo {
public static void main(String[] args) {

List staff = Collections.emptyList();
System.out.println("\nList contents: ");
for (String value : staff) {
System.out.println("name = " + value);
}
System.out.println("\nList size: " + staff.size());
}
}
List contents:
List size: 0
Слайд 10

Сравнение производительности для пустого List public class EmptyListsCompareDemo { private static

Сравнение производительности для пустого List

public class EmptyListsCompareDemo {
private static final int

ITERATIONS = 10000000;
public static void main(String[] args) {
List theList;
long now = System.currentTimeMillis();
for (int i = 0; i < ITERATIONS; i++){
theList = new ArrayList();
}
System.out.println("Time using ArrayList(): " + (System.currentTimeMillis() - now) + " ms");
now = System.currentTimeMillis();
for (int i = 0; i < ITERATIONS; i++){
theList = new ArrayList(0);
}
System.out.println("Time using ArrayList(0): " + (System.currentTimeMillis() - now) + " ms");
now = System.currentTimeMillis();
for (int i = 0; i < ITERATIONS; i++){
theList = new LinkedList();
}
System.out.println("Time using LinkedList(): " + (System.currentTimeMillis() - now) + " ms");
now = System.currentTimeMillis();
for (int i = 0; i < ITERATIONS; i++){
theList = Collections.emptyList();
}
System.out.println("Time using Collections.emptyList(): " + (System.currentTimeMillis() - now) + " ms");
}
}
Слайд 11

Сравнение производительности для пустого List Time using ArrayList(): 312 ms Time

Сравнение производительности для пустого List
Time using ArrayList(): 312 ms
Time using ArrayList(0):

188 ms
Time using LinkedList(): 1187 ms
Time using Collections.emptyList(): 31 ms
Слайд 12

Класс SingletonList


Класс SingletonList

Слайд 13

Класс SingletonList public class Collections { public static List singletonList(T o)

Класс SingletonList

public class Collections {
public static List singletonList(T o) {

return new SingletonList(o);
}
private static class SingletonList extends AbstractList implements RandomAccess, Serializable {
static final long serialVersionUID = 3093736618740652951L;
private final E element;
SingletonList(E obj) {element = obj;}
public int size() { return 1;}
public boolean contains(Object obj) {return eq(obj, element);}
public E get(int index) {
if (index != 0)
throw new IndexOutOfBoundsException("Index: "+index+", Size: 1");
return element;
}
}
...
}

private final E element

return 1

SingletonList(o)

AbstractList)

C

Слайд 14

Использование SingletonList public class SingletonListDemo { public static void main(String[] args)

Использование SingletonList

public class SingletonListDemo {
public static void main(String[] args) {

List staff = Collections.singletonList("Harry Hacker");
System.out.println("\nList contents: ");
for (String value : staff) {
System.out.println("name = " + value);
}
System.out.println("\nList size: " + staff.size());
}
}
List contents:
name = Harry Hacker
List size: 1
Слайд 15

Сравнение производительности для List с одним элементом public class OneValueListsCompareDemo {

Сравнение производительности для List с одним элементом

public class OneValueListsCompareDemo {
public static

void main(String[] args) {
List theList;
long now = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++){
theList = new ArrayList();
theList.add("Harry Hacker");
}
System.out.println("Time using ArrayList(): " + (System.currentTimeMillis() - now) + " ms");
now = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++){
theList = new ArrayList(1);
theList.add("Harry Hacker");
}
System.out.println("Time using ArrayList(1): " + (System.currentTimeMillis() - now) + " ms");
now = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++){
theList = new LinkedList();
theList.add("Harry Hacker");
}
System.out.println("Time using LinkedList(): " + (System.currentTimeMillis() - now) + " ms");
now = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++){
theList = Collections.singletonList("Harry Hacker");
}
System.out.println("Time using SingletonList(): " + (System.currentTimeMillis() - now) + " ms");
}
}
Слайд 16

Сравнение производительности для List с одним элементом Time using ArrayList(): 359

Сравнение производительности для List с одним элементом
Time using ArrayList(): 359 ms
Time

using ArrayList(1): 266 ms
Time using LinkedList(): 1406 ms
Time using SingletonList(): 78 ms
Слайд 17

Класс ArrayList


Класс ArrayList

Слайд 18

Класс ArrayList public class ArrayList extends AbstractList implements List , RandomAccess,

Класс ArrayList

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable

{
private transient Object[] elementData;
private int size;
public ArrayList()
public ArrayList(int initialCapacity)
public ArrayList(Collection c)
public void trimToSize()
public void ensureCapacity(int minCapacity)
public boolean add(E e)
public void add(int index, E element)
public boolean addAll(Collection c)
public E set(int index, E element)
public E get(int index)
public boolean contains(Object o)
public int indexOf(Object o)
public int lastIndexOf(Object o)
public E remove(int index)
public boolean remove(Object o)
public void clear()
public int size()
public boolean isEmpty()
public Object[] toArray()
public E[] toArray(E[])
public Object clone()
}

C

Object[] elementData

int size

Слайд 19

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


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

Слайд 20

public class ArrayListCapacityDemo { private static final int ITERATIONS = 25000000;

public class ArrayListCapacityDemo {
private static final int ITERATIONS = 25000000;

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

Изменение ёмкости
ArrayList with ensureCapacity() time: 312
ArrayList without ensureCapacity() time: 641

Слайд 21

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


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

Слайд 22

Добавление элементов public class SimpleListAddDemo { public static void main(String[] args)

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

public class SimpleListAddDemo {
public static void main(String[] args) {
List

fruits = new ArrayList();
fruits.add("apple");
fruits.add("orange");
fruits.add("kiwi");
fruits.add("apple");
fruits.add("apple");
fruits.add("mango");
fruits.add("pear");
fruits.add("pear");
fruits.add("apple");
fruits.add("orange");
System.out.println("List contents: " + fruits);
}
}
List contents: [apple, orange, kiwi, apple, apple, mango, pear, pear, apple, orange]
Слайд 23

Добавление элементов по индексу public class ListInsertDemo { public static void

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

public class ListInsertDemo {
public static void main(String[]

args) {
List fruits = new ArrayList();
fruits.add(0,"apple");
fruits.add(0,"banana");
fruits.add(0,"kiwi");
fruits.add(0,"mango");
fruits.add(0,"orange");
fruits.add(0,"peach");
fruits.add(0,"pear");
System.out.println("List contents: " + fruits);
fruits.clear();
fruits.add(0,"apple");
fruits.add(1,"banana");
fruits.add(2,"kiwi");
fruits.add(3,"mango");
fruits.add(4,"orange");
fruits.add(5,"peach");
fruits.add(6,"pear");
System.out.println("List contents: " + fruits);
}
}
List contents: [pear, peach, orange, mango, kiwi, banana, apple]
List contents: [apple, banana, kiwi, mango, orange, peach, pear]
Слайд 24

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


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

Слайд 25

Удаление элементов public class ListRemoveDemo { public static void main(String[] args)

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

public class ListRemoveDemo {
public static void main(String[] args)

{
String[] toAdd = { "apple", "cucumber", "carrot", "kiwi", "potato",
"tomato", "cucumber", "orange", "carrot", "tomato" };
String[] toRemove = { "carrot", "tomato", "onion", "cucumber", "potato" };
List produce = new ArrayList();
Collections.addAll(produce, toAdd);
// List produce = new ArrayList(Arrays.asList(toAdd));
System.out.println("List size: " + produce.size());
System.out.println("List contents: " + produce + "\n");
for (String f : toRemove) {
if (produce.remove(f))
System.out.println(f + " was removed. List contents: " + produce);
else
System.out.println(f + " was not removed");
}
System.out.println("\nFinal list size: " + produce.size());
System.out.println("Final list contents: " + produce + "\n");
}
}
Слайд 26

Удаление элементов List size: 10 List contents: [apple, cucumber, carrot, kiwi,

Удаление элементов
List size: 10
List contents: [apple, cucumber, carrot, kiwi, potato, tomato,

cucumber, orange, carrot, tomato]
carrot was removed. List contents: [apple, cucumber, kiwi, potato, tomato, cucumber, orange, carrot, tomato]
tomato was removed. List contents: [apple, cucumber, kiwi, potato, cucumber, orange, carrot, tomato]
onion was not removed
cucumber was removed. List contents: [apple, kiwi, potato, cucumber, orange, carrot, tomato]
potato was removed. List contents: [apple, kiwi, cucumber, orange, carrot, tomato]
Final list size: 6
Final list contents: [apple, kiwi, cucumber, orange, carrot, tomato]
Слайд 27

Удаление элементов по индексу public class ListRemoveAtIndexDemo { public static void

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

public class ListRemoveAtIndexDemo {
public static void main(String[]

args) {
String[] toAdd = { "apple", "cucumber", "carrot", "kiwi", "potato",
"tomato", "cucumber", "orange", "carrot", "tomato" };
List produce = new ArrayList();
Collections.addAll(produce, toAdd);
// List produce = new ArrayList(Arrays.asList(toAdd));
System.out.println("List size: " + produce.size());
System.out.println("List contents: " + produce + "\n");
for (int i = 0; i < toAdd.length; i++) {
String removed = produce.remove(0);
System.out.println(removed + " was removed. List contents: "
+ produce);
}
System.out.println("\nFinal list size: " + produce.size());
System.out.println("Final list contents: " + produce + "\n");
}
}
Слайд 28

Удаление элементов по индексу List size: 10 List contents: [apple, cucumber,

Удаление элементов по индексу
List size: 10
List contents: [apple, cucumber, carrot, kiwi,

potato, tomato, cucumber, orange, carrot, tomato]
apple was removed. List contents: [cucumber, carrot, kiwi, potato, tomato, cucumber, orange, carrot, tomato]
cucumber was removed. List contents: [carrot, kiwi, potato, tomato, cucumber, orange, carrot, tomato]
carrot was removed. List contents: [kiwi, potato, tomato, cucumber, orange, carrot, tomato]
kiwi was removed. List contents: [potato, tomato, cucumber, orange, carrot, tomato]
potato was removed. List contents: [tomato, cucumber, orange, carrot, tomato]
tomato was removed. List contents: [cucumber, orange, carrot, tomato]
cucumber was removed. List contents: [orange, carrot, tomato]
orange was removed. List contents: [carrot, tomato]
carrot was removed. List contents: [tomato]
tomato was removed. List contents: []
Final list size: 0
Final list contents: []
Слайд 29

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


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

Слайд 30

Позиционный доступ public class ListGetSetDemo { public static void main(String[] args)

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

public class ListGetSetDemo {
public static void main(String[] args) {

String[] toAdd = { "apple", "carrot", "kiwi", "potato", "tomato", "pear",
"cucumber", "orange" };
List produce = new ArrayList();
Collections.addAll(produce, toAdd);
// List produce = new ArrayList(Arrays.asList(toAdd));
System.out.println("Set size: " + produce.size());
System.out.println("Set contents: " + produce + "\n");
for (int i = 0; i < produce.size(); i++) {
String to = produce.get(i).toUpperCase();
String prev = produce.set(i, to);
System.out.println("Changing " + prev + " to " + to);
}
System.out.println("\nSet size: " + produce.size());
System.out.println("Set contents: " + produce + "\n");
}
}
Слайд 31

Позиционный доступ Set size: 8 Set contents: [apple, carrot, kiwi, potato,

Позиционный доступ
Set size: 8
Set contents: [apple, carrot, kiwi, potato, tomato, pear,

cucumber, orange]
Changing apple to APPLE
Changing carrot to CARROT
Changing kiwi to KIWI
Changing potato to POTATO
Changing tomato to TOMATO
Changing pear to PEAR
Changing cucumber to CUCUMBER
Changing orange to ORANGE
Set size: 8
Set contents: [APPLE, CARROT, KIWI, POTATO, TOMATO, PEAR, CUCUMBER, ORANGE]
Слайд 32

Поиск


Поиск

Слайд 33

Поиск первого и последнего вхождения public class ListIndexOfDemo { public static

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

public class ListIndexOfDemo {
public static void

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

Поиск первого и последнего вхождения Set size: 11 Set contents: [apple,

Поиск первого и последнего вхождения
Set size: 11
Set contents: [apple, cucumber, carrot,

kiwi, potato, tomato, pear, cucumber, orange, carrot, tomato]
carrot is on the list, first index: 2, last index: 9
tomato is on the list, first index: 5, last index: 10
onion is not on the list
cucumber is on the list, first index: 1, last index: 7
potato is on the list, first index: 4, last index: 4
Слайд 35

Поиск public class ListContainsDemo { public static void main(String[] args) {

Поиск

public class ListContainsDemo {
public static void main(String[] args) {
String[] toAdd

= { "apple", "carrot", "kiwi", "potato", "tomato",
"pear", "cucumber", "orange" };
String[] toFind = { "carrot", "tomato", "onion", "cucumber", "potato" };
List produce = new ArrayList();
Collections.addAll(produce, toAdd);
//List produce = new ArrayList(Arrays.asList(toAdd));
System.out.println("Set size: " + produce.size());
System.out.println("Set contents: " + produce + "\n");
for (String f : toFind) {
if (produce.contains(f))
System.out.println(f + " is on the list");
else
System.out.println(f + " is not on the list");
}
}
}
Слайд 36

Поиск Set size: 8 Set contents: [apple, carrot, kiwi, potato, tomato,

Поиск
Set size: 8
Set contents: [apple, carrot, kiwi, potato, tomato, pear, cucumber,

orange]
carrot is on the list
tomato is on the list
onion is not on the list
cucumber is on the list
potato is on the list
Слайд 37

Класс LinkedList


Класс LinkedList

Слайд 38

Класс LinkedList public class LinkedList extends AbstractSequentialList implements List ,..., Cloneable,

Класс LinkedList

public class LinkedList extends AbstractSequentialList implements List,..., Cloneable, Serializable {

private transient Entry header = new Entry(null, null, null);
private transient int size = 0;
public LinkedList()
public LinkedList(Collection c)
public boolean add(E element)
public void add(int index, E element)
boolean addAll(int index, Collection c)
public E set(int index, E element)
public E get(int index)
public boolean contains(Object o)
public int indexOf(Object o)
public int lastIndexOf(Object o)
public E remove(int index)
public boolean remove(Object o)
public void clear()
public ListIterator listIterator()
public ListIterator listIterator(int index)
List subList(int from, int to)
private static class Entry {
...
}
}

C

Слайд 39

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


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

Слайд 40

Позиционный доступ public class ListGetSetDemo { public static void main(String[] args)

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

public class ListGetSetDemo {
public static void main(String[] args) {

String[] toAdd = { "apple", "carrot", "kiwi", "potato", "tomato", "pear",
"cucumber", "orange" };
List produce = new LinkedList();
Collections.addAll(produce, toAdd);
// List produce = new ArrayList(Arrays.asList(toAdd));
System.out.println("Set size: " + produce.size());
System.out.println("Set contents: " + produce + "\n");
for (int i = 0; i < produce.size(); i++) {
String to = produce.get(i).toUpperCase();
String prev = produce.set(i, to);
System.out.println("Changing " + prev + " to " + to);
}
System.out.println("\nSet size: " + produce.size());
System.out.println("Set contents: " + produce + "\n");
}
}
Слайд 41

Позиционный доступ Set size: 8 Set contents: [apple, carrot, kiwi, potato,

Позиционный доступ
Set size: 8
Set contents: [apple, carrot, kiwi, potato, tomato, pear,

cucumber, orange]
Changing apple to APPLE
Changing carrot to CARROT
Changing kiwi to KIWI
Changing potato to POTATO
Changing tomato to TOMATO
Changing pear to PEAR
Changing cucumber to CUCUMBER
Changing orange to ORANGE
Set size: 8
Set contents: [APPLE, CARROT, KIWI, POTATO, TOMATO, PEAR, CUCUMBER, ORANGE]
Слайд 42

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


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

Слайд 43

Сортировка

Сортировка

Слайд 44

Сортировка public class ListSortDemo { public static void main(String[] args) {

Сортировка

public class ListSortDemo {
public static void main(String[] args) {
String[] toAdd

= { "orange", "apple", "carrot", "kiwi", "potato", "banana", "tomato",
"pear", "cucumber"};
List produce = new ArrayList();
Collections.addAll(produce, toAdd);
//List produce = new ArrayList(Arrays.asList(toAdd));
System.out.println("Set contents: " + produce + "\n");
System.out.println("Sorting ...\n");
Collections.sort(produce);
System.out.println("Set contents: " + produce + "\n");
}
}
Set contents: [orange, apple, carrot, kiwi, potato, banana, tomato, pear, cucumber]
Sorting ...
Set contents: [apple, banana, carrot, cucumber, kiwi, orange, pear, potato, tomato]
Слайд 45

Сортировка с Comparable public class AnotherListSortDemo { public static void main(String[]

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

public class AnotherListSortDemo {
public static void main(String[] args)

{
List items = new ArrayList();
items.add(new Item("Toaster", 1234));
items.add(new Item("Kettle", 4562));
items.add(new Item("Microwave oven", 9912));
items.add(new Item("Coffemaker", 2912));
items.add(new Item("Blender", 1231));
System.out.println("Set contents: ");
for(Item item : items)
System.out.println(item);
System.out.println("\nSorting ...\n");
Collections.sort(items);
System.out.println("Set contents: ");
for(Item item : items)
System.out.println(item);
}
}
Слайд 46

Сортировка с Comparable Set contents: [name=Toaster, number=1234] [name=Kettle, number=4562] [name=Microwave oven,

Сортировка с Comparable
Set contents:
[name=Toaster, number=1234]
[name=Kettle, number=4562]
[name=Microwave oven, number=9912]
[name=Coffemaker, number=2912]
[name=Blender, number=1231]
Sorting

...
Set contents:
[name=Blender, number=1231]
[name=Toaster, number=1234]
[name=Coffemaker, number=2912]
[name=Kettle, number=4562]
[name=Microwave oven, number=9912]
Слайд 47

Сортировка с Comparator public class ComparatorListSortDemo { public static void main(String[]

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

public class ComparatorListSortDemo {
public static void main(String[] args)

{
List items = new ArrayList();
items.add(new Item("Toaster", 1234));
items.add(new Item("Kettle", 4562));
items.add(new Item("Microwave oven", 9912));
items.add(new Item("Coffemaker", 2912));
items.add(new Item("Blender", 1231));
System.out.println("Set contents: ");
for(Item item : items)
System.out.println(item);
System.out.println("\nSorting ...\n");
Collections.sort(items, new NameComparator());
System.out.println("Set contents: ");
for(Item item : items)
System.out.println(item);
}
}
Слайд 48

Сортировка с Comparator Set contents: [name=Toaster, number=1234] [name=Kettle, number=4562] [name=Microwave oven,

Сортировка с Comparator
Set contents:
[name=Toaster, number=1234]
[name=Kettle, number=4562]
[name=Microwave oven, number=9912]
[name=Coffemaker, number=2912]
[name=Blender, number=1231]
Sorting

...
Set contents:
[name=Blender, number=1231]
[name=Coffemaker, number=2912]
[name=Kettle, number=4562]
[name=Microwave oven, number=9912]
[name=Toaster, number=1234]
Слайд 49

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


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

Слайд 50

Сравнение производительности public class ListsPerformanceDemo { private static final int ITERATIONS

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

public class ListsPerformanceDemo {
private static final int ITERATIONS =

2000000;
public static void main(String[] args) {
List linkedList = new LinkedList();
for (int i = 0; i < ITERATIONS; i++) {
linkedList.add("" + (i % 10));
}
long startTime = System.currentTimeMillis();
for (int i = 0; i < 1000; i++)
linkedList.add(0,"");
long endTime = System.currentTimeMillis();
System.out.println("LinkedList time: " + (endTime - startTime));
List arrayList = new ArrayList();
for (int i = 0; i < ITERATIONS; i++) {
arrayList.add("" + (i % 10));
}
startTime = System.currentTimeMillis();
for (int i = 0; i < 1000; i++)
arrayList.add(0,"");
endTime = System.currentTimeMillis();
System.out.println("ArrayList time: " + (endTime - startTime));
}
}
Слайд 51

Сравнение производительности LinkedList time: 0 ArrayList time: 10484

Сравнение производительности
LinkedList time: 0
ArrayList time: 10484