자바 에서 링크 드 리스트 를 집합 하 는 원리 와 사용 방법

머리말
LinkedList 는 Array List 와 마찬가지 로 집합 List 의 실현 류 입 니 다.Array List 에 비해 사용 장면 이 많 지 않 지만 똑 같이 유용 할 때 다음 에 알 아 보 겠 습 니 다.
링크 목록

public static void main(String[] args) {
 List<String> stringList = new LinkedList<>();
 List<String> tempList = new ArrayList<>();
 tempList.add("   ");
 tempList.add("   ");
 tempList.add("   ");
 tempList.add("   ");
 tempList.add("   ");
 tempList.add("   ");
 tempList.add("   ");
 List<String> stringList2 = new LinkedList<>(tempList);
}

위의 코드 에서 두 가지 방식 으로 LinkedList 를 정의 합 니 다.빈 집합 을 정의 할 수도 있 고 기 존의 집합 을 전달 하여 LinkedList 로 전환 할 수도 있 습 니 다.소스 코드 한번 볼 게 요.

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
 transient int size = 0;

 /**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 * (first.prev == null && first.item != null)
 */
 transient Node<E> first;

 /**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 * (last.next == null && last.item != null)
 */
 transient Node<E> last;

 /**
 * Constructs an empty list.
 */
 public LinkedList() {
 }

 /**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
 public LinkedList(Collection<? extends E> c) {
 this();
 addAll(c);
 }
}

LinkedList 는 AbstractSequential List 류 를 계승 하여 List 인 터 페 이 스 를 실현 했다.AbstractSequential List 는 get(int index),set(int index,E element),add(int index,E element)와 reove(int index)등 여러 가지 방법 을 실현 했다.이런 방법 들 은 우리 가 집합 작업 을 할 때 가장 많이 사용 하지만 이런 방법 들 은 LinkedList 에서 모두 재 작성 되 었 다.추상 적 인 방법 은 링크 드 리스트 에서 구체 적 으로 실현 되 었 다.그래서 우 리 는 링크 드 리스트 류 로 돌 아 왔 다.
LinkedList 클래스 에서 세 개의 변 수 를 정 의 했 습 니 다.
집합 길이
first:양 방향 링크 헤드 노드
last:양 방향 링크 꼬리 노드
first 변수 와 last 변수 에 대해 우 리 는 Node 류 의 실 체 를 보 았 습 니 다.이것 은 정적 내부 류 입 니 다.정적 내부 류 에 대한 설명 은static 5 대 응용 장면장 에서 이미 설명 되 었 습 니 다.

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 가 양 방향 링크 를 통 해 이 루어 진 것 을 알 고 있 습 니 다.양 방향 링크 는 Node 류 를 통 해 나타 난 것 입 니 다.클래스 에서 item 변 수 를 통 해 현재 노드 의 값 을 저장 하고 next 변 수 를 통 해 다음 노드 를 가리 키 며 prev 변 수 를 통 해 이전 노드 를 가리 킵 니 다.
2.LinkedList 상용 방법
1. get(int index)
랜 덤 읽 기 요 소 는 LinkedList 가 잘 하 는 것 이 아니 라 읽 기 효율 이 ArrayList 보다 훨씬 낮 다 는 것 을 알 고 있 습 니 다.그럼 왜 그런 지 알 아 보 겠 습 니 다.

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

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

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

상기 코드 에서 우 리 는 get(int index)방법 이 node(int index)를 통 해 이 루어 진 것 을 볼 수 있 습 니 다.그 실현 체 제 는:
들 어 오 는 색인 매개 변수 index 와 집합 길이 size/2 를 비교 합 니 다.index 가 작 으 면 첫 번 째 순서 로 찾 을 때 까지 순환 합 니 다.index 가 크 면 마지막 역순 으로 찾 을 때 까지 순환 합 니 다.즉,중간 요소 에 가 까 워 질 수록 get(int index 방법 을 사용 하 는 횟수 가 많 을 수록 효율 도 낮 아 지고 집합 이 커지 면서 get(int index)의 실행 성능 도 지수 급 이 떨어진다.따라서 LinkedList 를 사용 할 때 저 희 는 이런 방식 으로 데 이 터 를 읽 는 것 을 권장 하지 않 습 니 다.getFirst(),getLast()방법 을 사용 하여 클래스 의 first 와 last 변 수 를 직접 사용 할 수 있 습 니 다.
2.add(E e)와 add(int index,E element)
링크 드 리스트 삽입,삭제 작업 효율 이 높다 고 하 는데,stringList.add('저팔계')를 예 로 들 면 도대체 무슨 일이 일 어 났 는 지 알 수 있다.
LinkedList 에서 add(E)방법의 원본 코드 를 찾 았 습 니 다.

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

/**
 *     e       
*/
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++;
}

