LinkedList is introduced
The LinkedList implementation of the interface. Implement all optional list operations and allow all elements (including NULL). In addition to implementing the List interface, the LinkedList class provides a uniform naming method for get, remove, and INSERT elements at the beginning and end of a List. These operations allow linked lists to be used as stacks, queues, or double-ended queues.
LinkedList,
The characteristics of the LinkedList
- Orderliness Stores and reads in the same order
- Elements can be repeated
- Contains indexed methods
- Unique features: the data structure is linked list, can be used as a stack, queue or double – ended queue!
LnkedList is a bidirectional linked list structure. The bidirectional linked list structure is as follows
Data structure details
Linkedlist is a Linkedlist source as follows:
public class LinkedList<E>{
transient int size = 0;
// The header of the bidirectional list
transient Node<E> first;
// The last node of the bidirectional list
transient Node<E> last;
// Node class
private static class Node<E> {
// Data elements
E item;
// The next node of the node
Node<E> next;
// The last node of the node
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the codeLinkedList is a two-way LinkedList, which is a Node class in the code. There’s no array structure inside. A bidirectional list must have a head node and a tail node. The Node class, which is an inner class, is present in the LinkedList. Each Node class has two member variables:
- Prev: a node on the current node. The previous node on the head node is null
- Next: the next node of the current node, and the next node of the tail node is null
Linked list data structure features: query slow, add and delete fast!
- The basic structure of linked list data structure is a node. In each node class, there is a node prev and the next node next
- The LinkedList must have at least two nodes, first and last. If the LinkedList has no data, both first and last are null
The data structure of LinkedList is slow to query and fast to add and delete.
Deleting is similar to inserting. For example, if you delete B, look up the previous node A and the next node C of node B, and then point the next node of node A to C, empty the previous node of node B and point the previous node of node C to A, empty the next node of node B, Finally, the data in the B node is set to empty. The slow query is the need to look back one node at a time to find the node you want. The greater the amount of data, the lower the efficiency
Add elements
public boolean add(E e) {
// Join to the end of the list
linkLast(e);
return true;
}
// Connect to the last node
void linkLast(E e) {
// Assign the trailing node to l
final Node<E> l = last;
// Create a new node whose last node is L, whose data is e, and whose next node is null.
final Node<E> newNode = new Node<>(l, e, null);
// Use the current node as the end node
last = newNode;
// Check whether the l node is null
if (l == null)
// the end node is also the head node
first = newNode;
else
// The next node of the previous end node is set to the newly added node
l.next = newNode;
// The number of elements in the current collection +1
size++;
// Set of operations +1. The modCount property is to modify the counter
modCount++;
}
Copy the codeAdds an element to the list at the specified location
public void add(int index, E element) {
// Check whether the index bit meets the requirement
checkPositionIndex(index);
// Determine if index is equal to the number of elements, if so, the last element
if (index == size)
linkLast(element);
else
// Connect after the specified node
linkBefore(element, node(index));
}
//// query linked list nodes by index!
Node<E> node(int index) {
// Check whether the index is less than 1/2 of the number of stored elements
if (index < (size >> 1)) {
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;
returnx; }}// Appends the current element before the specified node
void linkBefore(E e, Node<E> succ) {
// Fetch the previous node of the succ node
final Node<E> pred = succ.prev;
// Create element node: previous node, current element, next node
// The last node of the element is pred and the next node is succ
final Node<E> newNode = new Node<>(pred, e, succ);
// Reassign the previous node of succ to the new node
succ.prev = newNode;
// Check whether the last node of succ is null, if null, succ is the header node
if (pred == null)
// When the newly created node is used as the header node
first = newNode;
else
// Reassign the next node of the previous node of succ to the newly created node
pred.next = newNode;
size++;
modCount++;
}
Copy the codeDelete the specified element
public E remove(int index) {
checkElementIndex(index);
// Delete element node,
//node(index) Finds the node to be deleted based on the index
//unlink() deletes a node
return unlink(node(index));
}
// Delete a specified node
E unlink(Node<E> x) {
// Get the element from the node to be deleted
final E element = x.item;
// Get the next node of the node to be deleted
final Node<E> next = x.next;
// Get the next node of the node to be deleted
final Node<E> prev = x.prev;
if (prev == null) {
// If null, the node to be deleted is the header node
first = next;
} else {
// The next node of the previous node is changed to the next node of the node to be deleted
prev.next = next;
// The last node of the node to be deleted is empty
x.prev = null;
}
if (next == null) {
// If null, the node to be deleted is the tail node
last = prev;
} else {
// Change the upper node of the next node to be deleted to the upper node of the node to be deleted
next.prev = prev;
// The last node to delete is empty
x.next = null;
}
// Delete the element in the node to be deleted
x.item = null;
size--;
modCount++;
return element;
}
Copy the codeLook for the element
public E get(int index) {
// Verify that the node exists
checkElementIndex(index);
//node(index) Obtains the node
return node(index).item;
}
Copy the codeThe node(index) index is used to compare the nodes (not all nodes, but half of all nodes).