선형 표 ArrayList 와 LinkedList 소스 코드 상세 설명.
19538 단어 데이터 구조
묘사 하 다.
선형 표 추상 인터페이스, 모든 선형 표 는 이 인 터 페 이 스 를 실현 하 는 토대 에서 조작 해 야 한다.
인터페이스
package list;
/**
* Description: ，
*
* @ClassName: List
* @author
* @date 2018 8 13 10:45:13
*/
public interface ListInterface {
public void add(T newEntry);
public void add(Integer newPosition, T newEntry);
public T remove(int givePosition);
public void clear();
public T replace(int givenPosition, T newEntry);
public T getEntry(int givenPosition);
public T[] toArray();
public boolean contains(T anEntry);
public int getLength();
public boolean isEmpty();
}
ArrayList
인터페이스
/**
* java ArrayList list， AList
* ， ，
*/
public class AList implements ListInterface {
@Override
public void add(T newEntry) {
}
@Override
public void add(Integer newPosition, T newEntry) {
}
@Override
public T remove(int givePosition) {
return null;
}
@Override
public void clear() {
}
@Override
public T replace(int givenPosition, T newEntry) {
return null;
}
@Override
public T getEntry(int givenPosition) {
return null;
}
@Override
public T[] toArray() {
return null;
}
@Override
public boolean contains(T anEntry) {
return false;
}
@Override
public int getLength() {
return 0;
}
@Override
public boolean isEmpty() {
return false;
}
} 2. 실현 경로
Array 는 배열 이라는 뜻 이기 때문에 배열 을 사용 하여 List 를 실현 하 는 것 으로 쉽게 추측 할 수 있 습 니 다. 배열 에 몇 개의 유효 위 치 를 알 기 위해 int 값 으로 저장 합 니 다.초기 화 할 때 사용자 가 배열 용량 을 지정 하거나 기본 용량 을 사용 합 니 다.
주: Array List 나 다른 확장 용 기 를 사용 할 때 용량 을 정 하 는 것 을 강력 히 권장 합 니 다. 확장 시간 을 크게 절약 할 수 있 기 때 문 입 니 다.
public class AList implements ListInterface {
// ，
T[] list = null;
//
int numberOfEntries = 0;
// ( )，
static final int DEFAULT_CAPACITY = 27;
@SuppressWarnings("unchecked")
public AList(int initialCapacity) {
T[] tempList = (T[]) new Object[initialCapacity];
list = tempList;
numberOfEntries = 0;
}
public AList() {
this(DEFAULT_CAPACITY);
}
//
} add 방법 구현
아래 표 시 를 1 부터 사용 하기 때문에 Array List 와 혼동 하지 마 세 요 (0 부터).
주: Vectory 배열 은 두 배의 확장 을 사용 합 니 다. 즉, 현재 배열 공간 이 가득 차 면 우 리 는 두 배의 용량 의 배열 을 신청 한 다음 에 원래 의 배열 을 새 배열 로 복사 합 니 다.
Array List 의 배열 은 1.5 배 확장 을 사용 합 니 다. 즉, oldCapacity + (oldCapacity > > 1) 를 신청 합 니 다.
그래서 그 말 입 니 다. 대체적인 용량 을 정 하면 확장 횟수 를 대폭 줄 이 고 속 도 를 최적화 할 수 있 습 니 다. (아마 저 같은 초보 자만 이 용량 을 기본 으로 할 수 있 을 것 입 니 다)
@Override
public void add(T newEntry) {
// ArrayList ， 1 。
list[numberOfEntries + 1] = newEntry;
numberOfEntries++;
ensureCapacity();
//
// add(numberOfEntries+1,newEntry);
// ， ， 。 ， ( )
}
/**
*
*
* @param newPosition
* @param newEntry
*/
@Override
public void add(Integer newPosition, T newEntry) {
if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) {
if (newPosition <= numberOfEntries) {
makeRoom(newPosition); // 。
}
list[newPosition] = newEntry;
numberOfEntries++;
ensureCapacity(); //
} else {
throw new IndexOutOfBoundsException(" ， ");
}
}
/**
* @param newPosition
*/
private void makeRoom(Integer newPosition) {
assert (newPosition >= 1) && (newPosition <= newPosition + 1); // ， ， ， assert
int newIndex = newPosition;
int lastIndex = numberOfEntries;
for (int index = 0; index < newIndex; index++) {
list[index + 1] = list[index]; // ， ‘ ’
}
}
/**
*
*/
private void ensureCapacity() {
int capacity = list.length - 1;
if (numberOfEntries >= capacity) {
int newCapacity = 2 * capacity;
list = Arrays.copyOf(list, newCapacity + 1);
}
}간단 한 방법 을 실현 하 다
앞의 밑바닥 이 실현 되 는 것 을 알 면 다음 세 가지 방법의 실현 에 문제 가 없 을 것 이다.
@Override
public int getLength() {
return numberOfEntries;
}
@Override
public boolean isEmpty() {
return numberOfEntries == 0;
}
@Override
public void clear() {
list = null; // ， GC
numberOfEntries = 0;
}
remove 방법
배열 이 하나의 요 소 를 제거 한 후에 후속 요 소 는 바로 따라 가서 공간 을 메 웁 니 다.
주의: 이미 확 대 된 용량 은 반환 되 지 않 으 며 반환 할 필요 도 없습니다.
@Override
public T remove(int givePosition) {
if ((givePosition >= 1) && (givePosition <= numberOfEntries)) {
assert !isEmpty();
T result = list[givePosition];
if (givePosition < numberOfEntries) {
removeGap(givePosition); // ， ，
}
return result;
}
return null;
}
/**
* ， ，
*/
private void removeGap(int givePosition) {
assert (givePosition >= 1) && (givePosition < numberOfEntries);
int removedIndex = givePosition;
int lastIndex = numberOfEntries;
for (int index = givePosition; index < lastIndex; index++) {
list[index] = list[index + 1];
}
}toArray 방법의 실현
메모: Array List 밑 에 있 는 배열 로 직접 돌아 가지 마 세 요. 우 리 는 공간 을 새로 신청 하고 요 소 를 하나씩 넣 어야 합 니 다.list 로 돌아 가면 무 서운 일이 될 것 이다.
패 키 징 성: 방법 을 통 해 대상 의 도 메 인 을 바 꿀 수 있 습 니 다.배열 을 직접 되 돌려 주면 클 라 이언 트 프로그래머 는 대상 의 도 메 인 을 마음대로 변경 할 수 있 습 니 다.
@Override
public T[] toArray() {
/* T[] list
* ，
* list, 。
* List， 。
*/
T[] result = (T[]) new Object[numberOfEntries];
for (int index = 0; index < numberOfEntries; index++) {
result[index] = list[index + 1];
}
return result;
}나머지 방법
@Override
public T replace(int givenPosition, T newEntry) {
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
assert !isEmpty();
T oldEntry = list[givenPosition];
list[givenPosition] = newEntry;
return oldEntry;
}
//
return null;
}
@Override
public T getEntry(int givenPosition) {
// ， 。
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
assert !isEmpty();
return list[givenPosition];
}
//else ，
return null;
}
@Override
public boolean contains(T anEntry) {
boolean found = false;
int index = 1;
// ， 。
while (!found && (index <= numberOfEntries)) {
if (anEntry.equals(list[index])) {
found = true;
}
index++;
}
return found;
}
모든 방법 으로 소스 코드 를 실현 하 다.
package list;
import java.util.Arrays;
/**
* java ArrayList list， ArrayList
*/
public class AList implements ListInterface {
T[] list = null;
int numberOfEntries = 0;
static final int DEFAULT_CAPACITY = 27;
@SuppressWarnings("unchecked")
public AList(int initialCapacity) {
T[] tempList = (T[]) new Object[initialCapacity];
list = tempList;
numberOfEntries = 0;
}
public AList() {
this(DEFAULT_CAPACITY);
}
@Override
public void add(T newEntry) {
// ArrayList ， 1 。
list[numberOfEntries + 1] = newEntry;
numberOfEntries++;
ensureCapacity();
//
// add(numberOfEntries+1,newEntry);
// ， ， 。 ， ( )
}
/**
*
*
* @param newPosition
* @param newEntry
*/
@Override
public void add(Integer newPosition, T newEntry) {
if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) {
if (newPosition <= numberOfEntries) {
makeRoom(newPosition); // 。
}
list[newPosition] = newEntry;
numberOfEntries++;
ensureCapacity(); //
} else {
throw new IndexOutOfBoundsException(" ， ");
}
}
/**
* @param newPosition
*/
private void makeRoom(Integer newPosition) {
assert (newPosition >= 1) && (newPosition <= newPosition + 1); // ， ， ， assert
int newIndex = newPosition;
int lastIndex = numberOfEntries;
for (int index = 0; index < newIndex; index++) {
list[index + 1] = list[index]; // ， ‘ ’
}
}
@Override
public T remove(int givePosition) {
if ((givePosition >= 1) && (givePosition <= numberOfEntries)) {
assert !isEmpty();
T result = list[givePosition];
if (givePosition < numberOfEntries) {
removeGap(givePosition); // ， ，
}
return result;
}
return null;
}
/**
* ， ，
*
* @param givePosition
*/
private void removeGap(int givePosition) {
assert (givePosition >= 1) && (givePosition < numberOfEntries);
int removedIndex = givePosition;
int lastIndex = numberOfEntries;
for (int index = givePosition; index < lastIndex; index++) {
list[index] = list[index + 1];
}
}
@Override
public void clear() {
list = null; // ， GC
numberOfEntries = 0;
}
@Override
public T replace(int givenPosition, T newEntry) {
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
assert !isEmpty();
T oldEntry = list[givenPosition];
list[givenPosition] = newEntry;
return oldEntry;
}
return null;
}
@Override
public T getEntry(int givenPosition) {
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
assert !isEmpty();
return list[givenPosition];
}
//else ，
return null;
}
@Override
public T[] toArray() {
T[] result = (T[]) new Object[numberOfEntries];
for (int index = 0; index < numberOfEntries; index++) {
result[index] = list[index + 1];
}
return result;
}
@Override
public boolean contains(T anEntry) {
boolean found = false;
int index = 1;
while (!found && (index <= numberOfEntries)) {
if (anEntry.equals(list[index])) {
found = true;
}
index++;
}
return found;
}
@Override
public int getLength() {
return numberOfEntries;
}
@Override
public boolean isEmpty() {
return numberOfEntries == 0;
}
/**
*
*/
private void ensureCapacity() {
int capacity = list.length - 1;
if (numberOfEntries >= capacity) {
int newCapacity = 2 * capacity;
list = Arrays.copyOf(list, newCapacity + 1);
}
}
} 총결산
Array List 가 주의해 야 할 부분 이 있다 면.
4. 567917. 1.5 배 확대 되 고 사상 이 좋 지만 시간 을 낭비 하기 때문에 프로그래머 는 사용 할 공간의 대략적인 상 계 를 최대한 추산 한 다음 에 초기 화 할 때 용량 을 지정 합 니 다
4. 567917. toArray 때 밑 에 배열 이 있 지만 밑 에 있 는 배열 로 돌아 갈 수 없습니다
4. 567917. clear 시 배열 인용 을 null 로 직접 설정 하면 GC 는 이 메모리 로 회수 할 수 있 습 니 다
덧 붙 여 몇 마디 하 자 면, 두 배의 확장 은 Vector 가 사용 하 는 방법 이 고, ArrayList 는 1.5 배의 확장 을 사용 하 며, vector 의 방법 은 라인 안전 을 실현 하 였 으 나, ArrayLust 가 없 기 때문에 라인 안전 을 요구 하지 않 는 상황 에서 ArrayList 를 사용 하면 코드 의 운행 속 도 를 가속 화 할 수 있다.
LinkedList
실현 인터페이스
package list;
/**
* LinkedList， LList，
* 1 ， java （ 0 ）
*/
public class LList implements ListInterface {
@Override
public void add(T newEntry) {
}
@Override
public void add(Integer newPosition, T newEntry) {
}
@Override
public T remove(int givePosition) {
return null;
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public T replace(int givenPosition, T newEntry) {
return null;
}
@Override
public T getEntry(int givenPosition) {
return null;
}
@Override
public T[] toArray() {
return null;
}
@Override
public boolean contains(T anEntry) {
return false;
}
@Override
public int getLength() {
return 0;
}
@Override
public boolean isEmpty() {
return false;
}
} 밑바닥 실현
체인 을 뚜렷하게 사용 하기 때문에 우 리 는 결점 류 노드 를 정의 해 야 한다.
그 다음 에 우 리 는 처음에 단 방향 링크 를 사용 하여 실현 과 이해 에 유리 하고 그 후에 일부 코드 를 수정 하여 양 방향 링크 로 만 들 었 다.그리고 양 방향 링크 특유 의 조작 을 제공 합 니 다.
public class LList implements ListInterface {
int size;
Node firstNode;
// ， 。
public LList() {
size = 0;
firstNode = null;
}
//
// ， next data
class Node {
T data;
Node next;
public Node() {
}
public Node(T data) {
this(data, null);
}
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
} 핵심 방법: add 의 실현
@Override
public void add(T newEntry) {
//
add(size, newEntry);
}
@Override
public void add(Integer newPosition, T newEntry) {
Node newNode = new Node(newEntry);
if (newPosition == 1) {
//
newNode.next = firstNode;
firstNode = newNode;
} else if (newPosition > 1 && newPosition <= size) {
Node beforeNode = firstNode;
int count = 1;
// ，
while (count != newPosition - 1) {
beforeNode = beforeNode.next;
count++;
}
//
newNode.next = beforeNode.next; //
beforeNode.next = newNode;
} else {
throw new IndexOutOfBoundsException(" ");
}
}
LinkedList 모든 원본 코드
package list;
/**
* LinkedList， LList，
* 1 ， java （ 0 ）
*/
public class LList implements ListInterface {
private int size;
private Node firstNode;
public LList() {
size = 0;
firstNode = null;
}
@Override
public void add(T newEntry) {
//
add(size, newEntry);
}
@Override
public void add(Integer newPosition, T newEntry) {
Node newNode = new Node(newEntry);
if (newPosition == 1) {
//
newNode.next = firstNode;
firstNode = newNode;
} else if (newPosition > 1 && newPosition <= size) {
Node beforeNode = firstNode;
int count = 1;
// ，
while (count != newPosition - 1) {
beforeNode = beforeNode.next;
count++;
}
//
newNode.next = beforeNode.next; //
beforeNode.next = newNode;
} else {
throw new IndexOutOfBoundsException(" ");
}
}
@Override
public T remove(int givePosition) {
T result;
if ((givePosition >= 1) && (givePosition <= size)) {
assert !isEmpty();
if (givePosition == 1) {
//
result = firstNode.data;
firstNode = firstNode.next;
} else {
Node nodeBefore = getNodeAt(givePosition - 1);
Node nodeToRemove = nodeBefore.next;
result = nodeBefore.data;
Node nodeAfter = nodeToRemove.next;
nodeBefore.next = nodeAfter; //
}
size--;
return result;
} else
throw new IndexOutOfBoundsException(" ");
}
private Node getNodeAt(int i) {
if (i > 0 && i <= size) {
Node curNode = firstNode;
for (int j = 0; j < i; j++)
curNode = curNode.next;
return curNode;
} else
throw new IndexOutOfBoundsException(" ");
}
@Override
public void clear() {
size = 0;
firstNode = null;
}
@Override
public T replace(int givenPosition, T newEntry) {
// getNodeAt
Node nodeToReplace = getNodeAt(givenPosition);
T result = nodeToReplace.data;
nodeToReplace.data = newEntry;
return result;
}
@Override
public T getEntry(int givenPosition) {
return getNodeAt(givenPosition).data;
}
@Override
public T[] toArray() {
T[] result = (T[]) new Object[size];
Node curNode = firstNode;
for (int i = 0; i < size; i++) {
result[i] = curNode.data;
}
return null;
}
@Override
public boolean contains(T anEntry) {
Node curNode = firstNode;
boolean found = false;
while (!found && curNode != null) {
if (curNode.data.equals(anEntry)) {
found = true;
}
curNode = curNode.next;
}
return found;
}
@Override
public int getLength() {
return size;
}
@Override
public boolean isEmpty() {
boolean result = false;
// ， ， 。 。
if (size == 0) {
assert firstNode == null;
result = true;
} else {
assert firstNode != null;
result = false;
}
return result;
}
class Node {
T data;
Node next;
public Node() {
}
public Node(T data) {
this(data, null);
}
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
}
다음은 단 방향 링크 를 양 방향 링크 로 바 꾸 면 됩 니 다. "getPrevNode (), addFirst Node ()" 와 같은 방법 을 추가 하여 add () 를 수정 하면 됩 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
