The JAVA container – said LinkedList

Preface

In the previous article, I interview questions and answers in the form of learning with everyone ArrayList, interested, but did not read the students, you can look through my article records, with ArrayList, natural LinkedList indispensable.

PS: because I live in Zhuhai two days ago suffered typhoon Columba, the original life after 2 days with no water and no electricity no network no signal, so this article for a long time failed to complete and publish, please understand.

Here, I’ll learn our frequently used load container LinkedList (source code analysis based on JDK8) in the form of an interview question and answer

Questions and answers

One

Q: please briefly explain what you know about LinkedList, what it can be used for and how it can be used

Answer:

  • LinkedList bottom is a two-way linked list, while achieving the List interface and Deque interface, so it can be regarded as a sequential container, can also be viewed as a queue (Queue), but also can be regarded as a stack (Stack), but if you want to use the stack or queue data structure, recommended ArrayDeque, as a stack or queue will have better performance than using LinkedList.

Sample code:

/ / create a LinkedList, each node list of the memory space is allocated in real time, so there is no need to pre specified container size LinkedList< String> = new; linkedList LinkedList< String> (); / / linkedList.add element added to the container ("three"); linkedList.add ("Lee four"); / / Zhang three and four Li inserted between a king (five linkedList.add 1, "king five"); / / the insertion of a linkedList.addFirst in the head Mistress ("mistress"); / / get the index subscript 2 element five String element = linkedList.get King (2); / / modify the index subscript 2 elements five is a small Wang linkedList.set (2, "small"); / / delete index subscript 1 elements three String removeElement = L InkedList.remove (1); / / delete the first element of String = linkedList.removeFirst (removeFirstElement); / / delete the last element of String (removeLastElement = linkedList.removeLast);
  • LinkedList implementation is a two-way linked list, core elements are: int size = 0 for recording list length; Node< E> first; for the recording head (first) node (storage is a reference to the first node); Node< E> last; used to record the tail (the last node is stored () reference tail node).

Sample code:

Public class LinkedList< E> extends; AbstractSequentialList< E> implements List< E> Deque< E>, Cloneable, java.io.Serializable, transient {/ / chain length record int size = 0; / * * * Pointer to first node. to a node in a * Invariant: (first = = null & & last = || * (null) first.prev = = null & & first.item! = null) * / transient Node< E> first; / * * * Pointer to last node. points to the last node * Invariant: (first = = null & & last = null) || * (last.next = = null & & last.item! = null) * / transient Node< E> last;}
  • The core of two-way linked list elements are one of the most important Node< E> Node< E>, including: E item; Node< data elements for storage, E> next; successor node, pointing to the current element Node< E> prev; precursor node to the current element.

Sample code:

The bottom of the LinkedList / * * * definition private static class * / node Node< E> E {item; / / storage element data Node< E> next; / / Node< successor node points to the current element; E> prev; / * * * / / precursor node to the current node element Node structure method (Node< / Node; E> prev, E, element, Node< E> next) {this.item = element; / / storage element this.next = next; / / prev / / this.prev = successor node; precursor node}}
The JAVA container - said LinkedList
two-way linked list bottom implementation, pictures from the network

The head in the figure above is Node< E> first; tail; that is, Node< last; E>

Two

Q: please analyze how it gets elements, modify elements, add new elements and delete elements, and analyze the time complexity of these operations.

Answer:

  • Get the element: LinkedList provides three ways to obtain elements, namely:
  1. Gets the first element getFirst (), gets the first element, returns the Node&lt directly; E> first points to the node, so the time complexity is O (1).
  2. Take the last element, getLast (), fetch the last element, return directly to Node< E> last point to the node, so the time complexity is O (1).
  3. Access to the specified index position of index element get (int index), the Node< E> node is stored in memory of the storage space is not continuous, so a position to find the node, only through the way of traversing the list search node, so the LinkedList will be judged by index < (size > > 1 size> > 1), which is half of the size/2 length of the current list, determine the index position is on the list of the first half or the second part. The decision is to traverse the head to find the data or to traverse the lookup data from the tail. In the worst case, to obtain the intermediate element, you need to traverse n/2 times to get the corresponding element, so the time complexity of this method is O (n).
  • To sum up, the time complexity of LinkedList getting elements is O (n).

