[자바의 정석] 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와 LinkedList의 비교

	특징	읽기(접근시간)	추가/삭제	비고
ArrayList	연속적	빠르다	느리다	순차적인 추가삭제는 더 빠르다. 비효율적인 메모리사용
LinedList	불연속	느리다	빠르다	데이터가 많을수록 접근성이 떨어진다.