11-12 LinkedList / ArrayList, LinkedList 비교

배열의 장단점

장점:

배열은 구조가 간단하고 데이터를 읽는데 걸리는 시간(접근 시간, access time)이 짧다. (연속적이라서)

단점:

1. 크기를 변경할 수 없다.

    - 크기를 변경해야하는 경우 새로운 배열을 생성 후 데이터를 복사해야함.   

    - 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.

2. 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.

    - 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야함.

    - 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

 

요약: 크기변경이 불가능하고, 추가 및 삭제 시간이 많이걸림

 

이런 배열의 단점을 보완하기 위해 LinkedList를 쓴다.

- 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)

데이터의 삭제: 단 한 번의 참조변경만 으로 가능 (변경에 유리)

 

데이터의 추가: 한번의 Node객체 생성과 두 번의 참조변경 만으로 가능

 

 

이중 연결 리스트

링크드 리스트(linked list) - 연결리스트. 데이터 접근성이 나쁨 (자기 다음밖에 모름)

앞 뒤로 이동만 좋아졌을 뿐 한 번에 두, 세개를 갈 수 없어 아쉬움.

 

 

 

ArrayList vs LinkedList - 성능 비교

 

1. 순차적으로 데이터를 추가/삭제 - ArrayList가 빠름

2. 비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름

3. 접근시간(access time) - ArrayList가 빠름

* 인덱스가 n인 데이터 주소 = 배열의 주소 + n * 데이터 타입의 크기

 

컬렉션

읽기(접근시간)

추가/삭제

비 고

ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름 비효율적인 메모리사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