This series of articles have been supplemented and improved, and has been revised and organized into a book, The Logic of Java Programming (written by Ma Junchang), published by Huazhang Branch of China Machine Press, which was on the market in January 2018 and received high praise from readers. Major online shops and bookstores are available for sale, welcome to buy: JINGdong self-run link

In the last section, we introduced ArrayList, which has high random access efficiency but low insert and delete performance. We mentioned LinkedList, which also implements the List interface, and its characteristics are almost exactly the opposite of ArrayList. In this section, we will introduce LinkedList in detail.

In addition to implementing the List interface, LinkedList also implements the Deque and Queue interface, which can operate as queues, stacks, and double-ended queues. This section describes these usages and their implementation principles.

Let’s see how it’s used first.

usage

A constructor

The LinkedList constructor is similar to ArrayList in that there are two, one is the default constructor and the other can accept an existing Collection, as shown below:

public LinkedList(a)
public LinkedList(Collection<? extends E> c)
Copy the code

For example, you could create it like this:

List<String> list = new LinkedList<>();
List<String> list2 = new LinkedList<>(
        Arrays.asList(new String[]{"a"."b"."c"}));
Copy the code

The List interface

Like ArrayList, LinkedList implements the List interface, which extends the Collection interface, which extends the Iterable interface. All of these interface methods are available in the same way as in the previous section. I won’t go into that in this section.

Queue (Queue)

LinkedList also implements the Queue interface, which is similar to queues in daily life, characterized by first in, first out, adding elements to the tail and removing elements from the head. Its interface is defined as:

public interface Queue<E> extends Collection<E> {
    boolean add(E e);
    boolean offer(E e);
    E remove(a);
    E poll(a);
    E element(a);
    E peek(a);
} 
Copy the code

Queue extends Collection and has three main operations:

  • Add elements at the end (Add, offer)
  • Look at the header element (Element, peek) and return the header element without changing the queue
  • Remove the header element (remove, poll), return the header element, and remove it from the queue

Every operation has two forms. What’s the difference? The difference is that special cases are treated differently. The special case is that the queue is empty or the queue is full. Empty is easy to understand. Full means that the queue has a length limit and is already full. The implementation of LinkedList has no limit on Queue length, but other implementations may.

When the queue is empty, Element and Remove throw NoSuchElementException, peek and poll return the special value null, and add throws IllegalStateException when the queue is full. Offer simply returns false.

It is also easy to use a LinkedList as a Queue, for example:

Queue<String> queue = new LinkedList<>();

queue.offer("a");
queue.offer("b");
queue.offer("c");

while(queue.peek()! =null){
    System.out.println(queue.poll());    
}
Copy the code

The output is:

a
b
c
Copy the code

The stack

We have introduced the stack when we introduced the principle of function call. The stack is also a common data structure. In contrast to the queue, it has the characteristics of advanced back out, back in first out, similar to a storage box, when you put things up, you can only take from the top.

Java has a Stack class that represents a Stack, but this class is obsolete and will not be introduced. There is no separate Stack interface in Java. Stack-related methods are included in the interface Deque that represents a double-ended queue.

void push(E e);
E pop(a);
E peek(a);
Copy the code

Explain:

  • Push means pushing, adding elements to the header. The stack may be limited in space, and if it is full, push will throw an IllegalStateException.
  • Pop means out of the stack, returns the header element, and removes it from the stack, throwing NoSuchElementException if the stack is empty.
  • Peek looks at the stack header element, does not modify the stack, and returns null if the stack is empty.

It is also easy to use LinkedList as a stack, for example:

Deque<String> stack = new LinkedList<>();

stack.push("a");
stack.push("b");
stack.push("c");

while(stack.peek()! =null){
    System.out.println(stack.pop());    
}
Copy the code

The output is:

c
b
a
Copy the code

Double-ended queue (Deque)

Both stacks and queues operate on both ends. The stack operates only on the head, and both ends of the Queue operate, but tails only add and heads only view and delete. There is a more general interface to both ends of the Queue, Deque, which extends the Queue to include stack operations.

