Java-鍊錶LinkedList原始碼原理分析，並且透過LinkedList建構佇列-java类库-PHP中文網

Java-鍊錶LinkedList原始碼原理分析，並且透過LinkedList建構佇列

高洛峰

發布： 2016-10-11 16:27:26

原創

2008 人瀏覽過

在這裡我們介紹一下最簡單的鍊錶LinkedList；

看一下add()方法：

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

登入後複製

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

登入後複製

add原理就是：

1.首先取得鍊錶最後一個節點。

2.把新節點插入到最後一個節點之後。

3.linkedList的last屬性重新指向最後一個節點。

4.如果這個節點是第一個節點，之前沒有節點，那麼將linkedList的first的屬性指向新節點；如果不是，則將上一個節點的next屬性指向該節點。

使用LinkedList建構先進先出隊列：

offer()方法入隊：使用add()方法插入節點在最後。

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

登入後複製

poll()方法出隊：從鍊錶頭開始移出隊列

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

登入後複製

使用LinkedList建構後進先出隊列：

push()方法入隊：插入節點在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++;
    }

登入後複製

()方法出隊：從鍊錶頭開始移出佇列

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

登入後複製

最後要注意的是：LinkedList是執行緒不安全的，如果需要執行緒安全那麼請使用synchronized加鎖，或是使用vector，或使用java.util.concurrent套件。

如果需要執行緒遍歷List的時候，避免出現ConcurrentModificationException異常，那麼有3種解決方式。

1.遍歷List的使用synchronized加鎖；

2.使用java.util.concurrent套件下面的CopyOnWriteArrayList，每次使用List時實際上都是使用的List副本。

3.使用Jdk8中foreach方法，不過此方法只接受lambda表達式

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

登入後複製