자바의 정석 기초편 - ch11 - 컬렉션 프레임워크(2) 리스트

ArrayList

기존의 Vector를 개선한 것.
이름에 보이는 것처럼 데이터의 저장공간으로 배열을 사용한다.

ArrayList에 저장된 객체를 삭제할 때 (list.remove())

삭제할 데이터 아래 있는 데이터를 한칸씩 위로 복사해서 삭제할 데이터를 덮어 쓰고
마지막 데이터는 null로 변경한뒤 데이터를 삭제하고 개수가 줄었으니 size 값을 감소시킴
(-> 복잡하다. 시간이 걸린다.)

ArrayList에 저장된 첫번째 객체부터 삭제하는 경우에는 배열복사가 발생하니
마지막 객체부터 삭제하는 것이 낫다 훨씬.
-> 이러한 경우에는 배열복사 발생하지 않고 속도도 빠름.

LinkedList

배열의 장점: 배열은 구조가 간단. 데이터 읽는데 걸리는 시간이 짧음.
배열의 단점: 크기를 변경 할 수 없다.
무엇보다 비순차적인 데이터 추가, 삭제에 시간이 많이 걸린다(데이터 옮겨야 해서..)
그러나 데이터 끝에 추가와 끝부터 삭제는 빠름.

LinkedList는 배열의 단점을 보완!: 크기 변경 불가능하고 추가 삭제 시간이 오래걸리는 것을 보완
배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결.

LinkedList의 종류

• LinkedList: 데이터가 불연속적이라서 데이터 접근성이 나쁨(노드로 연결)
• Doubly LinkedList: 이중 연결 리스트, 접근성 향상
• Doubly Circular LinkedList: 이중 원형 연결 리스트

ArrayList와 LinkedList의 성능 비교

순차적으로 하는 일은 ArrayList가 빠르지만 중간에 추가 하거나 삭제 하는것은 LinkedList가 빠름. 접근 시간은 ArrayList가 빠르다.