이해 하기 쉽다.
상황 1:stringList 가 비어 있 으 면 추 가 된 node 는 first 이 고 last 입 니 다.이 node 의 prev 와 next 는 모두 null 입 니 다.

상황 2:stringList 가 비어 있 지 않 으 면 추 가 된 node 는 last 입 니 다.node 의 prev 는 이전의 마지막 요 소 를 가리 키 고 node 의 next 는 null 입 니 다.동시에 이전의 마지막 원소 의 next.

stringList.add(1,'저팔계')를 통 해 요 소 를 집합 에 추가 하면?

//           
public void add(int index, E element) {
 checkPositionIndex(index);
 if (index == size)
 linkLast(element);
 else
 linkBefore(element, node(index));
}

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

사실 코드 에서 보 듯 이 add(E)의 코드 구현 과 본질 적 인 차이 가 없습니다.모두 새로운 Node 실 체 를 통 해 prev 와 next 를 지정 하여 이 루어 집 니 다.다른 점 은 node(int index)를 호출 하여 들 어 오 는 index 를 통 해 삽입 할 위 치 를 찾 아야 한 다 는 것 입 니 다.이것 도 시간 이 걸 립 니 다.위의 get(int index)방법 을 참고 하 십시오.
사실 이곳 을 보고 모두 가 알 게 되 었 다.
LinkedList 삽입 효율 이 높 은 것 은 상대 적 인 것 입 니 다.Array List 가 데 이 터 를 삽입 할 수 있 는 배열 확장 과 데이터 요소 가 이동 할 때 발생 하 는 비용 을 줄 였 기 때 문 입 니 다.그러나 데이터 확장 과 데이터 요소 의 이동 은 항상 발생 하 는 것 이 아 닙 니 다.
3.remove(Object o)와 remove(int index)
여기 서 removeFirst()와 removeLast()는 더 이상 말 하지 않 습 니 다.클래스 에서 정의 하 는 first 와 last 변 수 를 사용 합 니 다.매우 간단 합 니 다.remove(Object o)와 reove(int index)소스 코드 를 살 펴 보 겠 습 니 다.

//      
public boolean remove(Object o) {
 if (o == null) {
 for (Node<E> x = first; x != null; x = x.next) {
 if (x.item == null) {
 unlink(x);
 return true;
 }
 }
 } else {
 for (Node<E> x = first; x != null; x = x.next) {
 if (o.equals(x.item)) {
 unlink(x);
 return true;
 }
 }
 }
 return false;
}
//         
public E remove(int index) {
 checkElementIndex(index);
 return unlink(node(index));
}
//     ，           （   ）      （   ）    
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;
 size--;
 modCount++;
 return element;
}

사실 실현 은 매우 간단 합 니 다.먼저 삭제 할 노드 를 찾 고 reove(Object o)방법 으로 전체 집합 을 옮 겨 다 니 며==또는 equals 방법 으로 판단 합 니 다.reove(int index)는 node(index)방법 을 통 해

4.LinkedList 옮 겨 다 니 기
우 리 는 주로 세 가지 자주 사용 하 는 옮 겨 다 니 는 방식 을 열거 했다.
일반 for 순환,증강 for 순환,Iterator 교체 기