Sample code:

/ * * * returns a list of the element at the specified position in the specified position * * @param index index * @return returns the element at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} * public E get (int index) {/ / index to check the legality of subscript [0, size) checkElementIndex (index); / / get the corresponding index position traverse the list elements (index return node.Item);} / * * * * private void to check the legality of the subscript checkElementIndex (int index) {if (! IsElementIndex (index) new (outOfBoundsMsg) throw IndexOutOfBoundsException (index));} private Boolean isElementIndex (int index) {return index > = 0; & & index < size;} / * * * Return To specify the location of the node elements (focus) * / Node< E> node (int index) {/ / assert isElementIndex (index); / / judge index position is in the list of the first half or the second part of if (index < (size; > > 1)) {/ / AB node begins from front to back traverse to find node elements corresponding to the location of Node< E> X = first; for (int i = 0; I < index; i++) x = x.next; return x;} else {/ / from the beginning of the tail node, from the back after the traverse to find node elements corresponding to the location of Node< E& gt; X = last; for (int i = size - 1; I > index; i--) x = x.prev; return x;}}
  • Modify elements: LinkedList provides a way to modify element data set (int, index, E, element), the steps to modify the element data are: 1. check whether the index index is legal, [0, size). 2. binary query to obtain the corresponding index elements. 3. assign new elements to return old elements. By the analysis of elements that binary query time complexity is O (n), the modified element data and the time complexity is O (n).

Sample code:

Specify the location of the node / * * * * * @param index data storage location specified * @param element to modify the stored data * @return return not before the amendment of the stored data of IndexOutOfBoundsException * @throws {@inheritDoc} * / public E set (int index, E element) {/ / index to check the legality of subscript [0, size) checkElementIndex (index); / / binary the query to obtain the corresponding index element Node< E> X = node (index); / / the new assignment, return to the old elements E oldVal = x.item; x.item = element; return oldVal;}
  • New element: LinkedList provides four methods for adding new elements, namely:
  1. Insert the specified element into the first position of the list, addFirst (E E), simply point the head node first to the new element node, and then point the predecessor pointer of the original first node to the new element node. You do not need to move the original data storage location, just exchange the pointer field information of the related nodes. So the time complexity is O (1).
  2. Insert the specified element into the last position of the list, addLast (E E), simply point the tail node last to the new element node, and then point the successor pointer of the last node to the new element node. You do not need to move the original data storage location, just exchange the pointer field information of the related nodes. The time complexity is also O (1).
  3. Adding element methods add (E, e) is equivalent to addLast (E, e).
  4. The specified element is inserted into the specified location in the list of index add (int index, E element), according to the position of index need to call node (index) to obtain the position of the original node traversing the list, and then in front of the new node inserted into the original position of the node, without moving the original data storage location pointer domain information you can only exchange the relevant node. The time complexity is also O (1).
  • To sum up, the time complexity of the new element in LinkedList is O (1). The operation of inserting new elements is very efficient, especially inserted into the head or inserted into the tail. But if you insert through index index, the location of the insertion is closer to the middle of the list, the longer it takes, because you need to iterate through the list.
The JAVA container - said LinkedList
adds element node diagrams, and pictures come from the big data structure

Sample code:

