Пишем свой arraylist java

QuadTheMage / MyArrayList.java

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

package com . company ;

import java . util .*;

/**

* Моя реализация ArrayList

*/

public class MyArrayList < E >implements List < E >

private int size = 0 ;

private int capacity = 0 ;

private final int CAPACITY = 16 ;

private Object [] array ;

public MyArrayList ()

capacity = CAPACITY ;

array = new Object [ capacity ];

>

public MyArrayList ( int capacity )

this . capacity = capacity ;

array = new Object [ capacity ];

>

private void increaseCapacity ()

capacity = capacity * 2 ;

Object [] newArray = new Object [ capacity ];

for ( int i = 0 ; i < size ; i ++)

newArray [ i ] = array [ i ];

array [ i ] = null ;

>

array = newArray ;

>

private void trimToSizeArray ()

capacity = size + 1 ;

Object [] newArray = new Object [ capacity ];

System . arraycopy ( array , 0 , newArray , 0 , size );

array = newArray ;

>

@ Override

public int size ()

return size ;

>

@ Override

public boolean isEmpty ()

return size == 0 ;

>

@ Override

public boolean contains ( Object o )

return indexOf ( o ) >= 0 ;

>

@ Override

public Iterator iterator ()

return null ;

>

@ Override

public Object [] toArray ()

Object [] newArray = new Object [ size ];

System . arraycopy ( array , 0 , newArray , 0 , size );

return newArray ;

>

@ Override

public boolean add ( Object o )

if ( size >= capacity )

increaseCapacity ();

>

array [ size ++] = o ;

return true ;

>

private void shiftToLeft ( int start )

size —;

if ( size <= 0 )

return ;

>

if ( size != start )

System . arraycopy ( array , start + 1 , array , start , size — start );

>

array [ size ] = null ;

>

@ Override

public boolean remove ( Object o )

if (( size == 0 ))

return false ;

>

int i ;

for ( i = 0 ; i < size ; i ++)

if ( array [ i ] == null && o == null )

break ;

>

if (( array [ i ] != null ) && ( array [ i ]. equals ( o )))

break ;

>

>

if ( i < size )

shiftToLeft ( i );

return true ;

>

return false ;

>

@ Override

public boolean addAll ( Collection c )

if ( c == null )

return false ;

>

if ( c . isEmpty ())

return false ;

>

for ( Object item : c )

add ( item );

>

return true ;

>

@ Override

public boolean addAll ( int index , Collection c )

if ( c == null )

return false ;

>

if ( c . isEmpty () || ( index < 0 ))

return false ;

>

if ( index > size )

index = size ;

>

for ( Object item : c )

add ( index ++, item );

>

return true ;

>

@ Override

public void clear ()

for ( int i = 0 ; i < size ; i ++)

array [ i ] = null ;

>

size = 0 ;

>

@ Override

public E get ( int index )

if (( index < size ) && ( index >= 0 ))

return ( E ) array [ index ];

>

return null ;

>

@ Override

public Object set ( int index , Object element )

if (( index < size ) && ( index >= 0 ))

Object o = array [ index ];

array [ index ] = element ;

return o ;

>

return null ;

>

@ Override

public void add ( int index , Object element )

if ( index < 0 )

return ;

>

if ( size + 1 >= capacity )

increaseCapacity ();

>

if ( index > size )

index = size ;

>

for ( int i = size ; i >= index ; i —)

array [ i + 1 ] = array [ i ];

>

array [ index ] = element ;

size ++;

>

@ Override

public E remove ( int index )

Object o = null ;

if (( index < size ) && ( index >= 0 ))

o = get ( index );

shiftToLeft ( index );

>

return ( E ) o ;

>

@ Override

public int indexOf ( Object o )

if ( o == null )

for ( int i = 0 ; i < size ; i ++)

if ( array [ i ] == null )

return i ;

>

>

> else

for ( int i = 0 ; i < size ; i ++)

if ( o . equals ( array [ i ]))

return i ;

