Collections Framework 4 : LinkedList (vs ArrayList)

배열의 장단점

• 장점
  • 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간이 짧음
• 단점
  • 크기를 변경할 수 없음
    • 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함
    • 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨
  • 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸림
    • 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함
    • 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠름

LinkedList

• 배열의 단점을 보완
• 배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결
• 장점
  • 데이터의 삭제 : 단 한번의 참조변경만을 가능
  • 데이터의 추가 : 한 번의 Node 객체 생성과 두 번의 참조 변경만으로 가능
• 단점
  • 데이터 접근성이 나쁨

Doubly LinkedList (이중 연결리스트)

• 접근성 향상
• 여전히 한 번에 두 개, 세 개의 요소를 건너 뛰는건 불가능

Doubly Circular LinkedList (이중 원형 연결리스트)

• 접근성 더욱 향상
• 여전히 배열에 비에서는 접근성이 나쁨

ArrayList(배열 기반) vs LinkedList(연결 기반)

• 순차적 증가 : ArrayList 승
• 순차적 삭제 : ArrayList 승
• 중간에 추가 : LinkedList 압승
• 중간에서 삭제 : LinkedList 압승
• 접근시간 테스트 : ArrayList 압승