Chain storage structure for linear lists
Java data structure source exploration (a) – ArrayList
N nodes (storage image of A1) are linked into a linked list, that is, a linear list (A1, A2… , an), because each node of the linked list contains only one pointer field, so it is called a single linked list. A singly linked list is simply a linear list of data elements linked together in their logical order through the pointer field of each node.
Node: data field + pointer field
Header: A header is set up for unity and convenience. It is placed before the node of the first element and its data field is generally meaningless. With a header, the operation of inserting and deleting the first element before the first element is the same as that of other nodes. The header is not necessarily a necessary element of the list.
Header pointer: a pointer to the first node in the list, or to the first node if the list has a header. The header pointer has the function of identification. The header pointer is usually preceded by the name of the linked list. Whether the list is empty or not, the head pointer is not empty. A header pointer is a necessary element of a linked list.
Java LinkedList definition – a two-way LinkedList
Bidirectional linked list Java definition
/** * Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null). * */
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable.java.io.Serializable
{
transient int size = 0;
/** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item ! = null) */
transient Node<E> first;
/** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item ! = null) */
transient Node<E> last;
/** * Constructs an empty list. */
public LinkedList(a) {}/**
* Node 数据结构
*/
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; }}Copy the codeLinkedList CRUD
/** * the list gets */
public E get(int index) {
// Check for index transgressions
checkElementIndex(index);
return node(index).item;
}
/** * add */ to the list
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
/ / end nodes
linkLast(element);
else
// List insertion
linkBefore(element, node(index));
}
/** ** delete */
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/** * Returns the (non-null) Node at the specified element index. */
Node<E> node(int index) {
// assert isElementIndex(index);
// start traversal from the beginning
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// Start traversal at the end
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}/** * 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++;
}
/** * Inserts element e before non-null Node succ. */
void linkBefore(E e, Node<E> succ) {
// assert succ ! = null;
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++;
}
Copy the codeLinkedList whole table created and deleted
The whole table creation
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the specified
* collection's iterator. The behavior of this operation is undefined if
* the specified collection is modified while the operation is in
* progress. (Note that this will occur if the specified collection is
* this list, and it's nonempty.)
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
/** * Inserts all of the elements in the specified collection into this * list, starting at the specified position. Shifts the element * currently at that position (if any) and any subsequent elements to * the right (increases their indices). The new elements will appear * in the list in the order that they are returned by the * specified collection's iterator. * *@param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
// Whether the index inserted is within the bounds of the list
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0) return false;
/ / initialization
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
Copy the codeThe whole table delete
It is worth noting that full list deletion is unnecessary to traverse the entire list to empty. The fundamental purpose is to free references to objects to aid the GC in garbage collection.
/** * Removes all of the elements from this list. * The list will be empty after this call returns. */
public void clear(a) {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
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++;
}
Copy the codeA comparison of linked list structures with sequential storage structures
storage
An ArrayList stores the data elements of a linear list in a sequence of contiguous storage cells
LinkedList uses a chained storage structure, with an arbitrary set of storage cells for the elements of a linear list.
Time performance
To find the
ArrayList O(1)
LinkedList O(n)
Insert and delete
An ArrayList needs to move an element half the length of the table on average.
LinkedList inserts and deletes only O(1) after finding a pointer to a location.
Space performance
ArrayList requires pre-allocation of storage space, and dynamic expansion reduces performance.
LinkedList requires no storage allocation and has an unlimited number of elements.
conclusion
ArrayList is suitable for scenarios that require frequent lookups and few inserts and deletions. Use LinkedList when frequent inserts and deletions are required.
It is best to use LinkedList when the number of elements in a linear table varies greatly or is unknown at all. If you know the length in advance, use ArrayList.