>

>

>

return — 1 ;

>

@ Override

public int lastIndexOf ( Object o )

int lastIndex = — 1 ;

if ( o == null )

for ( int i = 0 ; i < size ; i ++)

if ( array [ i ] == null )

lastIndex = i ;

>

>

return lastIndex ;

> else

for ( int i = 0 ; i < size ; i ++)

if ( o . equals ( array [ i ]))

lastIndex = i ;

>

>

>

return lastIndex ;

>

@ Override

public ListIterator listIterator ()

return null ;

>

@ Override

public ListIterator listIterator ( int index )

return null ;

>

@ Override

public List subList ( int fromIndex , int toIndex )

if ( fromIndex > toIndex )

int temp = fromIndex ;

fromIndex = toIndex ;

toIndex = temp ;

>

if (( fromIndex < 0 ) || ( toIndex >size ))

return null ;

>

List myArrayList = new MyArrayList ( toIndex — fromIndex );

for ( int i = fromIndex ; i < toIndex ; i ++)

myArrayList . add ( array [ i ]);

>

return myArrayList ;

>

@ Override

public boolean retainAll ( Collection c )

if ( c == null )

return true ;

>

if ( c . size () == 0 )

clear ();

return true ;

>

int i = 0 ;

boolean modyfied = false ;

while ( i < size )

if ( c . contains ( array [ i ]))

i ++;

> else

shiftToLeft ( i );

modyfied = true ;

>

>

return modyfied ;

>

@ Override

public boolean removeAll ( Collection c )

if ( c == null )

return false ;

>

if (( c . size () == 0 ) || ( size == 0 ))

return false ;

>

boolean modyfied = false ;

int i = 0 ;

while ( i < size )

if ( c . contains ( array [ i ]))

shiftToLeft ( i );

modyfied = true ;

> else

i ++;

>

>

return modyfied ;

>

@ Override

public boolean containsAll ( Collection c )

if ( c == null )

return false ;

>

if ( c . size () == 0 )

return true ;

>

for ( Object e : c )

if ( contains ( e ))

;

> else

return false ;

>

>

return true ;

>

@ SuppressWarnings ( «unchecked» )

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

if ( a . length < size )

// Make a new array of a’s runtime type, but my contents:

return ( T []) Arrays . copyOf ( array , size , a . getClass ());

System . arraycopy ( array , 0 , a , 0 , size );

if ( a . length > size )

a [ size ] = null ;

return a ;

>

>

Источник

Русские Блоги

Напишите код для укрепления алгоритма обучения Q в обучении и сообщите об ошибке: Вначале «Argmax» был отброшен. Вместо этого вам нужно использовать «idxmax». Используйте функц.

Синтаксис конвейера Jenkins (in)

Директивы Окружающая обстановка environmentВ инструкции указывается серия пар «ключ-значение». Эти пары «ключ-значение» будут определены как переменные среды для всех шагов или опр.

Примечания к исследованию Rabbitmq 5: модель публикации / подписки

1. Концепции и модели В модели публикации и подписки одно и то же сообщение отправляется нескольким потребителям. Этот режим реализуется путем добавления маршрутизации. Производитель сообщения отправл.

Поток Python (2): простая синхронизация потока реализации блокировки

В Python есть два типа замков. Один блокировка -это исходный замок (примитивный), который не может быть повторен, а другой -рекурсивный блокировка, который может быть переведен. Вместо этого модуль по.

Как создать эффективную разбивку на страницы в ASP.NET Core

содержание Вступление фон Создать проект Обработка пейджинга в бэкэнде Создайте элемент управления пользовательского интерфейса подкачки Добавить поисковый фильтр Пользовательские элементы управления .

Источник

Структуры данных в картинках. ArrayList

Взбрело мне в голову написать несколько статей, о том как реализованы некоторые структуры данных в Java. Надеюсь, статьи будут полезны визуалам (картинки наше всё), начинающим java-визуалам а также тем кто уже умеет писать new ArrayList(), но слабо представляет что же происходит внутри.

