LinkedList 상세 설명
17859 단어 데이터 구조
LinkedList 는 양 방향 링크 구조 로 링크 데이터 구조의 특징 은 모든 요소 가 분 배 된 공간 이 연속 되 지 않 고 요 소 를 삽입 하고 삭제 할 때 속도 가 매우 빠 르 지만 요소 에 접근 하 는 속도 가 비교적 느리다 는 것 이다.
LinkedList 는 AbstractSequential List 를 계승 하여 List, Deque, Cloneable, Serializable 인 터 페 이 스 를 실현 했다.
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable 전역 변수
LinkedList 의 전역 변 수 는 size, first, last 가 있 습 니 다.size 는 현재 링크 의 길 이 를 기록 하 는 데 사 용 됩 니 다. first 는 링크 머리 첫 번 째 노드 요소 의 정 보 를 기록 하 는 데 사 용 됩 니 다. last 는 링크 끝 에 있 는 마지막 노드 요소 의 정 보 를 기록 하 는 데 사 용 됩 니 다.
transient int size;
transient LinkedList.Node first;
transient LinkedList.Node last; 다시 한 번 살 펴 보 겠 습 니 다. 헤드 노드 LinkedList. Node 내부 의 개인 류 는 한 노드 의 관건 적 인 정 보 를 저장 하고 있 습 니 다. item 은 현재 노드 요 소 를 대표 하고 next 는 현재 노드 요소 의 다음 노드 요 소 를 대표 하 며 prev 는 현재 노드 요소 의 이전 노드 요 소 를 대표 합 니 다.
private static class Node {
//
E item;
//
LinkedList.Node next;
//
LinkedList.Node prev;
//Node
Node(LinkedList.Node var1, E var2, LinkedList.Node var3) {
this.item = var2;
this.next = var3;
this.prev = var1;
}
} getFirst 방법
LinkedList 헤드 노드 요소 가 져 오기
public E getFirst() {
// first var1
LinkedList.Node var1 = this.first;
// var1 null，
if (var1 == null) {
throw new NoSuchElementException();
}
// var1 item
else {
return var1.item;
}
}요소 방법
element 방법 내부 호출 getFirst 방법
public E element() {
return this.getFirst();
}peek 방법
peek 방법 은 LinkedList 헤드 노드 를 가 져 오 는 방법 입 니 다. getFirst 와 element 도 머리 노드 를 가 져 오 는 데 사 용 됩 니 다. 그러나 getFirst 와 element 는 머리 노드 를 찾 지 못 하면 잘못 던 집 니 다. peek 가 머리 노드 를 찾 지 못 하면 null 로 돌아 갑 니 다.
public E peek() {
//var1
LinkedList.Node var1 = this.first;
// null null， null item
return var1 == null ? null : var1.item;
}getLast 방법
LinkedList 끝 노드 요소 가 져 오기
public E getLast() {
// last var1
LinkedList.Node var1 = this.last;
// null，
if (var1 == null) {
throw new NoSuchElementException();
}
// var1 item
else {
return var1.item;
}
}get 방법
아래 표 시 를 통 해 LinkedList 에 대응 하 는 요 소 를 가 져 옵 니 다.
public E get(int var1) {
this.checkElementIndex(var1);
return this.node(var1).item;
}
//
private void checkElementIndex(int var1) {
// LinkedList ，
if (!this.isElementIndex(var1)) {
throw new IndexOutOfBoundsException(this.outOfBoundsMsg(var1));
}
}
//
private boolean isElementIndex(int var1) {
// 0 LinkedList size， true
return var1 >= 0 && var1 < this.size;
}
// LinkedList node
LinkedList.Node node(int var1) {
LinkedList.Node var2;
int var3;
if (var1 < this.size >> 1) {
var2 = this.first;
for(var3 = 0; var3 < var1; ++var3) {
var2 = var2.next;
}
return var2;
} else {
var2 = this.last;
for(var3 = this.size - 1; var3 > var1; --var3) {
var2 = var2.prev;
}
return var2;
}
} removeFirst 방법
첫 노드 요소 제거 first
public E removeFirst() {
// LinkedList
LinkedList.Node var1 = this.first;
// var1 null，
if (var1 == null) {
throw new NoSuchElementException();
}
//
else {
return this.unlinkFirst(var1);
}
}
//
private E unlinkFirst(LinkedList.Node var1) {
// var1 item var2
Object var2 = var1.item;
// var3 var1
LinkedList.Node var3 = var1.next;
// item null
var1.item = null;
// next null
var1.next = null;
// var3
this.first = var3;
// var3 null， null
if (var3 == null) {
this.last = null;
}
// var1 ， var1 var3 null
else {
var3.prev = null;
}
//size
--this.size;
++this.modCount;
//
return var2;
} removeLast
끝 노드 요소 제거 last
public E removeLast() {
// LinkedList var1
LinkedList.Node var1 = this.last;
// null，
if (var1 == null) {
throw new NoSuchElementException();
}
// null
else {
return this.unlinkLast(var1);
}
}
private E unlinkLast(LinkedList.Node var1) {
// var1 var2
Object var2 = var1.item;
// var3
LinkedList.Node var3 = var1.prev;
// var1 item null
var1.item = null;
// var1 null
var1.prev = null;
// var3
this.last = var3;
// null
if (var3 == null) {
// null
this.first = null;
} else {
// var3 null
var3.next = null;
}
//size-1
--this.size;
++this.modCount;
// var2
return var2;
} addFirst 방법
첫 노드 추가
public void addFirst(E var1) {
this.linkFirst(var1);
}
private void linkFirst(E var1) {
// var2
LinkedList.Node var2 = this.first;
// var3 ， null（ null）， var2， var1
LinkedList.Node var3 = new LinkedList.Node((LinkedList.Node)null, var1, var2);
// var3 this.first
this.first = var3;
// null， var3
if (var2 == null) {
// LinkedList var3
this.last = var3;
} else {
//var2 null ， var3 var2
var2.prev = var3;
}
//size+1
++this.size;
++this.modCount;
}addLast 방법
addLast 방법, 새로운 요소 노드 를 링크 의 마지막 부분 으로 추가 합 니 다.
public void addLast(E var1) {
this.linkLast(var1);
}
void linkLast(E var1) {
// var2
LinkedList.Node var2 = this.last;
// var1 item node var3
LinkedList.Node var3 = new LinkedList.Node(var2, var1, (LinkedList.Node)null);
// var3 last
this.last = var3;
if (var2 == null) {
// var2 null， LinkedList ，
this.first = var3;
} else {
// var2 var3
var2.next = var3;
}
// +1
++this.size;
++this.modCount;
}
contains 와 index Of 방법
contains 방법 은 index Of 방법 을 호출 하여 요소 가 있 는 위치 아래 표 시 를 - 1 로 판단 하여 요소 가 존재 하 는 지 여 부 를 판단 합 니 다.
public boolean contains(Object var1) {
return this.indexOf(var1) != -1;
}
public int indexOf(Object var1) {
int var2 = 0;
LinkedList.Node var3;
// var1 null
if (var1 == null) {
// ， null，
for(var3 = this.first; var3 != null; var3 = var3.next) {
// null， var2
if (var3.item == null) {
return var2;
}
// +1
++var2;
}
}
// var1 null
else {
// ， null，
for(var3 = this.first; var3 != null; var3 = var3.next) {
// var1 var3，
if (var1.equals(var3.item)) {
return var2;
}
// +1
++var2;
}
}
return -1;
}size 방법
LinkList 길 이 를 되 돌려 줍 니 다.
public int size() {
return this.size;
}add 방법
이곳 의 add 방법 은 위의 addLast 실현 원리 와 같 습 니 다. 단지 하나의 true 를 더 되 돌 렸 을 뿐 입 니 다.
public boolean add(E var1) {
this.linkLast(var1);
return true;
}
void linkLast(E var1) {
// var2
LinkedList.Node var2 = this.last;
// var1 item node var3
LinkedList.Node var3 = new LinkedList.Node(var2, var1, (LinkedList.Node)null);
// var3 last
this.last = var3;
if (var2 == null) {
// var2 null， LinkedList ，
this.first = var3;
} else {
// var2 var3
var2.next = var3;
}
// +1
++this.size;
++this.modCount;
}
add 리 로드 방법
지정 한 아래 에 요 소 를 추가 합 니 다.
public void add(int var1, E var2) {
//
this.checkPositionIndex(var1);
// var1
if (var1 == this.size) {
//
this.linkLast(var2);
} else {
//
this.linkBefore(var2, this.node(var1));
}
}
void linkLast(E var1) {
// var2
LinkedList.Node var2 = this.last;
// var1 item node var3
LinkedList.Node var3 = new LinkedList.Node(var2, var1, (LinkedList.Node)null);
// var3 last
this.last = var3;
if (var2 == null) {
// var2 null， LinkedList ，
this.first = var3;
} else {
// var2 var3
var2.next = var3;
}
// +1
++this.size;
++this.modCount;
}
void linkBefore(E var1, LinkedList.Node var2) {
// var3
LinkedList.Node var3 = var2.prev;
// var4 ， var1 item，var3 ，var2
LinkedList.Node var4 = new LinkedList.Node(var3, var1, var2);
// var2 var4
var2.prev = var4;
// var3 Null，
if (var3 == null) {
// var4
this.first = var4;
} else {
// var3 var4
var3.next = var4;
}
// +1
++this.size;
++this.modCount;
} set 방법
아래 표 시 된 위치 에 요 소 를 설정 합 니 다.
public E set(int var1, E var2) {
//
this.checkElementIndex(var1);
//
LinkedList.Node var3 = this.node(var1);
// var4 item
Object var4 = var3.item;
// var1 item
var3.item = var2;
//
return var4;
}
//
private void checkElementIndex(int var1) {
// LinkedList ，
if (!this.isElementIndex(var1)) {
throw new IndexOutOfBoundsException(this.outOfBoundsMsg(var1));
}
}
//
private boolean isElementIndex(int var1) {
// 0 LinkedList size， true
return var1 >= 0 && var1 < this.size;
}
// LinkedList node
LinkedList.Node node(int var1) {
LinkedList.Node var2;
int var3;
if (var1 < this.size >> 1) {
var2 = this.first;
for(var3 = 0; var3 < var1; ++var3) {
var2 = var2.next;
}
return var2;
} else {
var2 = this.last;
for(var3 = this.size - 1; var3 > var1; --var3) {
var2 = var2.prev;
}
return var2;
}
} remove 방법
public boolean remove(Object var1) {
LinkedList.Node var2;
// var1 null
if (var1 == null) {
// ， Null，
for(var2 = this.first; var2 != null; var2 = var2.next) {
// item null
if (var2.item == null) {
this.unlink(var2);
return true;
}
}
}
// var1 null
else {
// ， Null，
for(var2 = this.first; var2 != null; var2 = var2.next) {
// var1 ，
if (var1.equals(var2.item)) {
this.unlink(var2);
return true;
}
}
}
return false;
}
//
E unlink(LinkedList.Node var1) {
// var2 var1.item
Object var2 = var1.item;
// var3 var1
LinkedList.Node var3 = var1.next;
// var4 var1
LinkedList.Node var4 = var1.prev;
// var4 null， var1 ， LinkedList var3
if (var4 == null) {
this.first = var3;
}
// var4 var3，var1 null
else {
var4.next = var3;
var1.prev = null;
}
// var3 null， var1 ， var4
if (var3 == null) {
this.last = var4;
}
// var3 Null, var3 var4,var1 null
else {
var3.prev = var4;
var1.next = null;
}
//var1 item null
var1.item = null;
//size-1
--this.size;
++this.modCount;
// var2
return var2;
}
remove 방법
remove 과부하 방법, 내부 호출 removeFirst 방법, 헤드 노드 제거
public E remove() {
return this.removeFirst();
}
poll 방법
poll 방법 내부 에서 unlink First 방법 을 사용 하여 머리 노드 를 제거 합 니 다. reove 와 removeFirst 는 머리 노드 를 찾 지 못 할 때 잘못 던 집 니 다. poll 은 머리 노드 를 찾 지 못 하면 null 로 돌아 갑 니 다.
public E poll() {
LinkedList.Node var1 = this.first;
return var1 == null ? null : this.unlinkFirst(var1);
}addAll 방법
원본 코드 를 연구 할 때 안에 있 는 변 수 는 대부분 var 1, var 2, var 3 인 것 을 발 견 했 습 니 다. 이해 하기 어렵 습 니 다. 저 는 변수 이름 을 직접 수 정 했 습 니 다.
public boolean addAll(Collection extends E> collection) {
// addAll
return this.addAll(this.size, collection);
}
// low，TODO
public boolean addAll(int size, Collection extends E> collection) {
// size
this.checkPositionIndex(size);
// Collection collection Array
Object[] tempArr = collection.toArray();
// tempArrLen tempArr
int tempArrLen= tempArr.length;
// 0， false
if (tempArrLen == 0) {
return false;
}
else {
LinkedList.Node var5;
LinkedList.Node var6;
//
if (size == this.size) {
var6 = null;
var5 = this.last;
} else {
var6 = this.node(size);
var5 = var6.prev;
}
Object[] var7 = tempArr;
int var8 = var3.length;
for(int i = 0; i < var8; ++i) {
Object var10 = var7[i];
LinkedList.Node var12 = new LinkedList.Node(var5, var10, (LinkedList.Node)null);
if (var5 == null) {
this.first = var12;
} else {
var5.next = var12;
}
var5 = var12;
}
if (var6 == null) {
this.last = var5;
} else {
var5.next = var6;
var6.prev = var5;
}
this.size += tempArrLen;
++this.modCount;
return true;
}
}
//
private void checkPositionIndex(int size) {
// size ，
if (!this.isPositionIndex(size)) {
throw new IndexOutOfBoundsException(this.outOfBoundsMsg(size));
}
}
//
private boolean isPositionIndex(int size) {
return size>= 0 && size <= this.size;
}
LinkedList.Node node(int var1) {
LinkedList.Node var2;
int var3;
if (var1 < this.size >> 1) {
var2 = this.first;
for(var3 = 0; var3 < var1; ++var3) {
var2 = var2.next;
}
return var2;
} else {
var2 = this.last;
for(var3 = this.size - 1; var3 > var1; --var3) {
var2 = var2.prev;
}
return var2;
}
} clear 방법
LinkedList 비우 기 방법
public void clear() {
// var
LinkedList.Node var2;
// LinkedList ， item、next、prev null
for(LinkedList.Node var1 = this.first; var1 != null; var1 = var2) {
var2 = var1.next;
var1.item = null;
var1.next = null;
var1.prev = null;
}
// LinkedList null
this.first = this.last = null;
//size 0
this.size = 0;
++this.modCount;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
