자바 용기 소스 코드 LinkedList 원리 분석

LinkedList 소개
LinkedList 는 양 방향 링크 구 조 를 사용 하여 이 루어 진 용기 로 Array List 와 마찬가지 로 길 이 를 동적 으로 확장 할 수 있 습 니 다.LinkedList 는 Array List 에 비해 임의의 위치 삽입 속도 가 Array List 보다 빠 르 지만 조회 속 도 는 Array List 보다 느 립 니 다.LinkedList 는 AbstractSequential List 를 계승 하여 List,Deque,Cloneable,Serializable 인 터 페 이 스 를 실현 했다.
LinkedList UML 그림 은 다음 과 같 습 니 다.

ArrayList 와 마찬가지 로 LinkedList 도 스 레 드 가 안전 한 용기 가 아 닙 니 다.
LinkedList 소스 코드 분석
구조 방법
LinkedList 는 두 가지 구조 방법 이 있 습 니 다.

public LinkedList() {
}

//            LinkedList  
public LinkedList(Collection<? extends E> c) {
  this();
  addAll(c);
}

addAll()방법:

public boolean addAll(Collection<? extends E> c) {
  return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
  //  index    
  checkPositionIndex(index);
  
  Object[] a = c.toArray();
  int numNew = a.length;
  if (numNew == 0)
    return false;
  //   index   node   node      
  //succ： index   node  
  //pred：index     node  
  Node<E> pred, succ;
  if (index == size) {
    succ = null;
    pred = last;
  } else {
    succ = node(index);
    pred = succ.prev;
  }

  //  ，        
  for (Object o : a) {
    @SuppressWarnings("unchecked") E e = (E) o;
    Node<E> newNode = new Node<>(pred, e, null);
    if (pred == null)
      first = newNode;
    else
      pred.next = newNode;
    pred = newNode;
  }

  if (succ == null) {
    last = pred;
  } else {
    pred.next = succ;
    succ.prev = pred;
  }

  size += numNew;
  modCount++;
  return true;
}

add 방법
링크 드 리스트 에 도 두 가지 add 방법 이 있 습 니 다.다음 과 같 습 니 다.

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

public void add(int index, E element) {
  //  index    
  checkPositionIndex(index);

  if (index == size)
    //index == size，       
    linkLast(element);
  else
    //index != size，     index  
    linkBefore(element, node(index));
}

linkLast 방법:

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

linkBefore 방법:

void linkBefore(E e, Node<E> succ) {
  // assert succ != null;
  //     node        pred
  final Node<E> pred = succ.prev;
  //    node，       pred  
  final Node<E> newNode = new Node<>(pred, e, succ);
  //      node           ，    
  succ.prev = newNode;
  if (pred == null)
    first = newNode;
  else
    pred.next = newNode;
  size++;
  modCount++;
}

지정 한 위치 node 포인터 가 져 오 는 방법 node:

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

get 방법 도 간단 합 니 다.먼저 index 가 넘 치 는 지 확인 한 다음 index 위치 에 있 는 요 소 를 직접 찾 아 item 을 되 돌려 줍 니 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.