Сегодня поговорим о ArrayList-ах

ArrayList — реализует интерфейс List. Как известно, в Java массивы имеют фиксированную длину, и после того как массив создан, он не может расти или уменьшаться. ArrayList может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта. Элементы ArrayList могут быть абсолютно любых типов в том числе и null.

Создание объекта

ArrayList list = new ArrayList();

Только что созданный объект list, содержит свойства elementData и size.

Хранилище значений elementData есть ни что иное как массив определенного типа (указанного в generic), в нашем случае String[]. Если вызывается конструктор без параметров, то по умолчанию будет создан массив из 10-ти элементов типа Object (с приведением к типу, разумеется).

elementData = (E[]) new Object[10];

Вы можете использовать конструктор ArrayList(capacity) и указать свою начальную емкость списка.

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

Внутри метода add(value) происходят следующие вещи:

1) проверяется, достаточно ли места в массиве для вставки нового элемента;

2) добавляется элемент в конец (согласно значению size) массива.

Весь метод ensureCapacity(minCapacity) рассматривать не будем, остановимся только на паре интересных мест. Если места в массиве не достаточно, новая емкость рассчитывается по формуле (oldCapacity * 3) / 2 + 1. Второй момент это копирование элементов. Оно осуществляется с помощью native метода System.arraycopy(), который написан не на Java.

 // newCapacity - новое значение емкости elementData = (E[])new Object[newCapacity]; // oldData - временное хранилище текущего массива с данными System.arraycopy(oldData, 0, elementData, 0, size); 

Ниже продемонстрирован цикл, поочередно добавляющий 15 элементов:

При добавлении 11-го элемента, проверка показывает что места в массиве нет. Соответственно создается новый массив и вызывается System.arraycopy().

После этого добавление элементов продолжается

Добавление в «середину» списка

Добавление элемента на позицию с определенным индексом происходит в три этапа:

1) проверяется, достаточно ли места в массиве для вставки нового элемента;

2) подготавливается место для нового элемента с помощью System.arraycopy();

 System.arraycopy(elementData, index, elementData, index + 1, size - index); 

3) перезаписывается значение у элемента с указанным индексом.

 elementData[index] = element; size++; 

Как можно догадаться, в случаях, когда происходит вставка элемента по индексу и при этом в вашем массиве нет свободных мест, то вызов System.arraycopy() случится дважды: первый в ensureCapacity(), второй в самом методе add(index, value), что явно скажется на скорости всей операции добавления.

В случаях, когда в исходный список необходимо добавить другую коллекцию, да еще и в «середину», стоит использовать метод addAll(index, Collection). И хотя, данный метод скорее всего вызовет System.arraycopy() три раза, в итоге это будет гораздо быстрее поэлементного добавления.

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

Удалять элементы можно двумя способами:
— по индексу remove(index)
— по значению remove(value)

С удалением элемента по индексу всё достаточно просто

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

 int numMoved = size - index - 1; 

затем копируем элементы используя System.arraycopy()

 System.arraycopy(elementData, index + 1, elementData, index, numMoved); 

уменьшаем размер массива и забываем про последний элемент

 elementData[--size] = null; // Let gc do its work 

При удалении по значению, в цикле просматриваются все элементы списка, до тех пор пока не будет найдено соответствие. Удален будет лишь первый найденный элемент.

Дополнение 1: Как верно заметил MikeMirzayanov, при удалении элементов текущая величина capacity не уменьшается, что может привести к своеобразным утечкам памяти. Поэтому не стоит пренебрегать методом trimToSize().

Итоги

— Быстрый доступ к элементам по индексу за время O(1);
— Доступ к элементам по значению за линейное время O(n);
— Медленный, когда вставляются и удаляются элементы из «середины» списка;
— Позволяет хранить любые значения в том числе и null;
— Не синхронизирован.

Ссылки

Пишите в комментариях пожелания/замечания и есть ли смысл продолжать.

Источник