Linked List vs Array List

 

순차적인 추가 - ArrayList : 550.41ms

순차적인 추가 - LinkedList : 1828.78ms

--------------------------------------------------

--------------------------------------------------

순차적인 삭제 - ArrayList : 39.98ms

순차적인 삭제 - LinkedList : 98.39ms

--------------------------------------------------

--------------------------------------------------

중간 데이터 삭제 - ArrayList : 9.68ms

중간 데이터 삭제 - LinkedList : 0.1ms

--------------------------------------------------

--------------------------------------------------

중간 데이터 추가 - ArrayList : 8.26ms

중간 데이터 추가 - LinkedList : 0.02ms

--------------------------------------------------

--------------------------------------------------

데이터 검색 - ArrayList : 0.01ms

데이터 검색 - LinkedList : 12.6ms

--------------------------------------------------

 

순차적인 추가, 순차적인 삭제, 데이터 검색은 Array List 속도가 빨랐고
중간 데이터 삭제, 중간 데이터 추가는 Linked List가 시간이 더 단축되었다.

[Array List의 삽입 과정]

[Linked List의 삽입 과정]

이러한 둘의 삽입 과정을 비교해보면 Array List는 사이즈가 고정되어 있기 때문에 삽입 시 사이즈를 늘려주는 연산이 추가되어야 하고 삭제 시에는 순차적인 인덱스 구조로 인해서 삭제된 빈 인덱스를 채워야 하기 때문에 채워주는 연산이 추가되어야 한다. 이러한 부가적인 연산은 삽입 + 삭제가 빈번하게 발생되는 프로세스에 치명적이고 낭비되는 메모리도 많아지게 된다.

[Array List의 삭제 과정]

[Linked List의 삭제 과정]

반면 Linked List는 Array List와 같이 뒤로 밀거나 채우는 작업 없이 단지 주소만 연결시켜 주면 되기 때문에 추가 + 삭제가 용이하다. 따라서 삽입 + 삭제가 빈번하게 발생하는 프로세스는 Linked List를 사용! 위의 결과값과 같이 중간 데이터 삭제 + 삽입 속도가 Array List 보다 월등히 빠름을 볼 수 있음
but Array List는 무작위 접근이 가능하여 데이터 검색 속도가 Linked List보다 월등히 빠름을 알 수 있다.

따라서 Array List와 Linked List는 직접 코드로 구현해봐야 그 차이를 확실히 알 수 있다고 하셨다.

참고 문헌에 각각의 List를 구현해볼수 있는 코드가 구현되어 있으니 헷갈린다면 아래 링크를 따라가도 좋을 것 같다.

 

참고 문헌 Linked List vs Array List

자료구조: Linked List 대 ArrayList