ArrayList

• ArrayList는 기존의 Vector를 개선한 것으로 구현원리와 기능적으로 동일하다. ArrayList와 달리 Vector는 자체적으로 동기화처리가 되어 있다.
• List 인터페이스를 구현하므로, 저장순서가 유지되고 중복을 허용한다.
• 데이터의 저장공간으로 배열을 사용한다.

배열의 장점과 단점

• 장점 : 구조가 간단하고 데이터를 읽어오는 시간이 짧음
• 단점 :
  • 크기를 변경할 수 없기 때문에 만약 크기를 변경하고 싶다면 새로운 배열을 생성해서 그 배열에 데이터를 복사 후 참조변경 해야한다.
  • 데이터의 추가, 삭제에 시간이 많이 걸린다. 삭제나 삽입을 할때 데이터를 복사해 데이터의 위치를 움직여야 하기 때문이다. 데이터 끝에 추가하거나 끝의 데이터를 삭제하는 속도는 빠르다.

LinkedList

• 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결 합니다.
• 요소(노드)에 다음 요소(노드)의 참조변수가 저장되어 다음 요소(노드)를 가리킨다. 불연속적으로 연결되어 있기 때문에 테이터를 요소들 사이에 삭제하거나 추가하는 변경이 유리하다.
• 데이터의 삭제는 단 한번의 참조변수만 변경하면 되고(삭제한 데이터의 그 다음 데이터의 참조변수를 삭제된 데이터의 참조변수가 저장되어 있던 데이터에 저장하면 되기 때문이다.) 데이터의 추가는 두번의 참조변수 변경만으로 가능하다.
  (데이터의 추가는 추가되는 데이터의 참조변수를 앞에 데이터가 저장하면 되고 추가되는 데이터의 앞의 참조변수를 추가되는 데이터가 저장하면 된다.)
• 단점도 있다. 연속적인 배열은 내가 찾는 데이터를 한번에 이동해서 빠르게 찾을수 있어 접근성이 좋지만 링크드리스트는 현재 요소가 아는 것은 바로 다음 요소가 어딨는지만 알지 내가 찾는 데이터가 어디에 있는지는 모르기 때문에 데이터를 찾으려면 요소들을 지나가야 찾을수 있기 때문에 접근성이 좋지 않다.

더블 링크드 리스트

• 링크드 리스트의 접근성을 향상시키기 위해서 요소들의 앞뒤를 연결해 앞뒤의 참조변수를 저장하는 방식이다. 그래도 배열에 비교해서는 접근성이 좋지는 않다.

더블 써큘러 링크드 리스트

더블 링크드 리스트는 요소의 앞과 뒤의 참조변수를 저장하는 방식이었다면 더블 링크드 리스트는 요소의 앞과 뒤의 요소의 참조변수를 모두 저장하는 방식이다. 맨앞의 요소는 맨뒤의 요소의 참조변수를 저장하고 맨뒤의 요소는 맨앞의 요소의 참조변수를 저장하는 방식으로 구성된다.쉽게 말해서 더블 링크드 리스트에서 맨앞의 요소와 맨뒤에 요소를 연결시킨 것이다.

실제로 자바에서는 더블 링크드 리스트로 구현되어 있다.

ArrayList와 LinkedList 비교

• 데이터를 읽는 속도는 ArrayList가 LinkedList 보다 빠르다.
• 데이터를 순차적으로 추가하거나 삭제하는것은 ArrayList가 빠르고 비순차적으로 요소 사이에 데이터를 추가하거나 삭제하는것은 LinkedList가 빠르다.