1.LinkedList data structure

1.1 Data Structure

The underlying data structure of LinkedList is a bidirectional LinkedList, as shown in the figure below:

Matters needing attention:
  • Each Node in the list is called Node, and Node has a prev attribute, which represents the position of the previous Node, and a next attribute, which represents the position of the next Node
  • First is the head node of a bidirectional list, and its preceding node is NULL.
  • Last is the last node of the bidirectional list, and its next node is NULL;
  • When there is no data in the linked list, first and last are the same node, both pointing to null;
  • Because it’s a two-way list, there’s no size limit.

1.2 the Node

private static class Node<E> { E item; // Node<E> next; // The next Node to point to Node<E> prev; Node(Node<E> prev, E element, Node<E> next) {this.item = element; this.next = next; this.prev = prev; }}Copy the code

Source code analysis

2.1 LinkedList class annotation parsing

  • Use “bidirectional linked List” to implement List and Deque interface. Implements all the methods in the List interface and allows storing all elements, including Null.
  • All operations can be done via a two-way linked list. Approach the element to be manipulated by traversing the collection from the beginning or end.
  • It is recommended to use the thread safe Collections#synchronizedList class for multiple threads
  • Enhance the for loop, or use iterators that will fail quickly if the array size changes, throwing an exception.

2.2 new

Source code analysis:

When a new node is added, we can choose whether to append it to the head of the list or to the end of the list. By default, the add method starts at the end of the list

Method appends from the header:

Add:
Public Boolean add(E E) {linkLast(E); return true; }Copy the code
To add from the tail:
Void linkLast(E E) {final Node<E> l = last; // Create a new node and initialize the input parameter. Final Node< e > newNode = newNode <>(l, e, null) final Node< e > newNode = newNode <>(L, e, null); // append the newNode to the end. If (l == null) first = newNode; // If (l == null) first = newNode; Else // Otherwise, the next node of the first and last node points to the current last node. l.next = newNode; // size and version changes to size++; modCount++; }Copy the code
Increase from the head:
Private void linkFirst(E E) {// Final Node<E> f = first; // Create a new node and initialize the input parameter. Final Node<E> newNode = newNode <>(null, E, f) final Node<E> newNode = newNode <>(null, E, f); // append the newNode to the header first = newNode; If (f == null) last = newNode; if (f == null) last = newNode; F.rev = newNode; else f.rev = newNode; size++; modCount++; }Copy the code

Matters needing attention:

  • There is little difference between the header append node and the tail append node, except that the former is the prev pointer of the moving head node and the latter is the next pointer of the moving tail node.

2.3 Deleting Implementation

Source code analysis:

Delete LinkedList nodes in a similar way to append. We can delete the LinkedList node from the header or from the tail

Set all nodes to NULL.

Delete from header:
Final E element = f.tem; private E unlinkFirst(Node<E> f) {final E element = f.tem; Final Node<E> next = f.next; final Node<E> next = f.next; // help GC recover header f.tem = null; f.next = null; // First = next; If (next == null) last = null; Else // The list is not empty, the first node of the head node points to null next.prev = null; // Change the list size and version size--; modCount++; return element; }Copy the code
Delete from the tail:
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; }Copy the code

Matters needing attention:

  • Both the front and back pointing nodes are set to NULL to help GC recycle;
  • From the source code, we can know that the node addition and deletion of the LinkedList structure only modify the point of the nodes before and after, so the addition and deletion of LinkedList are fast.

2.4 Implementing The Query

Query:
*/ Node<E> Node (int index) {// If index is in the first half of the queue, start from the beginning. Size >> 1 = size divided by 2. if (index < (size >> 1)) { Node<E> x = first; // stop for (int I = 0; i < index; i++) x = x.next; return x; } else {// If index is at the bottom of the queue, start from the end to find Node<E> x = last; // stop for (int I = size-1; i > index; i--) x = x.prev; return x; }}Copy the code
Matters needing attention:

Instead of looping from beginning to end, LinkedList uses a dichotomy to see if the index is in the first or second half of the list. If it’s the first half, start from the beginning, and vice versa. In this way, the number of loops is reduced by at least half and lookup performance is improved.

Time complexity

O(1) add(index, E) adds the number of elements to the end. After adding the number of elements, we need to find the number of elements, and direct pointer to the operation. Remove () removes elements, direct pointer operations, O(1)

Four. Thread safety

4.1 Thread safety issues

There are thread-safety issues only when LinkedList is a shared variable, and there are no thread-safety issues when LinkedList is a local variable within a method.

The reason why LinkedList is thread-safe is because of the size of LinkedList, the fact that modConut does not lock the variables, and the variable type is not volatile, so if multiple threads operate on these variables, There may be cases where values are overwritten.

SynchronizedList (Collections#synchronizedList); Collections#synchronizedList (lock);

public boolean add(E e) {
    synchronized (mutex) {return c.add(e);}
}

Copy the code

We can also use ConcurrentLinkedQueue to keep threads safe,

In live.

The bottom of LinkedList is a LinkedList structure, suitable for the scene that is often added and deleted, welcome to pay attention to the public number: the future is light, get a line of large factory Java interview topic summary + knowledge learning thinking guide + a 300 page PDF document Java core knowledge summary! These are some of the things that the interviewer should ask during the interview. These include basics, Java collections, JVMS, multi-threaded concurrency, Spring principles, microservices, Netty and RPC, Kafka, diaries, design patterns, Java algorithms, databases, Zookeeper, distributed caching, data structures, and more.