[Java] Link 인터페이스를 구현한 ArrayList와 LinkedList

List ← 인덱스 기반인 배열의 오버헤드 발생 문제점을 해결 (인터페이스)

• 중복허용
• 가변적 크기
• 입력된 순서대로 저장

코드에서 list를 구현한 클래스명만을 바꾸기만 하면 프로그램의 자료구조를 바꿀 수 있음.

 

ArrayList ← List를 구현한 클래스

LinkedList ← 다른 알고리즘으로 List를 구현한 크래스

• 순차적인 처리에 빠른 속도 제공
• 인덱스를 이용한 요소 접근

ArrayList<Integer> array_List = new ArrayList<>();

ArrayList 클래스의 메소드와 멤버변수를 쓸 수 있음

List<Integer> array_List = new ArrayList<>();

List의 메소드만 쓰고 싶을 경우

ArrayList의 메소드

• add(x)
• size()
• indexOf(idx) // 인덱스가 있으면 인덱스 값을 반환, 없으면 -1을 반환
• set(idx, x) // ArrayList의 추가 삭제는 비효율적
• remove(idx) // ArrayList의 추가 삭제는 비효율적

리스트의 크기를 동적으로 관리

리스트 크기가 자주 달라지면(원소의 이동이 많을 경우) ArrayList보다 LinkedList가 더 적합

배열은 기본타입(int, char 등)rhk object를 담을 수 있지만, ArrayList는 object만 담을 수 있음

LinkedList의 메소드

원소의 삽입, 삭제가 잦을 경우에 좋음

탐색에는 비효율적 (순차접근만 가능함)