Chpt 11. 컬렉션 프레임워크 - 주제 3. List 인터페이스와 구현 클래스들

1. List 인터페이스의 메서드

 

1) Collection 인터페이스

메서드 참고

 

2) List 인터페이스

 

메서드 참고

 

2. 구현 클래스

 

[그림 2-1] List 인터페이스와 구현 클래스 간의 계층도

 

핵심 구현 클래스는 노란색으로 강조돼 있다.

 

1)  ArrayList

 

(1) 특징

 

(1) Object  배열을 갖고 있다.
- 모든 종류의 객체를 담을 수 있다.
- 순차적으로 객체가 저장된다.
- 변경 작업 중에 크기가 부족하면
① 새로운 배열을 생성
② 복사
③ 새로운 배열로 참조 변경

(2) 삭제 과정
- 마지막 데이터
null로 변경
- 그 외
① 삭제할 데이터의 인덱스보다 큰 인덱스들을 모두 왼쪽으로 하나씩 이동
② 마지막 데이터 null로 변경

(3) 추가 과정
① 추가할 데이터의 인덱스보다 큰 인덱스들을 모두 오른쪽으로 하나씩 이동
② 빈 인덱스에 데이터 추가

 

[참고]

(2)와 같은 삭제 과정 때문에 왼쪽보다 오른쪽 코드의 실행 속도가 더 빠르다.

 

for (int i = 0; i < list.size(); i++)      list.remove(i)

for (int i = list.size(); i >=0; i--)      list.remove(i)

 

(2) 메서드, 예제

 

참고

 

2) LinkedList

 

ArrayList의 단점을 보완해 고안된 것이 LinkedList이다. 그렇기 때문에 ArrayList와는 반대되는 특징을 갖고 있다.

 

1)  ArrayList vs. LinkedList

 

컬렉션 클래스	(1) 메모리 구조	(2) 접근 시간 (읽기)	(3) 순차적 데이터 추가/삭제	(4) 비순차적 데이터 추가/삭제	(5) 데이터 개수의 변경이 잦을 경우	(6) 메모리 사용
ArrayList	배열 기반 (연속) 예) 박스	빠르다	빠르다	느리다	비효율적	비효율적
LinkedList	연결 기반 (불연속) 예) 기차	느리다	느리다	빠르다	효율적	효율적

 

3부터 6열은 모두 메모리 구조에 기반한 장단점이다. 

 

LinkedList의 데이터 추가 삭제 과정은 다음과 같다.

 

(1) 삭제 과정
- 마지막 데이터
참조를 null로 변경
- 그 외
삭제할 데이터의 이전 참조를 삭제할 데이터의 다음 참조로 변경

(2) 추가 과정
① 추가할 위치 이전 요소의 참조를 새로운 요소로 변경
② 새로운 요소의 참조를 추가할 위치의 다음 요소로 변경

 

(6)의 경우 배열의 크기가 부족할 경우 새로운 크기의 배열을 생성하기 때문이다.

 

[참고] Doubly-LinkedList, Doubly-Circular-LinkedList 는 LinkedList의 접근성을 향상한 양방향, 순환적 연결을 갖고 있는 자료 구조이다.

 

3) Stack과 Queue

 

자료 구조	구조	적합한 클래스	추가 / 삭제 메서드	활용
Stack	LIFO	ArrayList, Stack	push, pop	웹브라우저 뒤로/앞으로, 괄호가 포함된 연산
Queue	FIFO	LinkedList	offer, poll	최근 사용 목록

 

적합한 클래스를 정할 때는 해당 클래스가 어떤 메모리 구조를 선택하고 있는지 확인하고, 데이터를 추가, 삭제할 때 어떤 방식으로 삭제하는지 확인하면 된다. 

 

[참고] Queue는 인터페이스이다.

 

(1) 메서드

 

참고

 

[참고] offer와 poll은 예외가 발생하지 않는 메서드이다.

 

(2) 예시

 

참고

 

(3) 활용 예시

 

참고