Java-LinkedList 소스 코드 원리 분석 및 LinkedList를 통한 대기열 구성

가장 간단한 연결 목록인 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의 마지막 속성은 마지막 노드로 리디렉션됩니다.

4. 이 노드가 첫 번째 노드이고 이전 노드가 없으면 linkedList의 첫 번째 속성이 새 노드를 가리키고, 그렇지 않으면 이전 노드의 다음 속성이 해당 노드를 가리킵니다.

LinkedList를 사용하여 선입선출 대기열 구축:

queue에 제안() 메서드 사용: 끝에 노드를 삽입하려면 add() 메서드 사용 .

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

queue에서 제거하는 poll() 메서드: 연결된 목록의 헤드에서 대기열을 제거합니다.

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

LinkedList를 사용하여 후입선출 대기열을 만듭니다.

push() 메소드 Enqueue: 처음에 노드 삽입

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

pop() 메소드 Dequeue: 연결된 목록의 선두부터 큐에서 제거

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는 스레드에 안전하지 않다는 점에 유의해야 합니다. 예, 스레드 안전성이 필요하면 동기화된 잠금을 사용하거나 벡터를 사용하거나 java.util.concurrent 패키지를 사용하십시오.

스레드가 목록을 순회할 때 ConcurrentModificationException을 방지해야 하는 경우 세 가지 해결 방법이 있습니다.

1. 목록을 탐색할 때 동기화된 잠금을 사용합니다.

2. java.util.concurrent 패키지에서 CopyOnWriteArrayList를 사용합니다. 목록.

3. Jdk8에서 foreach 메서드를 사용하지만 이 메서드는 람다 식만 허용합니다.

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