* / * * will specify the elements inserted into the list of the first position in * * @param e * public void to insert elements addFirst (E E) {linkFirst (E);} / * * * e elements as the first element of the void / private linkFirst (E E) {/ / get the original head final Node< E& gt; F = first; / / initialize the elements node final Node< E> new; newNode = Node< > (null, e, f); / / head pointer to the new node first = newNode; / / if it is the first element (the list is empty) if (F = = null) / / the tail pointer is a pointer to the new node last = newNode; / / else / / not empty list the first node of the original precursor pointer to the new node F.prev = newNode; / / record list length size + 1 size++; modCount++;} / * * * will specify the elements inserted into the list of the last position in * * < p> this method is equivalent with add (E E) {@link #add}. * * @param e * public void to insert elements (E, e addLast linkLast (E)) {}; / * * * will specify the elements inserted into the list of the last position in * * < p> this method is equivalent with addLast (E E) {@link #addLast}. * * @param e * @return {@code to insert elements true} (as specified by {@link Collection#add} public Boolean (add). E E) {linkLast (E); return true;} / * * * e as the last element An element of linkLast (E E / void) {/ / get the original tail node final Node< E> L = last; / / initialize the elements node final Node< E> new; newNode = Node< > (L, e, null); / / a pointer to the new node last = newNode; / / if it is the first one element (the list is empty) if (L = = null) / / the head pointer is a pointer to the new node first = newNode; / / else / / list is not empty successor node of the original tail pointer to the new node l.next = newNode; / / record list length size + 1 size++; modCount++;} / * * * will be inserted into the specified element list the location specified in index * * @param index The position of the index * to insert to insert @param element * @throws IndexOutOfBoundsException {@inheritDoc} * / public element of void add (int index, E element) {/ / check the legality of the [0 insertion position, size] checkPositionIndex (index); / / if you insert the position and the current list of equal length, is directly inserted into the end of the linked list of if elements (index = = size) / / elements inserted into the end of the linked list linkLast (element); / / else element will be inserted to the designated location, node (index) to obtain possession of the index position of the original node linkBefore (element, node (index));} / * * * * private void check position of the legality of the checkPositionIndex (int index {if (isPosi)! TionIndex (index) new (outOfBoundsMsg) throw IndexOutOfBoundsException (index));} / * * * * private Boolean check position of the legality of the isPositionIndex (int index) {/ / size] legal position is [0, return index > & = 0; & = index; < size;} / * * * e to insert the new elements in front of the old succ linkBefore (E / void elements e, Node< E> succ) {/ / assert succ! = null; / / succ precursor records the old element node pointer final Node< E> PRED = succ.prev; / / initialize the elements node final Node< E> new; newNode = Node< > (PRED, e, succ) the precursor; / / pointer element node node to old elements (i.e. new elements to the old node element node The front, instead of the old elements position) succ.prev = newNode; / / if the old precursor pointer element node is empty, that old node is the first node element, element node insertion to / / in front of the old element nodes, so the new head node is a node element if (PRED = first = null) newNode; else / / not inserted into the head pointer / successor predecessor node of the old elements pointing element node pred.next = newNode; / / record list length size + 1 size++; modCount++;}
  • Delete elements: LinkedList provides four ways to delete elements, namely:
  1. Delete the first element in the list removeFirst (), simply point the head node first to the subsequent node of the deleted element node, and empty the pointer information prev of the predecessor node. You do not need to move the original data storage location, just operate the pointer field information of the related nodes. So the time complexity is O (1).
  2. Delete the last element in the list removeLast (), simply point the tail node last to the predecessor of the deleted element node and empty the pointer information of the subsequent node next. There is no need to move the location of the original data storage, and only the pointer field information of the related nodes can be operated, so the time complexity is also O (1).
  3. The specified location elements of index (int index), remove deleted according to need a position index call node (index) original node traversing the list to obtain the location of the next successor node pointer domain and delete predecessor node element node to delete the element node node successor node.prev.next = node.next, prev precursor node pointer domain successor delete node element node to delete the element node precursor node can be node.next.prev = node.prev (there may be some around, do not understand the students to learn about the two-way linked list data structure, it) does not need to move the original data storage location, can only pointer domain information exchange related node. The time complexity is also O (1).
The JAVA container - said LinkedList
removes the element node sketch, and the picture comes from the big data structure
  1. Delete the incoming Object o the specified object, object of comparison is consistent with o.equals method remove (Object o), and 3. of the basic ideas about, the key is to compare the object through the o.equals method, you can remember this.
  • To sum up, the time complexity of LinkedList deleting elements is O (1). The operation of deleting elements is very efficient, especially deleting the first node or deleting the last node. But if you delete them in indexed index or object objects, you need to iterate over the list, find objects that correspond to the index index, or judge objects using the equals method.

Sample code:

Delete the list * / * * * * and returns the first element of the list in the first @return * @throws NoSuchElementException if this list element is empty E (removeFirst / public) {/ / according to the head node gets the first element node final Node< E> F = first; if (F = = null) / / no element node throw new (NoSuchElementException) throws exception; return unlinkFirst (f);} / * * * * private E to remove the first element unlinkFirst (Node< E> F) {/ / assert f = = first & & F! = null; / / final E domain data records to element = f.item to remove the element node; / / to remove the recording element node successor node pointer final Node< E& Gt; next = f.next; / / empty to delete the node data pointer domain and next domain information, to help the recycling of f.item = null; f.next = null; / / help / / GC head to remove the element node successor node first = next; / / if you want to remove the element node after node is empty, then that list only one element / / so it is necessary to tail pointer information node is to clear the if (next = = null) last = null; / / else will be the first node of the new precursor node pointer information clear next.prev = null; / / record list length size 1 size--; modCount++ return element; / / return data domain remove the element node;} / * * * Delete the list and returns the last element in the list of @return * * * @throws NoSuchElementException the last element of the if this list is empty E (removeLast / public) {/ / according to the tail node acquires the last element node of final Node< E> L = last; if (L = = null) / / no element node throw new NoSuchElementException is thrown (); return unlinkLast (L);} / * * * * / remove the last element of private E unlinkLast (Node< E> L) {/ / assert L = = last & & L = null; / /! Records to final E element data domain = l.item remove element node; to remove the element node records / precursor node pointer final Node< E> ; prev = l.prev; / / empty to delete the node data pointer domain and prev domain information, to help the recycling of l.item = null; l.prev = null; / / help / / GC head to remove the element node precursor node last = prev; / / if you want to remove the predecessor node element node is empty, that list only one element / / so it is necessary to head pointer information node is to clear the if (prev = = null) first = null; else / / the last node of the successor node pointer information clear prev.next = null; / / record list length size 1 size--; modCount++ return element; / / return to remove the data domain element node;} / * * * The specified location elements of the index * * @param index delete to delete the location of index * @return to delete the original position * @throws IndexOutOfBoundsException {@inheritDoc} * / public element of E remove (int index) {/ / index to check the legality of subscript [0, size) checkElementIndex (index); / / according to index traversing the list to delete access node. Then call the unlink method to remove the return unlink (node (index));} / * * * delete incoming Object o the specified object, object of comparison is consistent with o.equals method is to remove the Object * @param o o * @return {@code true} the specified object is to delete object o / public Boolean remove (Object o) {if you delete the object / / null, While traversing the list to find the node.item data domain node null and remove the if (o = = null) {for (Node< E> X = first; X = null; X! = x.next) {if (x.item = = null) {unlink (x); return true;}}} else {/ / start traversal the list, whether through the equals method and compared one by one node.item / / equal equal object, delete this object. For (Node< E> X = first; X = null; X! = x.next) {if (o.equals (x.item)) {unlink (x); return true;}}}} / * * * return false; X / E unlink removes the specified node (Node< E> x) {/ / assert X! = null; / / final E domain data records to element = x.item to remove the element node; / / record to remove the element node successor node pointer final Node< E> next = x.next; / / record to remove the element node precursor node pointer final Node< E> prev = x.prev; / / if you want to remove the predecessor node element node the empty, is shown to be deleted node is the first node if (prev = = null) {/ / the first node to delete the element node successor node first = next;} else {/ / successor pointer precursor node to delete the element node to delete element node successor node prev.next = next; / / empty to delete the node precursor node pointer information to help GC x.prev = null;} / / if you want to remove the element node of the successor node is empty, is shown to be deleted node for the last node of if (next = = null) {/ / tail node to delete the element node precursor node last = prev;} else {/ / precursor pointer successor node to delete element node to node next.pr precursor delete element node EV = prev; / / successor node pointer information to delete empty nodes, to help GC x.next = null;} / / empty to remove elements of the data domain, to help GC x.item = null; / / record list length size 1 size--; modCount++; / / return element returns the data domain remove element node;}

Three

Q: could you compare ArrayList and LinkedList, then?

Answer:

  1. LinkedList internally stores Node< E> not only to maintain the data domain, but also to maintain prev and next; if there are many nodes in LinkedList, LinkedList is more memory than ArrayList.
  2. Insert delete operation efficiency:
  • LinkedList in the insertion and deletion, insertion or deletion of the head or tail is efficient, the operation is close to the middle position of the element, need to traverse the search speed is relatively slow, if a large amount of data in, compared the cost of traversing searching each insert or delete when. So, LinkedList inserts and deletes, slow in traversal lookup, and just changes the reference address of the related node.
  • ArrayList in the insertion and deletion, insertion or deletion of the tail of the same is efficient, operating in other positions, you need to move batch elements, so ArrayList insertion and deletion, fast traversal search, slow in batch moving elements.
  1. Cyclic ergodic efficiency:
  • Since ArrayList implements the RandomAccess random access interface, the use of for (I = int = 0; I < size; i++) traversal is faster than using the Iterator iterator:
For (int, i=0, n=list.size ()), I, N; i++) {list.get (I);} runs, faster, than, this, loop:, for (Iterator, i=list.iterator (); i.hasNext ()) {i.next ();} <
  • Since LinkedList does not implement the RandomAccess interface, it is recommended to iterate through the data using the Iterator iterator.
  1. Therefore, if we need to change frequently in the list of central insert or delete elements, recommend the use of LinkedList, otherwise, recommend the use of ArrayList, because the ArrayList traversal to find elements of fast data domain and only storage elements, without the need for additional records other data location information, can save memory space.