void addFirst(E e);
void addLast(E e);
E getFirst(a);
E getLast(a);
boolean offerFirst(E e);
boolean offerLast(E e);
E peekFirst(a);
E peekLast(a);
E pollFirst(a);
E pollLast(a);
E removeFirst(a);
E removeLast(a);
Copy the code

XxxFirst operation head, xxxLast operation tail. Similar to queues, each operation has two forms, with the difference being handled differently when the queue is empty or full. If no, getXXX/removeXXX throws an exception, and peekXXX/pollXXX returns NULL. When the queue is full, addXXX throws an exception; offerXXX simply returns false.

Stacks and queues are just special cases of double-endian queues, and their methods can be replaced by the methods of double-endian queues, though it is conceptually clearer to use different names and methods.

The Deque interface also has an iterator method that iterates backwards

Iterator<E> descendingIterator(a);
Copy the code

For example, look at the following code:

Deque<String> deque = new LinkedList<>(
        Arrays.asList(new String[]{"a"."b"."c"}));
Iterator<String> it = deque.descendingIterator();
while(it.hasNext()){
    System.out.print(it.next()+"");
}
Copy the code

The output is

c b a 
Copy the code

Usage summary

The usage of LinkedList is relatively simple, similar to the usage of ArrayList, with support for List interface. However, LinkedList has added an interface Deque, which can be regarded as queue, stack, and double-ended queue for convenient operation on both sides.

If it’s just a List, should I use ArrayList or LinkedList? We need to understand how LinkedList works.

Realize the principle of

An internal

We know that an ArrayList is an array inside, and the elements are contiguous in memory, but a LinkedList is not. LinkedList is literally a LinkedList. To be exact, its internal implementation is a two-way LinkedList. Each element is stored separately in memory, and the elements are linked together by links, like children holding hands with each other.

To represent link relations, we need the concept of a node, which includes the actual element but also has two links pointing to the previous node (precursor) and the next node (successor). A node is an inner class, specifically defined as:

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 code

The Node class represents nodes, item points to the actual element, next to the next Node, and prev to the previous Node.

LinkedList consists of the following three instance variables:

transient int size = 0;
transient Node<E> first;
transient Node<E> last;
Copy the code

Size represents the length of the list, default is 0, first refers to the head node, last refers to the tail node, and initial values are null.

All public methods of LinkedList operate internally on these three instance variables. How does this work? How are link relationships maintained? Let’s take a look at some of the main methods, starting with the Add method.

The Add method

The code for the add method is:

public boolean add(E e) {
    linkLast(e);
    return true;
}
Copy the code

LinkLast is called, and its code is:

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++;
}
Copy the code

The basic steps of the code are:

  1. Create a newNode, newNode. Prev points to the original tail node, or null if the original list was empty. The code is:
Node<E> newNode = new Node<>(l, e, null);
Copy the code
  1. Modify last node to point to the new last node newNode. The code is:
last = newNode;
Copy the code
  1. Modify the back link of the previous node so that the head node points to the new node if the original list is empty, otherwise the next of the previous node points to the new node. The code is:
if (l == null)
    first = newNode;
else
    l.next = newNode;
Copy the code
  1. Increase the list size. The code is:
size++
Copy the code

ModCount++ serves the same purpose as ArrayList, recording the number of changes to facilitate detection of structural changes in the middle of an iteration.

Let’s use some diagrams to see it more clearly. For example, the code is:

List<String> list = new LinkedList<String>();
list.add("a");
list.add("b");
Copy the code

After executing the first line, the internal structure looks like this:

After adding “b”, the internal structure is as follows:

Access the element GET based on the index

If the element is added, what if the element is accessed by index? Let’s look at the code for the get method:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Copy the code

CheckElementIndex checks the validity of the index location and throws an exception if not, with code like this:

private void checkElementIndex(int index) {
    if(! isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}
Copy the code

If index is valid, then the node method is called to find the corresponding node, whose item attribute points to the actual element content. The node method code reads:

Node<E> node(int index) {
    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; }}Copy the code

Size >>1 = size/2 (index<(size>>1)); size>>1 = size/2 (index<(size>>1));

