java 자료구조, arrayList와 linkedList

** 어레이리스트가 자료 탐색은 빠름.

하지만 요소 중간에 수정이나 삭제 삽입을 하면, 해당인덱스를 제외한 나머지 요소들이 인덱스가 뒤로 밀려나거나 땡겨지거나하기 때문에 느림. (순차적으로 add하는식으로 추가하거나 순차적으로 삭제할땐 별상관없음..)

arrayList클래슨 내부에보면 grow 메소드가 존재하는데,

해당 메소드 내부에서는 Arrays.copyOf를 통해서 기존 배열의 요소들을 더큰 배열에 복사하는 과정을 수행함.

자료가 적을때는 괜찮겠지만 많아지면 비효율적임..

 

** 링크드리스트는 인덱스가없기 때문에 특정 엘리먼트의 양옆의 요소를 메모리주소를 서로 비교하면서 찾아서 일반 사용시는 느린편.
하지만 링크드리스트는 수정삭제가 이뤄질때 바로 옆 요소의 주소만 영향을받기 때문에 이경우에 한해서 빠름.

가리키고 있는 주소만 추가하는 방식.

 

 

예를들어 linkedList의 요소가

[123] [454] [214] [5523] 

 

로 이뤄져있다고 할시,

 

[123] [454] 의 중간에 [333] 을 삽입한다고 가정.

 

결과적으로 [123] [333] [454] [214] [5523] 가 되게되는데,

arrayList는 해당 인덱스를 제외한 나머지 요소들이 한칸씩 뒤쪽 인덱스로 전체 이동되는반면,

[123]다음 주소가 [333] 이 되고 [454]의 전 주소가 [333]이 될뿐, [214] [5523]의 주소는 그대로임.

 

 

https://www.youtube.com/watch?v=AChba6iyiew 참조.