Data structures in pictures. Linkedlist

Greetings to you, habrazhiteli!

I continue what I have begun, namely, I am trying to tell (using visual images) how some data structures are implemented in Java.



Last time we talked about ArrayList , today we are eyeing LinkedList.

LinkedList - implements the List interface. It is a representative of a bidirectional list, where each structure element contains pointers to the previous and next elements. The iterator supports round trip. Implements methods for getting, deleting and inserting in the beginning, middle and end of the list. Allows you to add any elements including null.

Object creation

List<String> list = new LinkedList<String>();

Footprint{Objects=2, References=4, Primitives=[int x 2]}
Object size: 48 bytes

The newly created list object contains the properties header and size .

header is a pseudo-element of the list. Its value is always null , a next and prev always indicate the first and last element of the list, respectively. Since at the moment the list is still empty, the properties next and prev point to themselves (ie, to the header element ). Size list size is 0.

header.next = header.prev = header;

Adding items

list.add("0");

Footprint{Objects=5, References=8, Primitives=[int x 5, char]}
Object size: 112 bytes

Adding an element to the end of the list using the add (value) , addLast (value) method
and adding to the top of the list using addFirst (value) is performed in O (1) time.

Inside the LinkedList class, there is a static inner Entry class with which new elements are created.

privatestaticclassEntry<E>
{
    E element;
    Entry<E> next;
    Entry<E> prev;
	
    Entry(E element, Entry<E> next, Entry<E> prev)
    {
        this.element = element;
        this.next = next;
        this.prev = prev;
    }
}

Each time a new item is added, essentially two steps are taken:

1) a new instance of the Entry class is created

Entry newEntry = new Entry("0", header, header.prev);

2) redefined pointers to the previous and next item

newEntry.prev.next = newEntry;
newEntry.next.prev = newEntry;
size++;

Add another item

list.add("1");

Footprint{Objects=8, References=12, Primitives=[int x 8, char x 2]}
Object size: 176 bytes

one)

// header.prev указывает на элемент с индексом 0
Entry newEntry = new Entry("1", header, header.prev);

2)

Adding items to the “middle” of the list

In order to add an element to a specific position in the list, you must call the add (index, value) method . The difference from add (value) is in the definition of the element before which it will be inserted.

(index == size ? header : entry(index))

The entry (index) method scans the entire list in search of an element with the specified index. The direction of the traversal is determined by the condition (index <(size >> 1)) . In fact, it turns out that not more than half of the list is sorted out to find the right element, but from the point of view of asymptotic analysis, the search time increases linearly - O (n).

private Entry<E> entry(int index){
    if (index < 0 || index >= size)
        thrownew IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    Entry<E> e = header;

    if (index < (size >> 1))
    {
        for (int i = 0; i <= index; i++)
            e = e.next;
    }
    else
    {
        for (int i = size; i > index; i--)
            e = e.prev;
    }

    return e;
}

As you can see, the developer can catch an IndexOutOfBoundsException if the specified index is negative or greater than the current size value . This is true for all methods where the index appears in the parameters.

list.add(1, "100");

Footprint{Objects=11, References=16, Primitives=[int x 11, char x 5]}
Object size: 248 bytes

one)

// entry указывает на элемент с индексом 1, entry.prev на элемент с индексом 0
Entry newEntry = new Entry("100", entry, entry.prev);

2)

Deleting items

You can remove items from the list in several ways:
- from the beginning or the end of the list using removeFirst () , removeLast () in O (1) time;
- at the remove (index) index and at the remove (value) value in O (n) time.

Consider deletion by value

list.remove("100");

Footprint{Objects=8, References=12, Primitives=[int x 8, char x 2]}
Object size: 176 bytes

Inside the remove (value) method, all the elements of the list are searched for. Only the first found item will be deleted.

In general, deletion from the list can be divided into 3 steps:

1) search for the first item with the corresponding value 2) redefine the pointers to the previous and next item

// Значение удаляемого элемента сохраняется// для того чтобы в конце метода вернуть его
E result = e.element;
e.prev.next = e.next;
e.next.prev = e.prev;

3) deleting pointers to other elements and forgetting the element itself.

e.next = e.prev = null;
e.element = null;
size--;

Iterators

For a personal search of elements, you can use the “built-in” iterator. I will not go deep, the processes going on inside are very similar to what is described above.

ListIterator<String> itr = list.listIterator();

The above code will put the pointer at the top of the list. You can also start iterating over elements from a specific place, for this you need to pass an index to the listIterator (index) method . In case you need to start the traversal from the end of the list, you can use the descendingIterator () method .

It is worth remembering that ListIterator will fall down from ConcurrentModificationException , if after creating an iterator, the list has been changed not through its own iterator methods.

Well and just in case a primitive example of sorting the elements:

while (itr.hasNext())
    System.out.println(itr.next());

Results

- From LinkedList you can organize a stack, a queue, or a double queue, with access time O (1);
- To insert and delete from the middle of the list, to obtain an element by index or value, it will take linear time O (n). However, adding (and removing from the middle of the list) using ListIterator.add () and ListIterator.remove () will require O (1);
- Allows you to add any values ​​including null. For storage of primitive types, it uses the corresponding wrapper classes;
- Not synchronized.

Links

Sources LinkedList
Sources LinkedList of JDK7
Sources JDK OpenJDK & trade 6 Source Release - Build b23

volume of memory was measured using the instrument memory-measurer . You will also need Guava (Google Core Libraries) to use it.