자바의 정석 - LinkedList

배열의 장단점

• 장점 : 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간 (접근시간, access time)이 짧다.
• 단점1 : 크기를 변경할 수 없다.
  • 크기를 변경해야 하는 경우
  1. 새로운 배열을 생성 2. 데이터 복사 3. 참조 변경
  • 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨
• 단점2 : 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
  • 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.
  • 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다. 다른 데이터를 옮기지 않아도 되기 때문에

---

LinkedList - 배열의 단점을 보완

• 배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결(Link)
• 하나하나의 요소가 서로 연결되어있는 구조, 기차와 비슷 ㅇ - ㅇ - ㅇ 이런식
• 데이터의 삭제 : 단 한 번의 참조변경만으로 가능
  -> 1 - 2 - 3 있을 때, 2를 삭제하려고하면 참조변경을 한 번만 하여 1을 3으로 연결하면됨
• 데이터의 추가 : 한 번의 Node객체생성과 두 번의 참조변경만으로 가능
  -> 1 - 2 - 4 - 5 있을 때, 중간에 3을 추가한다면 2를 3으로, 3을 4로 연결하는 2번의 참조변경만 하면됨

---

LinkedList - 이중 연결 리스트

• 단점 : 연결 리스트, 데이터 접근성이 나쁨
  • 1 - 2 - 3이 있을 때, 1에서 3으로 한 번에 가는 것은 불가능. 바로 다음으로만 갈 수 있음 (배열은 한 번에 이동하는 것 가능!)
• doubly Linked List - 이중 연결 리스트 -> 접근성 향상
  • 1 - 2 - 3이 있을 때, 1 -> 2 -> 3 가능, 3 -> 2 -> 1 가능
    (LinkedLis는 3 -> 2 -> 1 불가능), but 한 번에 이동하는 것은 여전히 불가능
• doubly circular Linked List - 이중 원형 연결리스트
  • 1 - 2 - 3 가능, 3 - 2 - 1 가능, 1 - 3 가능

---

ArrayList vs LinkedList 성능비교

• 순차적으로 데이터를 추가 / 삭제 - ArrayList가 빠름
• 비순차적으로 데이터를 추가 / 삭제 - LinkedList 빠름
• 접근시간(읽기) - ArrayList가 빠름
• ArrayList는 비효율적인 메모리 사용
  -> 성능을 높이기 위해서 배열의 크기를 키워야하기 때문
• LinkedList는 데이터가 많을수록 접근성이 떨어짐
  -> 하나하나의 요소를 다 들려야하기 때문에
• ArrayList는 배열기반 (연속적) , LinkedList는 연결기반 (비연속적)