[Section1][Java] 컬렉션 - 컬렉션프레임웍 - 2 (List)

List

배열과 같이 데이터들을 순차적으로 관리하고 저장한다. 그렇기 때문에 인덱스로 데이터를 검색, 추가, 삭제가 가능하다.

 

List의 구현체

• ArrayList
  List의 구현체이므로 데이터가 순차적으로 존재하며 중복이 가능한 클래스이다.
  내부적으로 데이터를 배열로 관리하며,
  데이터의 검색, 추가, 삭제시에 인덱스로 접근이 가능하도록 구현되어 있다.
  그리고 내부적으로 배열을 사용하지만, 실제 배열과는 다르게 데이터 추가시 ArrayList의 저장용량이 초과된 경우 알아서 저장용량을 넓히고 새로운 저장공간(ArrayList 내부에서 쓰이는 배열)을 만든 뒤에 기존 데이터들을 기존 순서대로 모두 복사해준다.
  
  - 장점
  1. 데이터의 검색이 빠르다
  시작주소 + (한데이터의 크기 * 인덱스) 를 하면 바로 접근이 가능하므로 빠르다.
  
  
  2. 순차적인 데이터의 추가, 삭제가 빠르다.
  단, 마지막 인덱스 위치에서 추가, 삭제를 해야만 빠르다.
  단지 배열의 끝인덱스 변수에 데이터를 넣어주는 개념이다.
  
  3. 저장 용량 부족시 알아서 저장 용량을 넓혀준다.
  
  - 단점
  결국 내부적으로 배열을 사용하므로,
  처음 혹은 중간 위치에 데이터를 삭제하거나 추가할 경우에 해당 인덱스 위치 이후의 데이터들은 한칸씩 당겨지거나, 한칸씩 밀려지는 작업이 필요하다.
  
  
• LinkedList
  List의 구현체이므로 ArrayList와 마찬가지로 데이터를 순차적으로 관리하고 데이터의 중복또한 가능한 클래스이다.
  그러나, 내부적으로 각각의 데이터를 노드(Node)화 하여 관리하고 각 노드는 자신의 이전 노드, 다음 노드의 주소값을 가지고 있는 링크같은 구조이다.
  
  
  

- 장점
1. 데이터 추가, 삭제에 효율적
배열과 같이 추가, 삭제하는 위치의 이후 데이터를 복사할 필요 없이,
추가, 삭제할 위치의 이전, 이후 노드가 가르키는 주소값 변경만 해주면 된다.

- 단점
1. 데이터 검색(접근)이 느리다
특정 데이터를 찾아가기 위해 시작노드에서 부터 목표 인덱스 위치에 노드까지 순차적으로 접근하여야 하므로 느리다.

 

ArrayList와 LinkedList의 차이점과 결론

데이터들의 중간 위치에 잦은 추가, 삭제, 수정이 필요하다면 LinkedList가 효율적이고, 그렇지 않은 경우는 ArrayList가 효율적이다.