2. 리스트(List)

1. ArrayList

• 용도 : 일반적인 데이터 모음, 인덱스 조회가 많을 때 사용되는 자료구조
• 시간 복잡도 : 조회 get O(1), 추가 add O (1), 중간 삽입/삭제 (O(N)

메서드	설명	비고
add(E e)	리스트 맨 뒤에 데이터를 추가한다.
add(int idx, E e)	중간에 삽입한다. (지정한 인덱스 값 위치)	느림(사용 주의)
get(int idx)	i번째 데이터 조회	빠름
remove(int idx)	i번째 데이터 삭제	삭제 후 뒤의 요소들이 당겨진다.
size()	리스트의 크기를 반환한다.
contains(Object o)	리스트 내에 해당 값 존재 여부를 확인한다.	시간 복잡도 : O(N)

 

 

2. LinkedList

• 용도 : 맨 앞/뒤 추가나 삭제가 빈번하거나, 중간 삽입/삭제가 많을 때 사용된다.
• 특징 : 양방향 연결 리스트. List와 Deque 인터페이스를 모두 구현한 것이 특징.
• 시간 복잡도 : 조회 O(N), 앞뒤 추가/삭제 O(1)

분류	메서드	설명	시간 복잡도
추가 (앞)	addFirst(E e) / push(E e)	맨 앞에 추가	O(1)
추가 (뒤)	addLast(E e) / add(E e)	맨 뒤에 추가	O(1)
추가 (중간)	add(int idx, E e)	해당 인덱스에 데이터를 삽입한다.	O(N)
삭제 (앞)	removeFirst() / pollFirst()	맨 앞 삭제 및 반환	O(1)
삭제 (뒤)	removeLast() / pollLast()	맨 뒤 삭제 및 반환	O(1)
삭제 (중간)	remove(int idx)	해당 인덱스에 위치한 데이터를 삭제한다.	O(N)
	remove(Object o)	특정 객체를 찾아서 삭제한다.	O(N)
조회 (앞)	getFirst() / peekFirst()	맨 앞 데이터 확인	O(1)
조회 (뒤)	getLast() / peekLast()	맨 뒤 데이터 확인	O(1)
조회 (중간)	get(int idx)	인덱스에 위치한 데이터를 확인한다.	O(N) (매우 느림)
검색	contains(Object o)	특정 객체를 포함했는지에 대한 여부를 반환한다.	O(N)
	indexOf(Object o)	특정 객체의 인덱스 값을 반환한다.	O(N)