[java] ArrayList vs Linked List

<ArrayList>

- List 인터페이스를 구현하였으므로  저장순서가 있고와 중복값이 인정된다.

 

ArrayList의 핵심은 저장값이 순차적으로 저장된다는 점이다. 

ArrayList의 주소는  배열의 주소값 + (index  X 데이터타입 용량)  간단한 계산으로 주소가 순차적으로 할당된다. 이에따라

1. 순차적인 입력, 순차적인(뒤 -> 앞) 삭제가 매우 빠르다. 

 - 순차적인 삭제는 뒤쪽부터 이루어지는 삭제를 말한다. 앞쪽부터 삭제되면 중간값의 삭제와 동일한 원리로 느려진다.

 

2. 중간값의 삭제, 중간값의 삽입이 느리다.

- 중간값이 삭제되는경우 , 순차적인 저장을 유지하기위해 지워진 값 뒤의 모든 값들이 ArrayCopy( )를 통해 복사되고

한칸 앞으로 이동된다. 값이 많을 수록, 중간값이 많이 지워질수록 처리속도가 오래 걸릴 수 밖에 없다.

 

3. 값의 접근 속도가 빠르다.

- 주소값이 간단한 계산으로 부여되고 , 순차적으로 저장되므로 값에 접근하는 속도가 빠르다.

 

 

 

배열이 있는데  굳이 ArrayList를 사용하는 이유가 뭘까? 

- 배열은 한번 만들어지면 크기를 변경할 수 없다. 새로운 배열을 만들어야 하는 것이다.

반면 ArrayList는 클래스 내부적으로 배열을 사용하긴 하지만 자동으로 크기를 변경하도록 만들어져 있다. 

또한 배열과 달리 각종 유용한 기능들을 메서드로 정의해놓았기때문에 ArrayList를 사용한다.

 

<Linked List>

Linked List는 데이터가 불연속적으로 존재한다. 

불연속적으로 존재하는 데이터는 다음 요소의 주소 + 데이터 로 구성된다. 이에따라

1. 중간값의 생성, 삭제가 매우 빠르다.

- 중간값이 생성, 삭제되는 경우 이전의 데이터가 가진 다음 요소의 주소만 수정해주면 된다.

 

2. 값의 접근 속도가 느리다.

- 불연속적으로 데이터가 존재하므로 특정데이터에 접근하기위해서는 처음값부터 찾는 값까지 주소를 따라가야한다.

간단한 계산으로 위치를 계산할수 있는 ArrayList에 비해 느릴 수 밖에 없다.