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-list element. 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). The size of the size list 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 beginning of the list with 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.

 private static class Entry<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) create a new instance of the class Entry

 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) throw new 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

There are several ways to remove items from the list:
- from the beginning or the end of the list using removeFirst () , removeLast () in time O (1);
- 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, removal from the list can be divided into 3 steps:

1) search for the first element with the corresponding value



2) redefined 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

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

The amount of memory used was measured using the memory-measurer tool . You will also need Guava (Google Core Libraries) to use it.