Java
Raiting:
3

Data structures are in the pictures. ArrayList


This article explains how to implement some data structures in Java. It will be useful for beginners that use a programming language Java, as well as those who already know how to write a new ArrayList (), but have little knowledge what is happening inside.

image

Let us talk about the ArrayLists

ArrayList implements the List interface. As we know, Java arrays have a fixed length, and after the array is created, it cannot increase or decrease. ArrayList can change its size at runtime, but it does not necessarily indicate the size when an object is created. The elements of ArrayList can be any types, including null.

Creating an object

ArrayList<String> list = new ArrayList<String>();
The newly created object list contains the properties of elementData and size.

Storage of values elementData is a certain type of an array (that is specified in generic), in this case is String []. If the constructor is called without parameters, then by default will be created an array of 10 elements of Object type .

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

You can use the constructor ArrayList (capacity) and specify its initial capacity of the list.

Adding elements

list.add("0");
image

Inside of a method add(value) occur the following things:

1) It is ensured whether an array has enough space to insert a new element;

ensureCapacity(size + 1);
2) It is added an element to the end of an array (according to size).

elementData[size++] = element;
We will not consider the whole method ensureCapacity(minCapacity), let us discuss only a couple of interesting points. If the array does not have enough space, the new capacity is calculated by the formula (oldCapacity * 3) / 2 + 1. The second point is to copy the elements. It is implemented with usage of native method System.arraycopy (), which is not written in Java.

// newCapacity
elementData = (E[])new Object[newCapacity];

// oldData – temporary storage of the current array with data
System.arraycopy(oldData, 0, elementData, 0, size);

Below is shown the cycle that alternately is adding 15 elements:

list.add("1");
image

...

list.add("9");
image

list.add("10");
When we add 11th element, check shows that there is not enough space in the array. Accordingly, a new array is created and is called System.arraycopy().

image

After that, we continue add elements

image
...

list.add("14");
image

Adding to the "middle" of list

list.add(5, "100");

Adding an element with a particular index in three stages:

1) It is ensured whether an array has enough space to insert a new element;

ensureCapacity(size+1);
2) It is prepared a space for the new element using System.arraycopy();

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

3) It is rewritten the value of element at the specified index.

elementData[index] = element;
size++;

image

As we might guess, where is inserted an element at index and at the same time an array does not have enough space, then the call of System.arraycopy () will happen twice: the first will be in ensureCapacity (), and a second will be in the method add(index, value), that obviously will affect the speed of adding operation.

In cases, where another collection will be needed to add to the source list, and even in the "middle", we should use the method addAll(index, Collection). Although this method is likely will call System.arraycopy () three times, and eventually it will be much faster than elementwise adding.

Removing elements

We can remove the elements in two ways:
- by index remove(index)
- by value remove(value)

Removing element by index

list.remove(5);
First, we determine how many elements should be copied

int numMoved = size - index - 1;
then we copy the elements using System.arraycopy ()

System.arraycopy(elementData, index + 1, elementData, index, numMoved);
we reduce the size of the array and forget about the last element

elementData[--size] = null; // Let gc do its work
When we remove by value, in the process is scanned all list elements until it finds a match. There will be removed only the first element.

Appendix 1: When removing elements, the current value of capacity does not get reduced, this may lead to a kind of memory leaks. So let us do not neglect the method trimToSize ().

Results

- Quick access to the elements by the index in time O(1).
- Access to the elements by the value in linear time O(n).
- Slow access when are inserted and removed elements from the "middle" of the list.
- It allows storing any values, including null.
- It is not synchronized.

Links

Source: ArrayList
Source: ArrayList out of JDK7
Sources: JDK OpenJDK & trade 6 Source Release - Build b23
ZimerMan 17 december 2011, 18:29
Vote for this post
Bring it to the Main Page
 

Comments

Leave a Reply

B
I
U
S
Help
Avaible tags
  • <b>...</b>highlighting important text on the page in bold
  • <i>..</i>highlighting important text on the page in italic
  • <u>...</u>allocated with tag <u> text shownas underlined
  • <s>...</s>allocated with tag <s> text shown as strikethrough
  • <sup>...</sup>, <sub>...</sub>text in the tag <sup> appears as a superscript, <sub> - subscript
  • <blockquote>...</blockquote>For  highlight citation, use the tag <blockquote>
  • <code lang="lang">...</code>highlighting the program code (supported by bash, cpp, cs, css, xml, html, java, javascript, lisp, lua, php, perl, python, ruby, sql, scala, text)
  • <a href="http://...">...</a>link, specify the desired Internet address in the href attribute
  • <img src="http://..." alt="text" />specify the full path of image in the src attribute