1. 배열 기반 리스트
배열의 기본 특징
배열의 구조상의 특징
- 같은 타입의 여러 변수를 일렬로 묶은, 가장 기본적인 형태의 자료구조
- 배열의 크기는 변경 불가(정적 할당)
: 배열에 저장하려는 데이터의 개수가 기존 크기를 초과하면 새로운 배열을 생성하는 작업이 요구됨
배열의 성능상의 특징
- 데이터 접근 시간이 빠름
: 인덱스를 통해 배열의 특정 위치에 바로 접근 가능하기 때문- 차례대로 데이터를 추가 or 마지막에서부터 데이터를 삭제하는 속도가 빠름
- 배열의 중간에 데이터 삽입/삭제 시 많은 시간을 소요
: 특정 위치에서의 빈자리를 만들거나 없애기 위해 다른 데이터들의 이동을 수반하기 때문- 배열에 저장할 데이터가 많을수록 메모리 낭비 증가
: 배열의 크기가 일단 확정되면, 해당 배열의 크기는 더 이상 변경할 수 없기 때문
배열 기반 리스트 기능 구현 코드
- 전체 구현 코드는 여기에서 확인 가능
package arraylist;
public class ArrayList {
// 별도의 설정이 없을 시 배열 리스트의 크기
private static final int INITIAL_CAPACITY = 10;
private int size;
private final Object[] elementData;
// 배열 리스트 생성
public ArrayList() {
this.elementData = new Object[INITIAL_CAPACITY];
this.size = 0;
}
public ArrayList(int initialCapacity) {
this.elementData = new Object[initialCapacity];
this.size = 0;
}
// 배열 리스트의 맨 끝에 데이터 추가
public void add(Object element) {
elementData[size++] = element;
}
// 배열 리스트의 지정된 위치에 데이터 삽입
public void add(int index, Object element) {
// 1. 저장할 위치 이후의 데이터는 모두 오른쪽으로 1칸씩 이동
for (int i = size-1; i >= index; i--) {
elementData[i+1] = elementData[i];
}
// 2. 지정된 인덱스에 데이터 저장
elementData[index] = element;
// 3. 배열 리스트의 크기는 1 증가
size++;
}
// 지정된 위치에 저장된 데이터 삭제
public Object remove(int index) {
// 1. 삭제할 데이터는 별도로 저장
Object element = elementData[index];
// 2. 데이터 삭제 시 삭제할 데이터 이후의 데이터는 모두 왼쪽으로 1칸씩 이동
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i+1];
}
// 3. 배열 리스트의 크기는 1 감소
size--;
// 4. 삭제된 데이터 반환
return element;
}
// 지정된 위치에 저장된 데이터 가져오기
public Object get(int index) {
return elementData[index];
}
// 배열 리스트에 저장된 데이터의 개수 = 배열 리스트의 크기
public int getSize() {
return size;
}
// 배열 리스트에 저장된 데이터 현황을 문자열 형태로 반환
@Override
public String toString() {
StringBuilder result = new StringBuilder();
for (int i = 0; i < size; i++) {
result.append(elementData[i]);
if (i < size - 1) {
result.append(",");
}
}
return String.format("[%s]", result);
}
}배열 리스트의 주요 메서드 정리
ArrayList()/ArrayList(int capacity)
- 생성자를 이용하여 배열 리스트에 최대로 저장 가능한 데이터의 용량과
배열 리스트의 현재 크기를 초기화- 별도의 인자를 지정하지 않았을 경우 길이가 10인 배열 리스트 생성
void add(Object element)/void add(int index, Object element)
- 배열 리스트의 맨 끝에 새로운 데이터를 추가하거나 지정한 인덱스에 새로운 데이터를 삽입
- 메서드 오버로딩 활용
Object remove(int index)
- 지정된 인덱스에 저장된 데이터를 삭제한 후 반환
- 중복된 데이터가 저장될 수 있기 때문에 데이터가 아닌 인덱스 값을 이용한 데이터 삭제
Object get(int index)
- 지정한 인덱스에 저장된 데이터를 반환
int getSize()
- 리스트의 현재 크기 반환
- 리스트에 현재 저장된 개수를
실행 결과
package arraylist;
public class ArrayListMain {
public static void main(String[] args) {
ArrayList list = new ArrayList();
// 데이터 추가
for (int i = 1; i <= 5; i++) {
list.add(i);
}
System.out.printf("listSize: %d\n", list.getSize());
System.out.printf("list: %s\n\n", list);
// 지정한 인덱스에 데이터 삽입
list.add(3, 6);
list.add(6);
System.out.printf("listSize: %d\n", list.getSize());
System.out.printf("list: %s\n\n", list);
// 리스트의 각 인덱스별 데이터 출력
for (int i = 0; i < list.getSize(); i++) {
System.out.printf("list[%d]: %d\n", i, (int) list.get(i));
}
System.out.println();
// 특정 데이터 삭제 결과 출력
System.out.printf("removedData: %d\n", (int) list.remove(2));
System.out.printf("listSize: %d\n", list.getSize());
System.out.printf("list: %s\n", list);
}
}
Reference
- Do-it! 자료구조와 함께 배우는 알고리즘 입문(Bohyoh Shibata 지음, 강민 옮김)
- 윤성우의 열혈 자료구조(윤성우 지음)
