Java-LinkedList source code principle analysis, and constructing a queue through LinkedList-java类库-php.cn

Java-LinkedList source code principle analysis, and constructing a queue through LinkedList

高洛峰

Release： 2016-10-11 16:27:26

Original

2009 people have browsed it

Here we introduce the simplest linked list, LinkedList;

Look at the add() method:

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

Copy after login

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 after login

The principle of add is:

1. First get the last node of the linked list.

2. Insert the new node after the last node.

3.The last attribute of linkedList redirects to the last node.

4. If this node is the first node and there is no previous node, then point the first attribute of the linkedList to the new node; if not, point the next attribute of the previous node to the node.

Use LinkedList to build a first-in-first-out queue:

offer() method to join the queue: use the add() method to insert the node at the end.

public boolean offer(E e) {
        return add(e);
    }

Copy after login

poll() method dequeue: remove the queue from the head of the linked list

public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

Copy after login

Use LinkedList to build a last-in-first-out queue:

push() method enqueue: insert the node at the first

public void addFirst(E e) {
        linkFirst(e);
    }

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++;
    }

Copy after login

pop() method dequeue : Remove from the queue starting from the head of the linked list

public E pop() {
        return removeFirst();
    }

public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

Copy after login

The last thing to note is: LinkedList is thread-unsafe. If you need thread safety, please use synchronized locking, or use vector, or use the java.util.concurrent package.

If you need to avoid ConcurrentModificationException when a thread traverses the List, there are 3 solutions.

1. Use synchronized locking when traversing the List;

2. Use CopyOnWriteArrayList under the java.util.concurrent package. Every time you use the List, you are actually using a copy of the List.

3. Use the foreach method in Jdk8, but this method only accepts lambda expressions

list.forEach(item -> {
                    System.out.println("遍历元素：" + item);
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                });

Copy after login