자바의 정석 - 11.4 LinkedList

11.3.1 LinkedList

• 배열은 두 가지 단점이 있음
  1. 크기를 변경할 수 없음
  2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸림
  3. 💡 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터를 복사해서 이동해야 하기 때문임
• 이 배열의 단점을 보완하기 위해 LinkedList가 만들어졌음
• 배열은 모든 데이터가 연속적으로 존재하지만, LinkedList는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있음
• 💡 불연속적으로 위치한 각 요소들이 서로 연결된 구조이기 때문에 처음부터 n번째 데이터까지 차례로 따라가야만 원하는 값을 얻을 수 있음
• 기본적인 LinkedList는 이동방향이 단방향이기 때문에 다음 요소에 접근은 쉽지만, 이전 요소에 대한 접근이 어려움
• 때문에 이중 연결 리스트(Double Linked List)가 만들어졌음
• 실제로 LinkedList클래스는 이름과 달리 이중 연결 리스트로 만들어졌음
• 💡 이는 리스트의 단점은 낮은 접근성을 높이기 위함임

11.3.2 ArrayList와 LinkedList의 비교

1. 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠름
2. 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠름
3. 💡 ArrayList는 내부적으로 배열을 이용하기 때문에, 중간 데이터를 삭제시 재배치 하는데 시간이 오래 걸림