LinkedList 와 ArrayList 비교

배열의 장단점

• 장점 : 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.
• 단점

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

: 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함.
↳ ① 더 큰 배열 생성 ② 데이터 복사 ③ 참조 변경
: 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.

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

: 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함
: 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

LinkedList - 배열의 단점을 보완

: LinkedList는 불연속적으로 존재하는 데이터를 연결(link)

1) 배열의 구조

↳ 배열은 각 요소가 연속적(붙어있다) → 요소들의 위치를 알기 쉬움

2) LinkedList의 구조, 삭제

↳ LinkedList는 불연속적. 각 요소가 붙어있지 않아서 위치를 알 수 없음(그림은 이어져 있는 것처럼 보이지만 실제로는 아님) → 참조변수로 위치 알려주고 연결, 마치 기차 연결과 비슷하다.
↳ 데이터의 삭제: 단 한 번의 참조변경만으로 가능

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

LinkedList의 단점

• 데이터 접근성이 나쁘다.
  ↳ 배열은 이어져 있기 때문에 바로바로 원하는 요소로 한 번에 갈 수 있지만,
  LinkedList는 Next node의 주소만 알기 때문에, 원하는 요소로 바로가기 어렵다.
  

⇒ 단점 보완

• Doubly Linked List: 이중 연결리스트, 접근성 향상 ⇒ 실질적으로 java에서 구현돼있는 것
  
  ↳ 참조를 2개 가짐. 이전(previous), 다음(next) 요소.
  ↳ 그러나, 한 번에 여러개 건너뛰는건 여전히 어려움
• Doubly Circular Linked List : 이중 원형 연결리스트
  

↳ 단점을 보완했음에도, 여전히 배열보다 데이터 접근성이 떨어진다.

ArrayList vs LinkedList 성능 비교

↳ ms 단위로 측정
1) 순차적으로 데이터를 추가/삭제 : ArrayList가 빠름
2) 비순차적으로 데이터를 추가/삭제 : LinkedList가 빠름
3) 접근시간(access time) - ArrayList가 빠름
↳ 인덱스가 n인 데이터 주소 = 배열의 주소 + (n* 데이터 타입의 크기)
↳ 배열에서 n번째 요소에 접근하는데 걸리는 시간 공식

↳ 비효율 : 배열을 미리 크게 잡아놔야 하기 때문에.

출처

• 자바의 정석 기초편 : ch11- 12~ 14