summary
_ LinkedList_ At the same time, it realizes_ List_ Interface and_ Deque_ Interface, that is, it can be regarded as a sequential container, a queue, and a stack Therefore, when you need to use queue or stack structure, you can consider using LinkedList
The implementation of LinkedList determines that all operations related to subscripts are linear time, while operations at the first or end are constant time
Because the LinkedList does not achieve synchronization, the direct use of multi-threaded access may cause thread insecurity. The solution is to use collections when defining the LinkedList Wrap it with synchronizedlist()
List list=Collections.synchronizedList(new LinkedList(...));
characteristic
- LinkedList is based on linked list
- Is thread unsafe
- LinkedList can be operated as a stack, queue, or double ended queue.
- LinkedList implements the List interface, so you can queue it.
- LinkedList implements the Deque interface and can use LinkedList as a double ended queue.
- LinkedList implements the clonable interface, that is, it overrides the function clone(), which can be cloned.
- LinkedList implements Java io. Serializable interface, so LinkedList supports serialization,
internal structure
The underlying LinkedList is implemented through a two-way linked list. Each Node is represented by an internal class Node. Internally, it points to the chain header and tail respectively through the first and last pointers. There are no empty head and tail nodes inside. That is, when the LinkedList is empty, the above two pointers point to null
private static class Node<E> {
E item; //Current node value
Node<E> next; //Precursor node
Node<E> prev; //Successor node
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Internal source code
Construction method
1. Empty constructor
/**
* Constructs an empty list.
*/
public LinkedList() {
}
2. Use set to construct 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);
}
Insertion method
add(E e)
Add elements to the end of the linked list
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e); //Connect to end of list
return true;
}
/**
* Links e as first element.
*/
void linkLast(E e) {
final Node<E> l = last; //Temporary storage of old tail
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode; //The next pointer in the old tail points to the new tail
size++;
modCount++;
}
add(**int **index, E element)
Insert the element at the index position
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index); //Check whether the index is between [0-size]
if (index == size) //Subscript equal to size proves that it needs to be inserted into the tail
linkLast(element);
else
linkBefore(element, node(index)); Not equal to, insert into the specified node
}
Call linkBefore(element, node(index)) when it is not equal to; Insert the element before the index element (after insertion, the element becomes the index element)
void linkBefore(E e, Node<E> succ) {
// assert succ != null; succ is calculated from the node(index) method, so the assertion is not empty
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
node(index) finds the node with index as the subscript
/**
* Returns the (non-null) Node at the specified element index.
Return a node and ensure it is not null
*/
Node<E> node(int index) {
// assert isElementIndex(index); // It was verified before calling, so it was asserted that there was an index element
if (index < (size >> 1)) {//Because the subscript operation of the linked list is linear time, the binary search subscript is used to reduce the time complexity
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
addAll(collection c)
Insert collection into the tail of linked list
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
Call addAll(int index,collection c) to insert the collection into the specified location. The passed in parameter is size, so the collection is inserted into the tail
public boolean addAll(int index, Collection<? extends E> c) {
//1: Check whether the index range is within size
checkPositionIndex(index);
//2: The toArray () method stores the data of the collection into an object array
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//3: Get the precursor node and successor node of the insertion position
Node<E> pred, succ;
//If the insertion position is the tail, the predecessor node is last and the successor node is null
if (index == size) {
succ = null;
pred = last;
}
//Otherwise, call the node() method to get the successor node and then the predecessor node
else {
succ = node(index);
pred = succ.prev;
}
// 4: Traverse data insert data
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//Create a new node
Node<E> newNode = new Node<>(pred, e, null);
//If the insertion position is at the head of the linked list
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//If the insertion position is at the end, reset the last node
if (succ == null) {
last = pred;
}
//Otherwise, connect the inserted linked list with the previous linked list
else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
The implementation of addAll(int index,collection e) can be roughly divided into four steps
1. Verify the validity of parameters
2. Use the toarray method to convert the elements in the collection into arrays
3. Obtain the predecessor and successor node of the position to be inserted (the successor of the previous node and the predecessor of the next node)
4. Traverse the array and insert the element into the above two pointers
Addfirst (e e e) and addlast (e e e)
/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
public void addLast(E e) {
linkLast(e);
}
Both call linklast (E) respectively; linkFirst(e);
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
The execution method is similar to linkBefore
Delete method
Remove(), removefirst(), pop(): deletes the header node
public E pop() {
return removeFirst();
}
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC has no application about this node, and the memory will be recycled by GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
remove() implements the ListIterator interface, while removeFirst(),pop() implements the Depue interface
removeLast(),pollLast(): deletes the tail node
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* Retrieves and removes the last element of this list,
* or returns {@code null} if this list is empty.
*
* @return the last element of this list, or {@code null} if
* this list is empty
* @since 1.6
*/
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
The difference is that removeLast() will throw an exception after the deletion fails, while pollLast() will return null
Delete the specified element remove(Object o)
public boolean remove(Object o) {
//If the deleted object is null
if (o == null) {
//Traverse from scratch
for (Node<E> x = first; x != null; x = x.next) {
//Find element
if (x.item == null) {
//Remove the found element from the linked list
unlink(x);
return true;
}
}
} else {
//Traverse from scratch
for (Node<E> x = first; x != null; x = x.next) {
//Find element
if (o.equals(x.item)) {
//Remove the found element from the linked list
unlink(x);
return true;
}
}
}
return false;
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) { //If null
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) { //Find the element and use the equal sign to judge (there will be null pointer exception when calling equals)
unlink(x);
return true;
}
}
} else { //Not null
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) { //Find the element and judge by equals
unlink(x);
return true;
}
}
}
return false;
}
Calling this method will delete only one node (the first node matched during traversal), not all matching nodes
Search method
Find elements by subscript
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//Check the validity of parameters
checkElementIndex(index);
call node()Method acquisition item
return node(index).item;
}
node(index) finds the node with index as the subscript
/**
* Returns the (non-null) Node at the specified element index.
Return a node and ensure that it is not null
*/
Node<E> node(int index) {
// assert isElementIndex(index); // It is verified before calling, so it is asserted that there is an index element
if (index < (size >> 1)) {//Because the subscript operation of the linked list is linear time, the binary search subscript is used to reduce the time complexity
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Find subscripts by element
Ab initio traversal: indexOf(Object o),
Traverse lastIndexOf(Object o) from the tail
Still distinguish whether the parameter is null. If it is null, use = = to judge, and if not, use equals() to judge
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the last occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
contains(Object o):
Check whether the object o exists in the linked list
/**
* Returns {@code true} if this list contains the specified element.
* More formally, returns {@code true} if and only if this list contains
* at least one element {@code e} such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}