LinkedList The bottom layer is based on linked list , Adding or deleting does not require moving data , So it's very efficient . But the efficiency of querying and modifying data is low , You can't quickly locate the data according to the subscript like an array , You need to traverse the data one by one .
The basic structure
LinkedList It is a structure based on linked list , The main core is Node node , Source code is as follows ：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
The structure is shown in the following figure ：
This is a double linked list structure , Yes prev Leading pointer and next Post pointer .
And the first node first、 Tail node last、 length size:
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
Add data
LinkedList There are two ways to add elements ：add(E e) and add(int index,E e).
- add(E e) Add data at the end of the linked list
- add(int index,E e) Add data at the specified linked list location
add(E e)
add Method is called linkLast Method :
public boolean add(E e) {
linkLast(e);
return true;
}
linkLast Indicates that the specified element is added at the end of the linked list ：
void linkLast(E e) {
// Record the original tail node
final Node<E> l = last;
// Create a new node , The front node of the new node is the original tail node
final Node<E> newNode = new Node<>(l, e, null);
// Update tail node
last = newNode;
if (l == null)
// The tail node is empty , Update the header node
first = newNode;
else
// The tail is not empty , The original trailing node is the new node
l.next = newNode;
// size and modCount Self increasing
size++;
modCount++;
}
- Record the original tail node l
- Create a new node , The front node points to the original tail node .
- If l It's empty , Update the header node
- Update tail node
- If l Not empty ,l The post pointer to the new node
If the original tail node is empty , Create a node directly , This node is last and first node .
If the original tail node is not empty , Create a new node , The front of the new node points to the original last, The original last Of next Point to a new node .
addAdd data at the end of the chain , Add front and back pointers . And updated tolastnode .
add(int index,E e)
This method is to add elements to the specified position of the linked list , The subscript of the linked list is the same as that of the array , Also from the 0 From the beginning :
Have a look first add(int index, E element) Method
public void add(int index, E element) {
// Check if the subscript is out of range
checkPositionIndex(index);
if (index == size)
// The subscript is equal to size, Add directly to the end of the list
linkLast(element);
else
//
linkBefore(element, node(index));
}
checkPositionIndex Determine if the subscript is out of bounds ,index >= 0 && index <= size index Whether in 0 ~ size Within limits .
If index be equal to size, and add(E e) Same operation , Are added at the end of the linked list .
If index Less than size, call linkBefore Method , Insert a node into the middle of the linked list . First of all to see node Method ：
Node<E> node(int index) {
// assert isElementIndex(index);
// size >> 1 Express size Moves to the right one , Namely size/2 size Half of
// index Less than size Half of , Traverse back from the first node
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
// index Greater than size Half of , Traverse forward from the last node
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
node() The way is to find index Corresponding node node .
For example, a length of 5 The linked list of :
node(1) from first node （ The first 0 Nodes ） Go back through one , That is to say 1 Corresponding node .node(3) from last node （ The first 4 Nodes ） Go ahead and traverse a , That is to say 3 Corresponding node .
Find the node by subscript , The linked list generally needs to be traversed , You need to traverse half of the linked list at most , It mainly uses the characteristics of double linked list , You can traverse from front to back , You can traverse from back to front .
size>>1 Express size/2, Judge index Is it in the first half or the second half of the linked list , If you traverse back from the first node in the first half , If you traverse forward from the last node in the second half ,, This traverses at most size Half of , Avoid traversing the entire linked list . find index After the node under , Look again linkedBefore Method :
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// Record the front node pred
final Node<E> pred = succ.prev;
// Create a new node , New nodes pre Point to pred,next Point to succ node
final Node<E> newNode = new Node<>(pred, e, succ);
// succ pre Point to a new node
succ.prev = newNode;
// If pred It's empty , Express succ It's the first node , The new node is assigned to the first node
if (pred == null)
first = newNode;
else
// pred Of next Point to a new node
pred.next = newNode;
size++;
modCount++;
}
- Record
succThe front node of the nodepred. - The new node ,
prePoint topred,nextPoint tosucc. succOfprePoint to a new node .- If
predby null, Indicates that the first node issucc, Assign a node tofirstnode . - If
predNot for null,predOfnextPoint to a new node .
For example, a length of 5 The linked list of , The subscript for 1 Add data to the location of ：
get data
Data acquisition mainly includes get、getFirst、getLast.
get The method is mainly through node Method subscript node , Get the item data .
getFirst Method to get Head node Of item.
getLast Method to get Tail node Of item.
Delete data
remove(Object o)
Remove the first matching element from the list
public boolean remove(Object o) {
// Judge whether it is null
if (o == null) {
// Traverse node
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// Traverse node
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
Deletes the specified element , You need to determine whether the element is null.
- If
null, Just usex.item == nullSentence judgment . - If not for
null, Just useo.equals(x.item)Sentence judgment .
Then call unlink Method ：
E unlink(Node<E> x) {
// assert x != null;
// Record nodes element、next and prev
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// prev by null,next Assign to the first node
if (prev == null) {
first = next;
} else {
// prev Of next Point to next node
prev.next = next;
// x node prev Set as null
x.prev = null;
}
// next by null,prev Assign as tail node
if (next == null) {
last = prev;
} else {
// next Of prev Point to prev
next.prev = prev;
// x node next Set as null
x.next = null;
}
// x.item Set as null
x.item = null;
// The length decreases
size--;
modCount++;
return element;
}
Pictured , To delete 1 Data node ：
remove(int index)
Delete the data of the specified subscript ：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
First, through node Find the node corresponding to the subscript , Call again unlink Delete the data .
summary
LinkedListIs a double linked list data format , To support the double linked list structure , Headed node , Tail node and size size .add(E e)Add directly to the end of the queue , New node prev Point to the tail node , The tail node points to the new node .add(int index,E e)If the adding position is equal to the length of the linked list , Add data directly at the end of the linked list . Otherwise, add data to the linked list .- To add data to a linked list, you must first go through
nodeMethod to get data ,nodeClever judgmentindexandsizeA half length relationship , If it is less than, it will traverse from front to back , Greater than is traversed from back to front . No need to traverse the entire linked list . - After finding the node , Record node's
prevnode , stayprevCreate new nodes between and nodes .
- To add data to a linked list, you must first go through
remove(Object o), Traverse to find the element , Call againunlinkMethod . The front node of the record elementprevAnd post nodesnext, Front nodenextPoint to the post node , Post node next Point to the front node , Delete the pointers of other pre and post nodes .remove（int index）, Through the firstnodeMethod to find the subscript data , After finding the element , Call againunlinkMethod .
If the article is good , Give me some advice. ！
