[자바의 정석] ArrayList/LinkedList
1. ArrayList : 배열 기반 리스트
https://www.youtube.com/watch?v=_2e-cgwMOyc
▶ Vector를 개선. *차이점) Vector는 동기화 가능/ ArrayList는 동기화X
▶ 생성자
| ArrayList() | |
| ArrayList(Collection c) | 컬렉션을 넣으면 배열리스트로 변경됨 |
| ArrayList(int initalCapacity) | 저장하려는 갯수만큼 길이 지정 |
* 저장갯수를 지정해주지 않으면 배열이 늘어나고 줄어들 때마다 배열이 새로 생성되기에 성능 떨어진다.
▶ 메소드
| 추가 | 삭제 | 검색 | 기타 |
| add(Object o) : boolean add(int index, Object element) addAll(컬렉션) addAll(index, 컬렉션) |
remove(Object o) : boolean remove(int index) removeAll(Collection c) clear() |
indexOf() : int <- index lastIndexOf() : int contains() get(int index) : Object set(index, Object) : Object |
subList() toArray() : Object[] isEmpty() trimToSize() - 빈공간제거 size() - 갯수 반환 |
▶ ArrayList에서 객체를 추가하거나 삭제할 때 배열의 복사가 이루어질 수 있다.
★ 삭제할 때, Last in First Out 방식을 취할 경우, 배열 복사가 발생하지 않는다. (성능 ↑)
[예제 연습1]
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class ArrayListEx2 {
public static void main(String[] args) {
final int LIMIT = 10;
String source = "0123456789abcdefghijABCDEFGHIJ!@#$%^&*()ZZZ";
int length = source.length();
List list = new ArrayList(length/LIMIT+10);
for(int i = 0; i < length; i+=LIMIT) {
if(i+LIMIT < length)
list.add(source.substring(i,i+LIMIT));
else
list.add(source.substring(i));
}
for(int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}//end main
}//end class>> 결과
0123456789
abcdefghij
ABCDEFGHIJ
!@#$%^&*()
ZZZ
2. LinkedList
https://www.youtube.com/watch?v=1ey5QpqbapU
[배열의 장단점]
- 장점 : 배열의 구조가 간단하고, 데이터를 읽는데 걸리는 시간이 짧다.
- 단점1 : (실행중) 크기를 변경할 수 없다. (크기를 변경할 경우 : 크기를 늘려 복사해서 참조변경)
* 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨
- 단점2 : 비순차적인(=중간에) 데이터의 추가, 삭제에 시간이 많이 걸린다.
* 데이터를 추가/삭제하려면 다른 데이터를 옮겨야함
* 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.
[LinkedList <- 배열의 단점을 보완]
- 배열과 달리, 링크드 리스트는 불연속적으로 존재하는 데이터를 연결
▶ 데이터의 삭제 : 단 한 번의 참조 변경으로 가능
▶ 데이터의 추가 : 한 번의 객체 생성과 두 번의 참조변경만으로 가능
- 단점 : 데이터 접근성이 나쁘다 (why? 노드들이 next로 하나씩 연결되어 있음)
- 개선한 것
▶ 더블리 링크드 리스트 : 이중 연결리스트 *하나의 노드에 next + previous
▶ 더블리 써큘러 링크드 리스트 : 이중원형 연결리스트 *첫번째->맨끝 / 맨끝->첫번째 연결
- 자바는 더블리 링크드 리스트를 사용한다.
ArrayList vs LinkedList 비교
| 특징 | 읽기(접근시간) | 추가/삭제 | 비고 | |
| ArrayList | 연속적 | 빠르다 | 느리다 | 순차적인 추가삭제는 더 빠르다. 비효율적인 메모리사용 |
| LinedList | 불연속 | 느리다 | 빠르다 | 데이터가 많을수록 접근성이 떨어진다. |