Java LinkedList 소스코드 분석(사진)

전체 소개

LinkedList는 List인터페이스와 Deque 인터페이스를 모두 구현하므로 순차 컨테이너이자 큐(큐)로 간주할 수 있습니다. 스택(Stack)이라고도 볼 수 있습니다. 이런 관점에서 LinkedList는 그야말로 만능 챔피언입니다. 스택이나 큐를 사용해야 할 때 가장 먼저 고려해야 할 것은 LinkedList입니다. Java에서는 Stack 클래스의 사용을 권장하지 않는다고 공식적으로 밝혔기 때문에 LinkedList를 사용하는 것이 좋습니다. 더욱 아쉬운 점은 Java에는 Queue라는 클래스(인터페이스 이름입니다)가 없다는 점입니다.

LinkedList의 기본 계층은 이중 연결 목록을 통해 구현됩니다. 이 섹션에서는 삭제 요소, 즉 List 인터페이스와 관련된 함수 와 Queue, Stack, Deque와 관련된 지식 간의 솔루션에 대해서는 다음 섹션에서 논의하겠습니다. 이중 연결 리스트의 각 노드는 내부 클래스 Node로 표시됩니다. LinkedList는 에서 first 및 last을 참조하여 각각 연결된 목록의 첫 번째 요소와 마지막 요소를 가리킵니다. 여기에는 소위 더미 요소가 없습니다. 연결된 목록이 비어 있으면 및 first 모두 <a href="http://www.php.cn/wiki/62%EB%A5%BC%20%EA%B0%80%EB%A6%AC%ED%82%B5%EB%8B%88%EB%8B%A4.%20.html" target=" _blank">null<code>last. <a href="http://www.php.cn/wiki/62.html" target="_blank">null</a>

//Node内部类
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;
    }
}

LinkedList의 구현은 모든 첨자 관련 작업이 선형 시간이고 시작이나 끝의 요소를 삭제하면 상수 시간만 필요하다고 결정합니다. 효율성을 추구하기 위해 LinkedList는 동기화(syn

chr화)를 구현하지 않습니다. 여러 스레드의 동시 액세스가 필요한 경우 먼저 메서드를 사용하여 래핑할 수 있습니다. Collections.synchronizedList()

메서드 분석

add()

add() 메소드에는 두 가지 버전이 있는데 하나는

입니다. 이 메소드는 연결된 목록의 끝을 가리키며 끝에 요소를 삽입하는 데 일정한 시간이 걸립니다. 몇 가지 관련 참조만 수정하면 되며, 다른 하나는 아래 지정된 테이블에 요소를 삽입하는 것입니다. 먼저 선형 검색을 통해 특정 위치를 찾은 다음 관련 참조를 수정하여 완료하면 됩니다. 삽입 작업. add(E e)lastadd(int index, E element)

위 그림과 함께 보면 의 논리가 매우 단순하다는 것을 알 수 있습니다.

//add(E e)
public boolean add(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++;
    return true;
}

add(E e)의 논리는 약간 복잡하며 두 부분으로 나눌 수 있습니다. 1. 먼저 인덱스에 따라 삽입할 위치를 찾습니다. 2. 참조를 수정하고 삽입 작업을 완료합니다.

//add(int index, E element)
public void add(int index, E element) {
    checkPositionIndex(index);//index >= 0 && index <= size;
    if (index == size)//插入位置是末尾，包括列表为空的情况
        add(element);
    else{
        Node<E> succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用，完成插入操作。
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

위 코드의 add(int index, E element) 함수는 조금 까다롭습니다. 연결 목록이 양방향이기 때문에 처음부터 뒤로 검색할 수도 있고, 끝에서 앞으로 검색할 수도 있습니다. 구체적인 검색 방향은

조건, 즉 인덱스가 프런트 엔드에 가까울지, 백엔드에 가까울지에 따라 다릅니다.

node(int index)remove()index > 1)

메소드에도 두 가지 버전이 있습니다. 하나는 지정된 요소 remove(<a href="http)%EC%99%80%20%EB%8F%99%EC%9D%BC%ED%95%9C%20%EC%B2%AB%20%EB%B2%88%EC%A7%B8%20%EC%9A%94%EC%86%8C%EB%A5%BC%20%EC%82%AD%EC%A0%9C%ED%95%98%EB%8A%94%20%EA%B2%83%EC%9E%85%EB%8B%88%EB%8B%A4.%20://%20www.php.cn/wiki/60.html" target="_blank">Object</a>

o), 다른 하나는 지정된 첨자에서

요소를 삭제하는 것입니다. remove()remove(<a href="http://www.php.cn/wiki/60.html" target="_blank">Object</a> o)remove(int index)

두 삭제 작업 모두 1. 먼저 삭제할 요소의 참조를 찾은 다음, 2. 해당 참조를 수정하여 삭제 작업을 완료해야 합니다. 삭제된 요소에 대한 참조를 찾을 때 는 요소의

메서드를 호출하는 반면,

는 두 메서드 모두 선형 시간 복잡도를 사용합니다. 2단계에서는 remove(Object o) 메서드를 통해 두 equals 메서드가 모두 완료됩니다. 여기서 삭제된 요소가 첫 번째 또는 마지막 요소인 경우 경계 사례를 고려해야 합니다. remove(int index)

//unlink(Node<E> x)，删除一个Node
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;//let GC work
    size--;
    return element;
}

revome()get()unlink(Node<e> x)</e>

위에서 언급한

메서드를 호출하여 지정된 첨자에 있는 요소에 대한 참조를 가져옵니다.

public E get(int index) {
    checkElementIndex(index);//index >= 0 && index < size;
    return node(index).item;
}

get(int index)set()node(int index)

메서드는 지정된 첨자의 요소를 지정된 값으로 수정합니다. 또한 먼저

를 통해 아래 표의 요소에 대한 참조를 찾습니다. ,

set(int index, E element) 값을 수정합니다. node(int index)아아아아

위 내용은 Java LinkedList 소스코드 분석(사진)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!