ArrayList
- 사이즈가 고정되어 있음
- 삽입 시 사이즈를 늘려주는 연산이 필요
- 삭제 시에는 순차적인 인덱스 구조로 인해서 삭제된 빈 인덱스를 채워야 하기때문에 채워주는 연산이 필요
- 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 이런 부가적인 연산이 시스템의 성능 저하로 이어져 치명적임
LinkedList
- 뒤로 밀거나 채우는 작업 없이 단지 주소만 서로 연결시켜 주면 되기 때문에 추가/삭제가 ArrayList보다 빠르고 용이
- 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현 하는것이 바람직
LinkedList의 단점
- ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access) 만 가능
- LinkedList는 단방향성을 갖고 있기 때문에 인덱스를 이용하여 자료를 검색하는 애플리케이션에는 적합하지 않음
- 사실 순차 접근도 참조의 지역성(locality of reference) 때문에 LinkedList 보다는 ArrayList가 훨씬 빠름
- n개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장하는 반면, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장
- LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 ArrayList보다는 긴 지연 시간이 소모됨
- 참조자를 위해 추가적인 메모리를 할당해야 하므로 자료들의 크기가 작은 리스트의 경우 참조자를 위한 추가 적인 메모리할당은 비실용적일 수 있음
Double LinkedList
- 기존의 링크드리스트는 단방향으로만 탐색할 수 있으나 더블링크드리스트는 앞의 노드의 주소도 가지고 있으므로
양방향 탐색이 가능
참조의 지역성: 전산 이론중의 하나로 한번 참조한 데이터는 다시 참조될 가능성이 높고 참조된 데이터 주변의 데이터 역시 같이 참조될 가능성이 높다는 이론
Reference