자바 집합 시리즈 의 LinkedList 소스 분석
8566 단어 Java집합 하 다.LinkedList
F 는 두 결점 인용 을 나타 내 고 L 은 꼬리 결점 인용 을 나타 낸다.링크 의 모든 결점 은 세 가지 요소 가 있 는데 그것 이 바로 앞 접점 인용(P),결점 요소 의 값(E),뒤 접점 의 인용(N)이다.결점 은 내부 류 노드 에 의 해 표시 되 며,우 리 는 그것 의 내부 구 조 를 보 았 다.
//
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;
}
}
//
transient int size = 0;
//
transient Node<E> first;
//
transient Node<E> last;
//
public LinkedList() {}
//
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
// ( )
public boolean add(E e) {
//
linkLast(e);
return true;
}
// ( )
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) {
//
linkLast(element);
} else {
//
linkBefore(element, node(index));
}
}
// ( )
public E remove(int index) {
//
checkElementIndex(index);
return unlink(node(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 set(int index, E element) {
//
checkElementIndex(index);
//
Node<E> x = node(index);
//
E oldVal = x.item;
//
x.item = element;
//
return oldVal;
}
//
public E get(int index) {
//
checkElementIndex(index);
//
return node(index).item;
}
//
void linkBefore(E e, Node<E> succ) {
//
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++;
}
//
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;
}
linkBefore 방법의 과정 도:
unlink 방법의 과정 도:
위의 그림 을 통 해 알 수 있 듯 이 링크 의 삽입 과 삭제 작업 의 시간 복잡 도 는 모두 O(1)이 고 링크 에 대한 검색 과 수정 작업 은 모두 링크 를 옮 겨 다 니 며 요소 의 포 지 셔 닝 을 해 야 합 니 다.이 두 작업 은 모두 호출 된 node(int index)방법 으로 요 소 를 포 지 셔 닝 하고 아래 표 시 를 통 해 요 소 를 어떻게 포 지 셔 닝 하 는 지 보 세 요.
//
Node<E> node(int 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;
}
}
단 방향 대기 열 동작:
//
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//
public E element() {
return getFirst();
}
//
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//
public E remove() {
return removeFirst();
}
//
public boolean offer(E e) {
return add(e);
}
//
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//
public boolean offerLast(E e) {
addLast(e);
return true;
}
//
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
//
public void push(E e) {
addFirst(e);
}
//
public E pop() {
return removeFirst();
}
1.LinkedList 는 양 방향 링크 를 바탕 으로 이 루어 진 것 으로 삭제 검사 방법 이 든 대기 열 과 스 택 의 실현 이 든 모두 조작 노드 를 통 해 이 루어 질 수 있다.
2.LinkedList 는 미리 용량 을 지정 할 필요 가 없습니다.링크 작업 을 바탕 으로 집합 하 는 용량 은 요소 의 가입 에 따라 자동 으로 증가 하기 때 문 입 니 다.
3.LinkedList 요 소 를 삭제 한 후 집합 하여 사용 하 는 메모리 가 자동 으로 축소 되 며,ArrayList 처럼 trimToSize()방법 을 호출 할 필요 가 없습니다.
4.LinkedList 의 모든 방법 이 동기 화 되 지 않 았 기 때문에 스 레 드 가 안전 한 것 도 아니 므 로 다 중 스 레 드 환경 에서 사용 하지 않도록 해 야 합 니 다.
5.상기 분석 은 JDK 1.7 을 바탕 으로 다른 버 전이 약간 다 를 수 있 기 때문에 일률적으로 논 할 수 없다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
