Array
배열: 동일한 자료형를 가지고 연속된 공간에 저장되는 데이터(element)의 집합
길이
배열의 길이는 고정이며 변경할 수 없다.
메모리 할당
- 배열의 값은 메모리에 연속적으로 저장된다.
- 논리적 저장 순서 = 물리적 저장 순서
- 데이터의 자료형 크기 * 배열의 길이로 메모리의 크기가 결정된다.
- 자바 지역 변수는 Stack 영역에 저장되고, 배열은 실제로 Heap 영역에 레퍼런스형으로 할당되어 변수가 배열의 시작 주소(참조값)를 기억한다.
new연산자(동적 메모리 할당 연산자)로 생성된 데이터 → heap
- 연속된 빈 공간이 없다면 생성되지 않는다.
선언 & 생성
- 선언:
int[] numbers - 생성:
numbers = new int[3]- 배열을 처음 생성할 때 초기화를 할 값들의 집합 또는 배열크기를 지정해야 한다.
// 1. 초기값으로 선언 및 생성
int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; // 1차원 배열
// 2. 배열 크기로 선언 및 생성
String[][] sentences = new String[3][10]; // 2차원 배열
// 3. 선언 후 초기화, 값의 개수에 의해 배열의 길이 자동 결정
Object[] objects;
objects = new Object[] {new Object(), new Object()};접근
Indexing(원소의 일련번호)으로 배열의 원소에 무작위 접근(random access)이 가능하다.
int[] numbers = new int[3]; // 자료형의 기본값으로 초기화됨
for (int i = 0; i < numbers.length; i++) {
numbers[i] = i * i; // 원하는 값으로 저장(덮어쓰기)
}
int n = numbers[2]; // index 2로 접근삽입 & 삭제 & 검색
배열의 모든 인덱스에 접근해야 한다.
-
[1, 2, 3, 4, 5]의 2번째 자리(index = 1)에 0을 삽입하고 싶다.
특정 원소를 삽입할 때 배열의 마지막 원소부터 뒤로 이동한다.
index = 4 → [1, 2, 3, 4, 4]
index = 3 → [1, 2, 3, 3, 4]
index = 2 → [1, 2, 2, 3, 4] → [1, 0, 2, 3, 4]
-
[1, 2, 3, 4, 5]의 원소 2(index = 1)를 삭제하고 싶다.
삭제하고자하는 원소의 index로 먼저 이동
index = 1 → [1, 3, 3, 4, 5]
index = 2 → [1, 3, 4, 4, 5]
index = 3 → [1, 3, 4, 5, 5]
-
특정 값 검색
배열의 원소값이 정렬되어있지 않은 경우 첫번째 원소부터 순회하면서 검색하고자 하는 값과 비교해야 한다.
출력
// 1. for문
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + ", ");
}
// 2. Arrays method
System.out.println(Arrays.toString(numbers));Linked List
연결 리스트: 데이터와 포인터를 가진 노드(node)들이 한 줄로 연결된 자료구조
특징
- 원소 삽입, 삭제를 통해 연결 리스트의 길이가 변할 수 있다.
- 논리적인 저장 순서와 물리적 저장 순서가 일치하지 않다.
- Tree의 기본 자료구조
선언 & 생성 & 대표 메서드
LinkedList objects = new LinkedList(); // 타입 설정 X, Object로 선언
LinkedList<Integer> numbers = new LinkedList<>(); // 생성시 자료형 생략 가능
LinkedList<String> sentences = new LinkedList<>(Arrays.asList("ab", "cd", "ef"));
sentences.add("gh");
sentences.remove("cd"); // value 기반 삭제
sentences.remove(0); // index 기반 삭제접근
특정 원소에 접근하기 위해 첫 노드부터 순차 접근(sequential access)이 필요하다. random access 접근 불가.
삽입 & 삭제 & 검색
Array(배열)처럼 삽입, 삭제시 전체 인덱스가 밀리거나 당겨지지 않으며, 앞뒤 노드만 영향을 받는다.
| 변경 지점 | 시간 복잡도 |
|---|---|
| search | O(n) |
| first, last 삽입/삭제 | O(1) |
| index 기반 삽입/삭제 | O(n) |
| clear | O(n) |
index를 기반으로 삽입/삭제를 하고자 한다면 원하는 위치를 찾는 검색 과정이 필요하다.
에러
자바의 경우 배열/리스트의 크기를 벗어나거나 음수 인덱스에 접근하려할 경우 ArrayIndexOutOfBoundsException을 런타임에 발생시킨다.
int[] arrayNumbers = new int[n]; // index: 0 ~ n-1
// int errorIndexNumber = arrayNumbers[n];
List<Integer> listNumbers = new ArrayList<>();
// listNumbers.get(0);