데이터 구조 와 알고리즘 - 배열
37694 단어 데이터 구조 와 알고리즘
배열 (Array) 은 선형 표 데이터 구조 이다.그것 은 같은 유형의 데 이 터 를 저장 하기 위해 연속 적 인 메모리 공간 을 사용한다.
2. 특징
2.1 선형 표
선형 표 는 데이터 가 하나의 선 처럼 배열 되 어 있 는 구조 이다.모든 선형 표 의 데 이 터 는 최대 앞 과 뒤의 두 방향 만 있다.사실은 배열 을 제외 하고 링크, 대기 열, 스 택 등 도 선형 표 구조 이다.
2.2 메모리 공간 연속, 데이터 형식 동일
현재 요소 주소 = 배열 의 첫 번 째 주소 + 요소 바이트 크기 는 8727 ° 배열 아래 에 현재 요소 주 소 를 표시 합 니 다 = 배열 의 첫 번 째 주소 + 요소 바이트 크기 \ ast 배열 아래 에 현재 요소 주 소 를 표시 합 니 다 = 배열 의 첫 번 째 주소 + 요소 바이트 크기 는 8727 ° 배열 아래 에 표 시 됩 니 다.
2.3 효율 적 인 랜 덤 액세스, 비효 율 적 인 삽입 과 삭제
메모리 공간 이 연속 되 기 때문에 방문 은 한 번 의 주소 지정 을 통 해 해당 하 는 데 이 터 를 찾 을 수 있 으 며, 삽입 과 삭제 후 후속 요 소 를 여러 번 데이터 이전 해 야 합 니 다.
접근 시간 복잡 도: O (1)
삽입 및 삭제 시간 복잡 도: O (n)
3. 배열 과 용기 비교
3.1 용기 우위
여러 배열 의 조작 방법 을 밀봉 하여 개발 에 편리 하 다.
동적 확장 지원
3.2 배열 우위
기본 형식 저장 가능
다 차원 배열 이 더욱 직관 적 임 을 나타 낸다.
4. 기타
4.1 배열 아래 표 시 는 왜 0 에서 시작 합 니까?
무 작위 접근 (요소 메모리 주소 계산) 을 편리 하 게 하기 위해 서 아래 표 시 는 1 부터 한 번 더 감법 작업 을 할 것 입 니 다.
4.2 손 찢 기 배열
package com.company;
import java.util.Arrays;
/**
* ：
*
* @author liuchaoyong
* @version 1.0
* @date 2020/1/9 11:18
*/
public class MyArrayList<E> {
/**
*
*/
private static final Object[] EMPTY_ELEMENTDATA = {
};
/**
* ， ArrayList ， ，
*
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
};
/**
*
*/
private static final int DEFAULT_CAPACITY = 10;
/**
*
*/
transient Object[] elementData;
/**
* （ ， ， 8 ，
* ， -8）
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList ， elementData ，
* elementData
*/
private int size;
/**
*
*/
public MyArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
*
* >0
* =0
* <0
*/
public MyArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
/**
*
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* ，
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
/**
*
*/
public boolean add(E element) {
ensureCapacityInternal(size + 1);
elementData[size++] = element;
return true;
}
/**
*
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
// index index+1
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
*
*/
public E remove(int index) {
rangeCheck(index);
E oldValue = elementData(index);
int numMoved = size - index - 1;
// index+1 index ， gc
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
return oldValue;
}
/**
*
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++) {
if (elementData[index] == null) {
fastRemove(index);
return true;
}
}
} else {
for (int index = 0; index < size; index++) {
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
}
return false;
}
/**
*
*/
public boolean contains (Object o){
return indexOf(o) >= 0;
}
/**
*
*/
public int indexOf(Object o) {
if (o == null) {
for (int index = 0; index < size; index++) {
if (elementData[index] == null) {
return index;
}
}
} else {
for (int index = 0; index < size; index++) {
if (o.equals(elementData[index])) {
return index;
}
}
}
return -1;
}
/**
*
*/
public int lastIndexOf(Object o){
if (o == null) {
for (int index = size-1; index > 0; index--) {
if (elementData[index] == null) {
return index;
}
}
} else {
for (int index = size-1; index > 0; index--) {
if (o.equals(elementData[index])) {
return index;
}
}
}
return -1;
}
/**
* ArrayList
*/
public int size() {
return size;
}
/**
* ArrayList
*/
public boolean isEmpty() {
return size == 0;
}
/**
*
*/
public void clear() {
for (int index = 0; index < size; index++) {
elementData[index] = null;
}
size = 0;
}
/**
*
*/
private void rangeCheck(int index) {
if (index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
/**
*
*/
private void rangeCheckForAdd(int index) {
//rangeCheck
//System.arraycopy() ， index<0
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
/**
*
*/
@SuppressWarnings("unchecked")
private E elementData(int index) {
return (E) elementData[index];
}
/**
* ， ，
*/
private void fastRemove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
}
/**
*
*/
private void ensureCapacityInternal(int minCapacity) {
if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
}
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
/**
*
*/
private void grow(int minCapacity) {
//
int oldCapacity = elementData.length;
// 1.5 （ 1.5， ， ）
int newCapacity = oldCapacity + (oldCapacity >> 1);
// ， ，
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
}
// ， ，
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0) {
throw new OutOfMemoryError();
}
// ， Integer.MAX_VALUE （ ）,
newCapacity = minCapacity > MAX_ARRAY_SIZE ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
Object[] copy = new Object[newCapacity];
System.arraycopy(elementData, 0, copy, 0,
elementData.length);
elementData = copy;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
