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; } }
chr화)를 구현하지 않습니다. 여러 스레드의 동시 액세스가 필요한 경우 먼저 메서드를 사용하여 래핑할 수 있습니다. Collections.synchronizedList()
입니다. 이 메소드는 <가 있기 때문에 LinkedList의 끝에 요소를 삽입합니다. 🎜>연결된 목록의 끝을 가리키며 끝에 요소를 삽입하는 데 일정한 시간이 걸립니다. 몇 가지 관련 참조만 수정하면 되며, 다른 하나는 아래 지정된 테이블에 요소를 삽입하는 것입니다. 먼저 선형 검색을 통해 특정 위치를 찾은 다음 관련 참조를 수정하여 완료하면 됩니다. 삽입 작업. add(E e)
last
add(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 < (size >> 1)
remove(<a href="http)와 동일한 첫 번째 요소를 삭제하는 것입니다. :// www.php.cn/wiki/60.html" target="_blank">Object</h3> 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)
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!