LinkedList
LinkendList is a two-way linked list and implements the Deque ue interface, which can be used as a queue. Although LinkendList is a linear structure, the data is not stored as a linear interface, but as data and address of the next node in each node, Cloneable interface, copy support, and java.io.Serializable support serialization and deserialization.
-
Cloneable , Serializable interface through train: Analysis of ArrayList source code of java framework collection List subinterface
-
Data structure through train: Analysis of sequential storage structure and chain storage structure of data structure, with pictures and texts, and it has risen again
-
Queue through train : Queue of linear data structure (Queue)
Deque
Deque is the abbreviation of double ended queue, which supports the insertion and removal of elements at both ends, and is customarily called double ended queue. Most deque implementations have no fixed limit on the number of elements they may contain, but the interface supports capacity-limited deques as well as deques with no fixed-size limit
Deque also extends the Queue interface. When Deque is used as a queue, it will produce FIFO (first in, first out) behavior. Elements are added at the end of the deque and removed from the beginning.
The function of the double-ended queue is that it can be added from the head of the queue or added from the tail of the queue, and it can be obtained from the tail of the queue or obtained from the head of the queue.
Comparison of Deque and Queue methods
Deque | Queue | |
add element to the end of the queue | add(E e) / offer(E e) | addLast(E e) offerLast(E e) |
Take the first element of the queue and delete it | E remove() E poll() | E removeFirst() E pollFirst() |
Take the first element of the queue without removing it | E element() E peek() | E getFirst() E peekFirst() |
Add elements to the head of the team | none | addFirst(E e) offerFirst(E e) |
Take the tail element and delete it | none | E removeLast() E pollLast() |
Fetch tail element without removing | none | E getLast() E peekLast() |
You can see that LinkendList is a collection, a queue, and a stack, but when we use it, we always reference it with a specific interface because we have the interface specification code The level of abstraction is higher, and the methods defined by the interface itself represent a specific purpose.
// Not recommended spelling: LinkedList<String> d1 = new LinkedList<>(); d1.offerLast("z"); // Recommended spelling: Deque<String> d2 = new LinkedList<>(); d2.offerLast("z");
It can be seen that a principle of abstract-oriented programming is: try to hold interfaces instead of specific implementation classes.
LinkendList constructor
Constructor | describe |
LinkedList() | This constructor builds an empty linked list. |
LinkedList(Collection c) | This constructor builds a linked list, initialized with the elements of set c. |
// The number of nodes in the current list transient int size = 0; // first node transient Node<E> first; // last node transient Node<E> last; /** * Constructs an empty list. */ public LinkedList() { } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
Common methods of LinkendList
method | describe |
---|---|
void add(int index,Object element) | Inserts the specified element into this list at the specified position index. Throws IndexOutOfBoundsException if the specified index is out of bounds (index<0 or index>size()). |
boolean add(Object o)` | Appends the specified element to the end of this list. |
boolean addAll(Collection c) | Appends all elements in the specified collection to the end of this list, in the order returned by the specified collection's iterator. Throws a NullPointerException if the specified collection is null. |
boolean addAll(int index, Collection c) | Inserts all elements from the specified collection into this list, starting at the specified position. Throws a NullPointerException if the specified collection is null. |
void addFirst(Object o) | Inserts the given element at the beginning of this list. |
void addLast(Object o) | Appends the given element to the end of this list. |
void clear() | Removes all elements from this list. |
Object clone() | Returns a shallow copy of this LinkedList. |
boolean contains(Object o) | Returns true if this list contains the specified element. Returns true if and only if this list contains at least one element e, i.e., (o == null? e == null: o.equals(e)). |
Object get(int index) | Returns the element at the specified position in this list. Throws IndexOutOfBoundsException if the specified index is out of bounds (index < 0 or index> = size()). |
Object getFirst() | Returns the first element in this list. If this list is empty, a NoSuchElementException is thrown. |
Object getLast() | Returns the last element in this list. If this list is empty, a NoSuchElementException is thrown. |
int indexOf(Object o) | Returns the index in the list of the first occurrence of the specified element, or -1 if the list does not contain this element. |
int lastIndexOf(Object o) | Returns the index in the list of the last occurrence of the specified element, or -1 if the list does not contain this element. |
public ListIterator<E> listIterator(int index) | Returns a list iterator (in correct order) of the elements in this list, starting at the specified position in the list. Throws IndexOutOfBoundsException if the specified index is out of bounds (index < 0 or index> = size()). |
Object remove(int index) | Removes the element at the specified position in this list. If this list is empty, a NoSuchElementException is thrown. |
boolean remove(Object o) | Removes the first occurrence of the specified element in this list. If this list is empty, a NoSuchElementException is thrown. Throws IndexOutOfBoundsException if the specified index is out of bounds (index < 0 or index >= size()). |
Object removeFirst() | Removes and returns the first element from this list. If this list is empty, a NoSuchElementException is thrown. |
Object removeLast() | Removes and returns the last element from this list. If this list is empty, a NoSuchElementException is thrown. |
Object set(int index, Object element) | Replaces the element at the specified position in this list with the specified element. Throws IndexOutOfBoundsException if the specified index is out of bounds (index < 0 or index >= size()). |
int size() | Returns the number of elements in this list. |
Object[] toArray() | Returns an array containing all the elements in this list in the correct order. Throws NullPointerException if the specified array is null. |
Object[] toArray(Object[] a) | Returns an array containing all the elements in this list in the correct order; the runtime type of the returned array is that of the specified array. |
addAll()
public boolean addAll(int index, Collection<? extends E> c) { // Check if subscript is out of bounds checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; // The collection to be added is empty, return directly if (numNew == 0) return false; Node<E> pred, succ; // The insertion position is the same as the number of the current list, expressed as tail insertion if (index == size) { succ = null; pred = last; } else { // Find the node where index is located succ = node(index); // the previous node where index is located pred = succ.prev; } // Traverse the collection to be added and insert one by one for (Object o : a) { // Create a new node with pred as the previous node, value e, and null as the next node @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); // If pred is empty, it means inserting at the head if (pred == null) // That is to say, the newly created node is the first node first = newNode; else // pred is not empty, indicating that it is inserted in the middle or at the end // The next node of pred is connected to the newly created node pred.next = newNode; // Insert one by one pred = newNode; } // If succ is empty, it means inserting at the end if (succ == null) { // So the last element inserted is the last element last = pred; } else { // succ is not empty, indicating that it is inserted in the middle // The last inserted element is connected to the following paragraph pred.next = succ; // The first element of the following paragraph is connected to the previous paragraph succ.prev = pred; } // Quantity Consolidation size += numNew; // Modifications +1 modCount++; return true; }
Check array subscript out of bounds method
private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; }
I saw the very familiar exception IndexOutOfBoundsException, just check it according to the size of the linked list
time complexity
addAll() belongs to a shallow copy method, which traverses the elements of one set to another set through a for loop, so the time complexity is O(N)
add()
public boolean add(E e) { linkLast(e); return true; } public void add(int index, E element) { // Check whether index is out of bounds, as analyzed above checkPositionIndex(index); // The insertion position is the same as the current number, indicating that it is a tail insertion if (index == size) linkLast(element); else linkBefore(element, node(index)); } public void addFirst(E e) { linkFirst(e); } public void addLast(E e) { linkLast(e); }
It can be seen that the methods linkBefore() linkFirst() linkLast() are mainly called, so we will analyze these methods next
// Insert an element before a node void linkBefore(E e, Node<E> succ) { // assert succ != null; // Get the previous node of succ final Node<E> pred = succ.prev; // Create a new node, connect behind the previous node in succ final Node<E> newNode = new Node<>(pred, e, succ); // connect succ behind newNode succ.prev = newNode; // If the previous node of succ is empty, it means that succ is the head node if (pred == null) // Directly set newNode as the head node first = newNode; else // If the previous node of succ is not empty, it means that succ is the middle or tail node // Associate the previous node of succ to newNode pred.next = newNode; size++; modCount++; }
linkFirst() and linkLast() have similar logic, so analyze linkFirst
// Insert an element into the head node private void linkFirst(E e) { final Node<E> f = first; // current first node // A new node is created, with null as the previous node, e as the value, and the current first node as the next node final Node<E> newNode = new Node<>(null, e, f); first = newNode; // Set the newly created node as the first node if (f == null) // The current first node is empty, indicating that the list is empty last = newNode; // So the last node is the currently inserted node else // The current first node is not empty, indicating that the list is not empty f.prev = newNode; // The node inserted on the connection at the head of the current list size++; modCount++; }
time complexity
The add() method has three ways of adding, head insertion, tail insertion, middle insertion, head insertion and tail time complexity being O(1), because the previous node does not need to be found through traversal, but time complexity is O(N), because you need to call node(int index) to find the element corresponding to the subscript, and then insert after it
get()
public E get(int index) { // Check whether index is out of bounds, as analyzed above checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // If index is less than half of size, search from the beginning if (index < (size >> 1)) { Node<E> x = first; // Find from the beginning until i == index for (int i = 0; i < index; i++) x = x.next; return x; } else { // If index is greater than half of size, search from the end Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
getFirst() and getLast()
public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
time complexity
The time complexity of the get() method is also described separately, because the LinkendList implementation holds the head and tail elements, so it can be obtained directly, and time complexity is O(1), but if it is obtained from the subscript, then the element corresponding to the subscript must be retrieved through traversal, and time complexity is O(N)
remove()
public E remove(int index) { // Check if index is out of bounds checkElementIndex(index); return unlink(node(index)); } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); }
It can be seen that the remove() method is similar to the add() method, and it also calls unlink() unlinkFirst() unlinkLast() respectively, which means to delete a node, delete the head node, and delete the tail node.
E unlink(Node<E> x) { // assert x != null; // Get the element of the current node final E element = x.item; // get to the next node final Node<E> next = x.next; // get the previous node final Node<E> prev = x.prev; // If the previous node of the current node is empty, it is the head node if (prev == null) { // Just set the next node as the first node first = next; } else { // Not empty, indicating that it is an intermediate node or a tail node // Connect the previous node to the next node prev.next = next; x.prev = null; } if (next == null) { // If the next node of the current node is empty, it means the tail node // The tail node is removed, so make the previous node the tail node last = prev; } else { // Not empty, indicating that it is an intermediate node // Connect the previous node to the next node next.prev = prev; // The current node disconnects from the next node x.next = null; } // The current node element is set to be empty, which is convenient for GC x.item = null; size--; // Modifications +1 modCount++; return element; }
private E unlinkFirst(Node<E> f) { // assert f == first && f != null; // Get the element of the current node final E element = f.item; // Get the next element of the current node final Node<E> next = f.next; f.item = null; f.next = null; // help GC // Set the next node of the current node as the head node first = next; // If the next node is empty, the linked list has only one node if (next == null) // clear tail node last = null; else // Otherwise, there are other nodes // The next node is already set as the head node // So clear the association with the previous node next.prev = null; size--; // quantity: 1 modCount++; return element; }
private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; }
time complexity
Deleted time complexity is O(1), find the precursor and successor nodes that need to be deleted directly, then point the pointer of the precursor node of the deleted element to the succeeding node, because it is a two-way Chain table, so you can directly manipulate the precursor node if it's not a singly linked list
clear()
public void clear() { // Iterate over and set all to be empty for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }
time complexity
It is not difficult to see from the implementation of the code that the time complexity of the clear() method is O(N), because it traverses and then empties the elements in turn, so the time complexity is O(N)
More methods can be viewed https://www.runoob.com/manual/jdk11api/java.base/java/util/LinkedList.html
summary
LinkendList is a linear structure from the physical structure, and a chain storage structure from the logical structure. Although it is a linear structure, it is not stored in a linear order, but is stored scattered in memory. It establishes the connection between nodes through pointers, and implements Deque, which also indicates that it is a two-way Chain table. In the source code, it does not see how it handles thread security issues. So it's also a thread-insecure chain table, and you don't see null elements that aren't allowed to be inserted or duplicated, so it's a chain table that allows duplicate elements as well as null elements.