public static void main(String[] args) {
 LinkedList<Integer> list = getLinkedList();
 //          LinkedList
 listByNormalFor(list);
 //    for    LinkedList
 listByStrengThenFor(list);
 //        LinkedList
 listByIterator(list);
}

/**
 *     LinkedList  ,    50000 
 * @return
 */
private static LinkedList<Integer> getLinkedList() {
 LinkedList list = new LinkedList();
 for (int i = 0; i < 50000; i++){
 list.add(i);
 }
 return list;
}

/**
 *           LinkedList
 */
private static void listByNormalFor(LinkedList<Integer> list) {
 //       
 long start = System.currentTimeMillis();
 int size = list.size();
 for (int i = 0; i < size; i++) {
 list.get(i);
 }
 //     
 long interval = System.currentTimeMillis() - start;
 System.out.println("listByNormalFor：" + interval + " ms");
}

/**
 *     for    LinkedList
 * @param list
 */
public static void listByStrengThenFor(LinkedList<Integer> list){
 //       
 long start = System.currentTimeMillis();
 for (Integer i : list) { }
 //     
 long interval = System.currentTimeMillis() - start;
 System.out.println("listByStrengThenFor：" + interval + " ms");
}

/**
 *         LinkedList
 */
private static void listByIterator(LinkedList<Integer> list) {
 //       
 long start = System.currentTimeMillis();
 for(Iterator iter = list.iterator(); iter.hasNext();) {
 iter.next();
 }
 //     
 long interval = System.currentTimeMillis() - start;
 System.out.println("listByIterator：" + interval + " ms");
}

실행 결 과 는 다음 과 같 습 니 다.
listByNormalFor：1067 ms
listByStrengThenFor：3 ms
listByIterator：2 ms
일반 for 순환 무 작위 접근 방식 을 통 해 실행 시간 이 교체 기 접근 방식 보다 훨씬 크다 는 것 을 이해 할 수 있 습 니 다.앞의 get(int index)방법 에서 설명 한 적 이 있 습 니 다.그러면 왜 for 순환 을 강화 하면 교체 기 를 옮 겨 다 니 는 차이 가 많 지 않 은 효율 을 할 수 있 습 니까?
역 컴 파일 도 구 를 통 해 다음 코드 를 얻 을 수 있 습 니 다.

public static void listByStrengThenFor(LinkedList<Integer> list)
 {
 long start = System.currentTimeMillis();
 Integer localInteger;
 for (Iterator localIterator = list.iterator(); localIterator.hasNext(); 
 localInteger = (Integer)localIterator.next()) {}
 long interval = System.currentTimeMillis() - start;
 System.out.println("listByStrengThenFor：" + interval + " ms");
}

분명 합 니 다.증강 for 순환 을 옮 겨 다 닐 때 도 교체 기 Iterator 를 호출 했 지만 할당 과정 이 하나 더 생 겼 습 니 다.
또한 pollFirst(),pollLast()값 을 추출 한 후 삭제 하 는 방법 도 일부 옮 겨 다 니 는 효 과 를 얻 을 수 있 습 니 다.
총화
본 고 는 자바 8 을 바탕 으로 하나의 LinkeList 를 정의 하 는 데 착안 하여 점차적으로 전개 되 었 다.소스 코드 측면 에서 LinkedList 양 방향 링크 의 구 조 를 어떻게 구축 하 는 지 분석 하 는 동시에 자주 사용 하 는 방법 에 대해 분석 했다.이 는 get,add,reove 와 자주 사용 하 는 옮 겨 다 니 는 방법 을 포함 하고 그의 삽입,삭제 작업 이 왜 상대 적 으로 효율 적 이 고 수치 조작 성능 이 상대 적 으로 낮은 지 간단하게 설명 했다.잘못된 점 이 있 으 면 비판 하고 지적 하 며 함께 발전 하 기 를 바 랍 니 다.감사합니다!
자,이상 이 이 글 의 모든 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 참고 학습 가 치 를 가지 기 를 바 랍 니 다.여러분 의 저희 에 대한 지지 에 감 사 드 립 니 다.