링크 드 리스트 부분 소스 분석 (jdk 1.8, 이해 할 수 있 도록)

Lined List 를 분석 하기 전에 링크 에 대해 간단 한 소 개 를 하 겠 습 니 다. 링크 는 배열 처럼 많이 사용 되 지 않 기 때문에 많은 사람들 이 잘 모 르 는 것 도 불가피 합 니 다.
링크 는 기본 적 인 선형 데이터 구조 로 배열 과 같은 선형 이지 만 배열 은 메모리 의 물리 적 저장 에 있어 선형 논리 적 으로 도 선형 이 고 링크 는 논리 적 으로 선형 일 뿐이다.링크 의 모든 저장 장치 에 현재 요소 뿐만 아니 라 다음 저장 장치 의 주소 도 저장 되 어 있 습 니 다. 주 소 를 통 해 모든 저장 부 를 연결 할 수 있 습 니 다.찾 을 때마다 첫 번 째 저장 소 를 통 해 필요 한 요 소 를 찾 을 수 있다.삭제 작업 을 수행 하려 면 관련 요소 의 방향 을 끊 으 면 됩 니 다.
링크 드 리스트 에서 사용 하 는 것 은 가장 기본 적 인 단 방향 링크 가 아니 라 양 방향 링크 입 니 다.
linedList 에 기본 저장 장치 가 존재 합 니 다. LinkedList 의 내부 클래스 노드 요소 에 두 개의 속성 이 존재 합 니 다. 각각 앞의 노드 와 뒤의 노드 의 인용 을 저장 합 니 다.

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

정의.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

정의 상 ArrayList 와 큰 차 이 는 없 지만 주의해 야 할 것 은 LinkedList 가 Deque (간접 적 으로 Qeque 인터페이스 실현) Deque 를 실현 한 것 입 니 다.
초기 화 는 ArrayList 를 분석 할 때 ArrayList 가 무 참 구조 방법 을 사용 할 때 초기 화 길이 가 10 이 고 모든 무 참 구조 로 구 성 된 집합 이 같은 대상 배열 을 가리 키 는 것 을 알 고 있 습 니 다. 그러면 LinkedList 의 초기 화 는 어떻게 됩 니까?
무 참 구조 방법 열기

public LinkedList() {
}

아무것도 없 으 니 속성 만 볼 수 있 습 니 다.
/ / 길이 가 0 으로 초기 화 됨

transient int size = 0;
//     
transient Node<E> first;
transient Node<E> last;

방법.

add(E e)

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

방법 에서 우 리 는 추가 방법 을 호출 한 후에 바로 추가 한 것 이 아니 라 링크 Last 방법 을 호출 한 새로운 요소 의 추가 위 치 는 집합 마지막 이라는 것 을 알 고 있다.

void linkLast(E e) {
 //          （    ）   l final                   
  final Node<E> l = last;
 //                          
  final Node<E> newNode = new Node<>(l, e, null);
  //                    last
  last = newNode;
  //  l null                 first          list                            
  if (l == null)
    first = newNode;
  else
    //         ，       l（          ） next
    l.next = newNode;
  //  +1
  size++;
  //    +1
  modCount++;
}

상기 코드 에서 우 리 는 요 소 를 추가 할 때 아래 표 에 의존 하지 않 는 것 을 볼 수 있다.
그 중의 처 리 는 하나의 last (Node 대상) 를 통 해 마지막 노드 의 정 보 를 저장 하 는 것 이다 (실제 적 으로 마지막 노드). 매번 끊임없이 변화 하 는 마지막 요 소 를 통 해 요소 의 추 가 를 실현 한다.

**add(int index, E element)**
*        *
public void add(int index, E element) {
  //      
  checkPositionIndex(index);
//             linkLast
  if (index == size)
    linkLast(element);
  //     linkBefore
  else
    linkBefore(element, node(index));
}
//           
void linkBefore(E e, Node<E> succ) {
  // assert succ != null;      succ  null
  //          succ prev              
  final Node<E> pred = succ.prev;
  //                 e prev    pred        succ       next succ
  final Node<E> newNode = new Node<>(pred, e, succ);
  //  succ                      
  succ.prev = newNode;
 //   pred null          
  if (pred == null)
    //    first     
    first = newNode;
  //  
  else
    //      next       
    pred.next = newNode;
  //  +1
  size++;
  modCount++;

get

public E get(int index) {
  //                        
  checkElementIndex(index);
  //                item         
  return node(index).item;
}

//               
private void checkElementIndex(int index) {
  if (!isElementIndex(index))
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
  return index >= 0 && index < size;
}

//                 
Node<E> node(int index) {
  //                                  
  // assert isElementIndex(index);

  //  index  size             （    ）          
  if (index < (size >> 1)) {//            
    Node<E> x = first;
    //  
    for (int i = 0; i < index; i++)
      //      next                 x                     index      index       
      x = x.next;
    return x;
  } else {
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

이 코드 에서 양 방향 링크 의 우수 성 을 충분히 나 타 냈 다. 예전 부터 index 범위 에 대한 판단 을 통 해 현저 한 효율 을 높 일 수 있다.하지만 옮 겨 다 닐 때 도 링크 드 리스트 get 방법 으로 요 소 를 얻 는 비효 율 성 을 뚜렷하게 볼 수 있다.
remove(int index)
삭제 노드 란 노드 의 앞 뒤 인용 을 null 로 설정 하고 다른 노드 가 삭 제 된 노드 를 가리 키 지 않도록 하 는 것 입 니 다.

public E remove(int index) {
  //      
  checkElementIndex(index);
  //                 
  //node          
  //unlink          
  return unlink(node(index));
}

E unlink(Node<E> x) {
  //  x  null
  // assert x != null;
  //      element  x                 
  final E element = x.item;
  //          x         
  final Node<E> next = x.next;
  final Node<E> prev = x.prev;
  //        null          
  if (prev == null) {
    //x                first       
    first = next;
  } else {
    //    x          prev（x      ） next  x      （  x）
    prev.next = next;
    //x      null
    x.prev = null;
  }
//        null                               
  if (next == null) {
    last = prev;
  } else {
    next.prev = prev;
    x.next = null;
  }
// x        null
  x.item = null;
  size--;
  modCount++;
  return element;
}

prev, item, next 를 모두 null 로 설정 한 것 은 가상 컴퓨터 를 회수 하기 위 한 것 임 을 설명 합 니 다.