Unlike ArrayList, where array elements are stored consecutively and can be accessed randomly, LinkedList has to follow links from beginning to end, which is inefficient.

Find elements by content

Let’s look at the code for indexOf:

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)
                returnindex; index++; }}else {
        for(Node<E> x = first; x ! =null; x = x.next) {
            if (o.equals(x.item))
                returnindex; index++; }}return -1;
}
Copy the code

The code is simple: follow the link back to the original node. If null is desired, then the node whose first item is null is found. Otherwise, equals is used to compare.

Insert elements

Add is adding elements to the tail. What about inserting elements in the head or in the middle? You can use the following methods:

public void add(int index, E element)
Copy the code

The code is:

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
Copy the code

If the index is size, add it to the end of the index. In general, insert it before the node corresponding to the index. Call method is linkBefore, and its code is as follows:

void linkBefore(E e, Node<E> succ) {
    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 code

The succ parameter represents the successor node. The variable pred represents the precursor node. The goal is to insert a node between preD and SUCC. The insertion steps are:

  1. Create a newNode newNode with pred and succ as its precursor. The code is:
Node<E> newNode = new Node<>(pred, e, succ);
Copy the code
  1. Make subsequent precursors point to the new node. The code is:
succ.prev = newNode;
Copy the code
  1. Make the successor of the precursor point to the new node. If the precursor is empty, modify the head node to point to the new node. The code is:
if (pred == null)
    first = newNode;
else
    pred.next = newNode;
Copy the code
  1. Increase the length.

To see this more clearly, use the illustration above, for example, to add an element:

list.add(1."c");
Copy the code

The structure will become:

Remove elements

Let’s take a look at deleting elements as follows:

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
Copy the code

After the node method is used to find the node, the unlink method is called with the code as follows:

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}
Copy the code

Next is the successor of X, and prev is the precursor of X. It can be divided into two steps:

  1. The first step is to have the heirs of the precursor of X point to the heirs of X. If x does not have a precursor, it indicates that the header node is deleted. In this case, modify the header node to point to the successor of X.
  2. The second step is to have the successor precursor of X point to the precursor of X. If x has no successor, it indicates that the tail node is deleted. Change the tail node to point to the precursor of X.

Let’s look at the illustration again, as in the above example, if we delete an element:

list.remove(1);
Copy the code

The structure will become:

The principle of summary

Above, we have introduced the internals of LinkedList, as well as the code that implements several of the main methods. The principles of the other methods are similar, so we won’t go into details.

As mentioned earlier, there may be a limit on length for queue, stack, and dual-ended queue interfaces. LinkedList implements these interfaces, but LinkedList has no limit on length.

Analysis of LinkedList features

LinkedList is internally implemented as a two-way LinkedList, maintaining length, head and tail nodes, which determines its characteristics as follows:

  • Allocate space on demand, not a lot of space up front
  • Access by index location is inefficient. You must follow the link from the beginning to the end. The efficiency is O(N/2).
  • Regardless of whether the list is sorted or not, looking up elements by content is inefficient and must be compared one by one with O(N) efficiency.
  • The efficiency of adding and removing elements at both ends is O(1).
  • When inserting or deleting elements in the middle, the efficiency is O(N), which is low, but the efficiency of modification itself is high, which is O(1).

Understanding the characteristics of LinkedList and ArrayList makes the selection easier. If the list length is unknown and there are a lot of additions and deletions, especially from both ends, and relatively little access by index position, then LinkedList is an ideal choice.

summary

This section introduces LinkedList in detail, first with usage, then with implementation, and finally with an analysis of the characteristics of LinkedList and a comparison with ArrayList.

In usage, LinkedList is a List, but also implements a Deque interface and can be used as a queue, stack, and double-ended queue. In principle, the internal is a bidirectional linked list, and maintains the length, head node and tail node.

In both arrayLists and Linkedlists, finding elements by content is inefficient and requires comparison one by one. Is there a more efficient way?

To be continued, check the latest articles, please pay attention to the wechat public account “Lao Ma said programming” (scan the qr code below), simple and simple, Lao Ma and you explore the nature of Java programming and computer technology. All rights reserved.