- 배열의 장점: 구조가 간단하고 데이터를 읽는데 걸리는 시간(access time)이 짧다
- 배열의 단점:
- 크기를 변경할 수 없다 -> 새로운 배열을 생성 후 데이터를 복사해야함
- 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면 메모리 낭비
- 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸림
- 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함
- 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠름
LinkedList
LinkedList는 배열의 단점(1. 크기변경 x 2. 추가삭제시간 많이걸림) 을 보완
- LinkedList는 불연속적으로 존재하는 데이터를 연결(link)
- 불연속적
class Node{
Node next;
Object obj;
}
- 단 한번의 참조변경으로 데이터 삭제 가능
- 한번의 Node 객체생성과 두번의 참조 변경만으로 데이터 추가 가능
LinkedList - 이중 연결 리스트
- LinkedList - 데이터 접근성이 나쁨
- doubly linked list - 이중 연결 리스트, 접근성 향상
class Node{
Node next;
Node previous;
Object obj;
}
- doubly circular linked list - 이중 원형 연결리스트
- 자바에서는 이중연결리스트로 구현되어 있음
ArrayList vs. LinkedList
- ArrayList가 추가할 때 더 빠름
- 순차적으로 삭제할 때 ArrayList가 빠름
- 비순차적으로 데이터 추가/삭제 - LinkedList가 빠름 (20배는 차이남)
- 접근시간(access time)- ArrayList가 빠름 (400배 이상)
- 읽기는 ArrayList가 빠르고 추가/삭제는 LinkedList가 빠름
- LinkedList는 데이터가 많을수록 접근성이 떨어짐