자바 자료구조 상속 구조도
List는 인터페이스
List는 인터페이스이다. 그래서 자료형으로 선언한 경우에 구현체를 그 하위 클래스로 구현 할수도 있다.
ArrayList를 선언하고 LinkedList로 구현체를 만들거나 형변환 할 수는 없다.
List<Integer> list = new ArrayList<Integer>();
List<Integer> list = new LinkedList<Integer>();
List<Integer> list = new Stack<Integer>();
List<Integer> list = new Vector<Integer>();
ArrayList<Integer> list = new ArrayList<>(); // List로 선언하는 것보다 유연성 떨어짐ArrayList 특징
요소 삽입 및 삭제 과정
LinkedList는 순차접근인 반면에 ArrayList는 무작위 접근이다.
ArrayList는 사이즈가 고정되어 있기 때문에 삽입 시 사이즈를 늘려주는 연산이 들어간다(뒤로 미는 과정).
삭제할때도 요소를 삭제하고 그 뒤의 요소를 앞으로 당겨주는 연산이 있다. 순차적인 인덱스 구조로 인해서 빈공간을 채워주기 위함이다.
자료들이 지속적으로 삭제된다면 끝에 남는 공간 만큼 낭비되는 메모리가 많아진다.
O(N) 만큼의 연산 속도가 걸리기 때문에 자료의 최대 개수에 영향을 받는다.
따라서 삽입과 삭제가 빈번히 일어날때는 ArrayList를 피하는 것이 좋다.
LinkedList
요소 삽입 및 삭제 과정
LinkedList 는 뒤로 밀거나 당기는 연산 없이 주소만 연결시키면 되기 때문에 추가 / 삭제가 ArrayList보다 매우 빠르다.
LinkedList는 순차 접근만이 가능하다. 단순 LinkedList는 단방향성을 갖고 있기 때문에 인덱스를 이용한 검색 애플리케이션에는 적합하지 않다. 그래서 순차접근은 참조의 지역성 때문에 무작위 접근보다 느리다.
참조자(포인터)로 인해 저장 공간의 낭비가 있다.
참조의 지역성 (locality of reference : 한번 참조한 데이터는 다시 참조될 가능성이 높고 참조된 데이터 주변의 데이터 역시 같이 참조될 가능성이 높다는 이론.
LinkedList vs ArrayList
ArrayList는 자료들을 연속적인 묶음으로 저장해두지만 LinkedList는 자료들을 저장공간에 불연속적으로 저장해둔다. 그래서 저장된 데이터에 접근하는데 LinkedList는 ArrayList보다 더 많은 시간이 소모된다.
성능비교 사진