Four

Q: is LinkedList thread safe?

A: LinkedList is not thread safe and can cause data inconsistency or data corruption if multiple threads change data to the same LinkedList at the same time. If there is not thread safe operation, LinkedList will try to throw ConcurrentModificationException to prevent abnormal data, when we were in the traversal of a LinkedList, during the traversal, we cannot add to LinkedList, delete the number of changes according to the structure of the operation, otherwise it will throw a ConcurrentModificationException, this is fail-fast (rapid failure mechanism). From the source code analysis, we change the LinkedList data in add, remove and so on, will lead to changes in modCount, when expectedModCount = modCount, then throw ConcurrentModificationException. If you want thread safety, consider calling Collections.synchronizedCollection (Collection< T> c) methods.

Sample code:

Private class ListItr implements ListIterator< E> E> lastReturned {private Node< private; Node< E> next; private int nextIndex; private int expectedModCount = modCount; ListItr (int index) {/ / assert isPositionIndex (index); next (index = = = size)? Null: node (index); nextIndex = index public (hasNext);} Boolean {return nextIndex < size public;} E {checkForComodification (next) (if); (hasNext) throw (!) new (NoSuchElementException); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; Public Boolean (hasPrevious)} {0}; return nextIndex > public E (previous) {checkForComodification (if); (hasPrevious) throw (!) new (NoSuchElementException); lastReturned (next = next = = = null)? Last: next.prev; nextIndex--; return lastReturned.item; int (nextIndex) {public} return nextIndex public int (previousIndex);} return {nextIndex} - 1; public void (remove) {checkForComodification (); if (lastReturned = = null) throw new (IllegalStateException); Node< E> lastNext = Las TReturned.next; unlink (lastReturned); if (next = = lastReturned) next = lastNext; else = nextIndex--; lastReturned null; expectedModCount++ public void;} set (E E) {if (lastReturned = = null) throw new (IllegalStateException); checkForComodification (); lastReturned.item = E;} public void add (E e) {(checkForComodification); lastReturned = null; if (next = = null) linkLast (E); else linkBefore (E, next); nextIndex++ expectedModCount+; public void;} ForEachRemaining (Consumer< super? E> action) {Objects.requireNonNull (action) while (modCount = = expectedModCount; & & nextIndex < size) {action.accept (next.item); lastReturned = next; next = next.next; nextIndex++; checkForComodification;}} (final) void (checkForComodification) {if (modCount = expectedModCount! New ConcurrentModificationException (throw));}}

summary

  • Conclusion LinkedList has in the third part of the show, so I will not repeat that, in the form of interview and study with you LinkedList, because there is no time to draw, this may not ArrayList say so clearly, if you cannot read the place, please look at the data structure about list. If this article is helpful to you, please have a problem. Thank you.