이전 기사에서는 ArrayList의 기본 구현을 분석하고 ArrayList의 기본 구현이 배열을 기반으로한다는 것을 알았으므로 느리게 삽입 및 삭제하면서 빠른 검색 및 수정의 특성을 가지고 있습니다. 이 기사에서 소개 된 링크드리스트는 목록 인터페이스의 또 다른 구현입니다. 기본 레이어는 양방향 링크 목록을 기반으로합니다. 따라서 느린 검색 및 수정으로 빠른 삽입 및 삭제의 특성이 있습니다. 또한, 큐 및 스택의 기능은 양방향 링크 된 목록의 작동을 통해 실현 될 수 있습니다. Linkedlist의 기본 구조는 아래 그림에 나와 있습니다.
F는 헤드 노드 참조를 나타내고, l은 테일 노드 참조를 나타내고, 링크 된 목록의 각 노드는 세 가지 요소, 즉 전방 노드 참조 (p), 노드 요소 값 (e) 및 후속 노드 참조 (n)을 갖는다. 노드는 내부 클래스 노드로 표시되며 내부 구조를 살펴 보겠습니다.
// 노드 내부 클래스 비공개 정적 클래스 노드 <e> {e 항목; // 요소 노드 <E> 다음; // 다음 노드 노드 <e> 이전; // 이전 노드 노드 (Node <e> prev, e element, node <e> next) {this.item = element; this.next = 다음; this.prev = 이전; }}내부 클래스 노드는 실제로 3 개의 멤버 변수와 생성자 만있는 매우 간단합니다. 항목은 노드의 값을 나타내고, 다음은 다음 노드에 대한 참조이며, 이전은 이전 노드에 대한 참조입니다. 이 세 값은 생성자를 통해 전달됩니다. 다음으로 LinkedList의 멤버 변수 및 생성자를 살펴 보겠습니다.
// 세트 요소의 수는 int size = 0; // 헤더 노드 참조 과도 노드 <E> 첫 번째; // 테일 노드 참조 과도 노드 <E> 마지막; // 매개 변수가없는 생성자 public inlinkedList () {} // 제작자가 외부 링크 링크리스트 (collection <? c) {extends e (extends e) {) addall (c);}LinkedList는 헤더 노드에 대한 참조와 테일 노드에 대한 참조를 보유합니다. 그것은 두 개의 생성자가 있고, 하나는 매개 변수가없는 생성자이고, 다른 하나는 외부 컬렉션에 전달되는 생성자입니다. ArrayList와 달리 LinkedList는 초기 크기 생성자를 지정하지 않습니다. 추가, 삭제, 수정 및 검색 방법을 확인하십시오.
// 추가 (추가) public boolean add (e e) {// LinkLast (e) 추가; return true;} // add (삽입) public void add (int index, e element) {checkpositionIndex (index); if (index == size) {// linklast (element) 추가; } else {// linkbefore (element, node (index)); }} // delete (give index) public e 제거 (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); 진실을 반환하십시오. }}} else {// tranquility 링크 목록 (node <e> x = first; x! = null; x = x.next) {if (o.equals (x.item)) {// 삭제 Unlink (x); 진실을 반환하십시오. }}} return false;} // public e set (int index, e element) {// 첨자가 합법적 인 checkElementIndex (index)인지 확인합니다. // 지정된 첨자 노드의 노드 참조를 가져옵니다 <e> x = 노드 (index); // 지정된 첨자 노드 e OldVal = X.Item의 값을 가져옵니다. // 노드 요소를 새 값으로 설정 X.ITEM = 요소; // 이전 값을 반환하십시오. oldVal;} // public e get (int index) {// 첨자가 합법적 인 checkElementIndex (index)인지 확인; // 지정된 첨자 노드의 값을 반환합니다. 리턴 노드 (index) .item;}LinkedList에서 요소를 추가하는 방법은 주로 두 가지 메소드 LinkLast 및 LinkBefore를 호출하는 것입니다. LinkLast 메소드는 링크 된 목록 뒤에 요소를 연결하는 것이며 LinkBefore 메소드는 링크 된 목록의 중간에 요소를 삽입하는 것입니다. LinkedList의 삭제 방법은 링크되지 않은 메소드를 호출하여 링크 된 목록에서 요소를 제거합니다. 링크 된 목록의 삽입 및 삭제 작업의 핵심 코드를 살펴 보겠습니다.
// 지정된 노드 void inlinkbeforefore (e e, node <e> succ)에 연결하기 전에 {// 주어진 노드 최종 노드의 이전 노드 참조 <e> pred = succ.prev; // 새 노드를 생성, 새 노드의 이전 노드 참조는 주어진 노드의 이전 노드를 가리 킵니다. // 새 노드의 다음 노드의 참조는 주어진 노드 최종 노드 <e> newnode = new Node <> (pred, e, succ)를 가리 킵니다. // 주어진 노드의 이전 노드 참조를 새 노드 succ.prev = newnode; // 주어진 노드의 이전 노드가 비어 있으면 주어진 노드가 헤더 노드 If (pred == null) {// 헤더 노드 참조를 새 노드 First = newNode에 가리키는 것을 의미합니다. } else {// 그렇지 않으면 새 노드 pred.next = newNode에 대한 다음 노드 참조를 가리 킵니다. } // 세트 요소의 수를 추가하여 하나의 크기 ++; // 수정 수를 추가하여 하나의 modcount ++; } // 지정된 노드 E UNLINC (NODE <E> X)를 내립니다. {// 주어진 노드의 요소를 가져옵니다. 최종 E 요소 = X.Item; // 주어진 노드 최종 노드의 다음 노드에 대한 참조를 가져옵니다. <E> next = X.Next; // 주어진 노드 최종 노드의 이전 노드에 대한 참조를 가져옵니다 <E> prev = x.prev; // 주어진 노드의 이전 노드가 비어있는 경우, 설명 : 주어진 노드는 헤더 노드입니다. if (prev == null) {// 헤더 노드 참조가 주어진 노드의 다음 노드에 대한 참조를 가리 킵니다. } else {// 주어진 노드의 후속 노드를 가리키는 이전 노드의 후속 노드를 참조하십시오. // 주어진 노드의 이전 노드를 참조하십시오 x.prev = null; } // 주어진 노드의 다음 노드가 비어 있으면 주어진 노드가 꼬리 노드임을 의미합니다. (다음 == null) {// 주어진 노드의 이전 노드에 대한 테일 노드 참조를 가리키십시오. } else {// 주어진 노드의 이전 노드를 가리키는 다음 노드의 전방 노드를 참조하십시오. prev = prev; x.next = null; } // 주어진 노드 x.item = null의 요소를 비우십시오. // 크기별로 세트 요소의 수를 빼십시오. // modCount 추가 ++; 반환 요소;} LinkBefore 및 UnRink는 노드와 제거 노드를 제거하는 대표적인 작업입니다. 양쪽 끝에서 노드를 연결하고 제거하는 다른 방법은 유사하므로 Linkbefore 및 무제한 메소드에 중점을 둡니다.
Method 이전의 프로세스 다이어그램 :
무제한 방법의 프로세스 다이어그램 :
위의 그림을 통해 링크 된 목록의 삽입 및 삭제 작업의 시간 복잡성은 O (1)이며 링크 된 목록의 검색 및 수정 작업은 링크 된 목록을 가로 지르고 요소를 찾습니다. 두 작업을 모두 Node (Int Index) 메소드라고하며 요소를 찾아 첨자를 통해 요소를 찾는 방법을 확인합니다.
// 노드 노드 <e> 노드 (int index) {// 인덱스가 링크 된 목록의 전반전에있는 경우 처음부터 확인 if (index <(size >> 1)) {node <e> x = first; for (int i = 0; i <index; i ++) {x = x.next; } return x; } else {// 색인이 링크 된 목록의 후반에있는 경우 끝 노드 <e> x = last에서 확인하십시오. for (int i = size-1; i> index; i-) {x = x.prev; } return x; }} 위시를 위치시킬 때 먼저 링크 목록의 상단 절반 또는 하단에 있는지 확인하십시오. 그것이 상반부에 있다면 처음부터 시작하고 하반부라면 끝에서 시작하십시오. 따라서 첨자 검색 및 수정 작동의 시간 복잡성은 O (N/2)입니다. 양방향 연결된 목록의 작동을 통해 단일 항목 대기열, 양방향 대기열 및 스택의 기능도 실현 될 수 있습니다.
일방 통행 대기열 작동 :
// 헤더 노드를 가져옵니다 public e peek () {Final Node <e> f = 첫 번째; return (f == null)? NULL : F.ITEM;} // 헤더 노드 공개 e 요소 () {return getFirst ();} // 헤더 노드 public e poll () {Final Node <e> f = 첫 번째; return (f == null)? NULL : UnlinkFirst (F);} // 헤더 노드를 제거하여 ex remove () {return reftionfirst ();} // 대기열 끝에서 노드 추가 공개 부울 제안 (e e) {return add (e);}양방향 대기열 작동 :
// 공개 부울 혜택 추가 (e e) {addfirst (e); return true;} // 공개 부울 제안 (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;}스택 작동 :
// 스택을 공개 공개 void push (e e) {addfirst (e);} // 스택 공개 e pop () {return removefirst ();} 편도 대기열, 양방향 대기열 또는 스택이든 실제로 링크 된 목록의 헤드 및 꼬리 노드에서 작동합니다. 이들의 구현은 addfirst (), addlast (), removefirst () 및 removelast ()의 네 가지 방법을 기반으로합니다. 해당 작업은 LinkBefore () 및 Unlink ()와 유사합니다. 하나는 링크 된 목록의 양쪽 끝에서 작동하고 다른 하나는 링크 된 목록의 중간에서 작동하는 것입니다. 이 네 가지 방법은 intructe () 및 Unlink () 메소드의 특별한 경우이므로 내부 구현을 이해하는 것은 어렵지 않으므로 여기에 소개하지 않을 것입니다. 이 시점에서 LinkedList에 대한 분석이 끝날 예정이며 전체 텍스트의 핵심 사항을 요약합니다.
1. Linkedlist는 양방향 링크 목록을 기반으로 구현됩니다. 추가, 삭제, 수정 및 검색 방법이든 큐 및 스택의 구현에 관계없이 작동 노드를 통해 구현할 수 있습니다.
2. Linkedlist는 용량을 미리 지정할 필요가 없습니다. 링크 된 목록 작업을 기반으로 컬렉션의 용량은 요소 추가에 따라 자동으로 증가합니다.
3. LinkedList가 삭제 된 후 컬렉션이 차지하는 메모리가 자동으로 줄어들고 ArrayList와 같은 TrimTosize () 메소드를 호출 할 필요가 없습니다.
4. 링크 사전 목록의 모든 방법은 동기화되지 않으므로 스레드 안전하지 않으므로 다중 스레드 환경에서는 피해야합니다.
5. 위의 분석은 JDK1.7을 기반으로하며 다른 버전에는 약간의 차이가 있으므로 일반화 할 수 없습니다.
위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.