[2017.10.25] 17. ArrayList와 LinkedList

ArrayList와 LinkedList 비교

장점과 단점의 기준은 ArrayList는 LinkedList, LinkedList는 ArrayList이다.

구분	장점	단점
ArrayList	검색 속도가 더 빠르다.	삽입, 삭제가 더 느리다.
LinkedList	삽입, 삭제가 더 빠르다.	검색 속도가 더 느리다.

이유

ArrayList

ArrayList의 내부는 배열이 선언되어 있고, 배열의 크기를 넘어가면 배열을 자동으로 증가 시켜주는 원리이다.

그렇기 때문에 ArrayList의 장단점은 배열의 장단점에 기초한다. 

그래서 장점은 index를 통해 O(1)로 검색할 수 있다. 

하지만 단점은 삽입, 삭제 시 데이터를 이동(shift) 시켜야 한다.

LinkedList

LinkedList는 Node를 통해 데이터를 관리하는 자료구조이다. 

Node는 데이터와 다음 Node의 주소값으로 이루어져 있다.(단방향 LinkedList의 경우) 주소값으로 데이터가 연결되어 있어 삽입, 삭제가 빠르지만 index로 데이터를 찾기 위해서는 Node를 순차적으로 방문(traversal)하기 때문에 최악의 경우 O(n)으로 검색 할 수 있다.

#ArrayList #LinkedList #ArrayList LinkedList #ArrayList와 LinkedList #ArrayList LinkedList 차이점 #면접