JAVA Collection Framework 2/2 #Day5

List : ArrayList, LinkedList

• 순서ㅇ(index), 중복 ㅇ

ArrayList : 배열과 구조가 유사한 list 구현 클래스

• 내부는 배열로 구현되어 있음.(배열보다 사용성이 좋음)
• 길이를 자동으로 확장해줌(배열은 사이즈 고정), 미지정 시 default caplacity는 10이나 필요에따라 자동으로 확장.

LinkedList : 각 요소가 논리적으로 연결된 list 구현 클래스 ⇒ 더블링크드 리스트

• 메모리에 연결되어있지는 않은데, 각 노드가 앞, 뒤(Prev, Next) 노드를 가르키고 있음
• List인터페이스를 구현하기 때문에 ArrayList와 LinkedList 의 메소드가 거의 유사함

 

	요소 인접 여부	검색	순차 접근 (추가, 삭제)	중간 접근 (추가, 삭제)	Capacity
ArrayList	O	(상대적으로) 빠름 첫주소 + 인덱스	(빠름) 기존 요소 이동 불필요	(느림) 전부 이동해야 함	default 10개
LinkedList	X	(상대적으로) 느림 앞/뒤에서부터 Next/Prev를 따라서 원하는 곳까지 찾아감	(느림) 하나를 생성/삭제할때마다 객체가 생성/삭제되어야 함	(빠름) 가르키는 주소값만 변경해주면 됨	유동적

⇒ 데이터의 잦은 변경이 예상되면 LinkedList, 데이터의 갯수가 변하지 않는다면 ArrayList 사용

---

Set : HashSet, TreeSet

• 순서 X, 중복 X →  index가 없기 때문에 값 자체로 식별해야 함

HashSet : 해시코드를 사용하여 데이터의 중복을 배제하는 Set 구현 클래스

• 해싱 : 임의의 길이를 가진 데이터를 고정된 길이로 변경 → 요소가 저장될 위치가 됨
  • Object 클래스 내 hashCode() 메소드 있음
• <해시 자료구조의 저장/조회시 버킷을 계산하는 방법>

TreeSet : 이진탐색트리를 사용하여 객체를 저장하는 Set 구현 클래스

• 하나의 부모 노드가 최대 두 개의 자식 노드와 연결되는 이진트리(Binary Tree)의 일종으로, 정렬과 검색에 특화된 자료 구조
• 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징
• 데이터를 추가할 때 정렬을 실시함

Iterator

• 순회를 시켜주는 객체(Collection을 표준화된 방법으로 순회)
• Iterable 인터페이스를 구현하고 있는 collection 만 가능함 : List, Set (Map은 Set으로 바꿔서 순회함)
  • hasNext() : 읽어올 객체가 남아있는지 여부 T/F - cursor(필드)가 현재 위치를 기억하고 있음
  • next() : 컬렉션에서 하나의 객체를 읽어옴. cursor(필드)의 값
  • remove() : next()를 통해 읽어온 객체를 삭제. next()호출 후 사용

---

Map : HasMap, TreeMap

• 순서X, (Key 중복 X, Value 중복 O)
• Key-Value(각각이 객체)의 쌍으로 구성된 Entry 객체를 저장

HashMap

• 해시코드를 사용하여 데이터를 저장하는 Map 구현 클래스
  • key의 중복 배제 : key → hash함수 → 다이제스트 + 처리 ⇒ 해시맵의 index가 됨
  • 해시맵의 사이즈는 정해져 있어, 처리과정에서 인덱스가 겹칠 수 있음(해시충돌) → 링크드리스트로 처리
• 해싱(Hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는 데 있어서 뛰어난 성능
• keySet()이나 entrySet() 메서드를 이용해 Set 형태로 반환된 컬렉션에 iterator()를 호출하여 반복자를 만든 후, 반복자를 통해 순회

 

(요약)

	Collection implement Iterable	List implement Collection	Set implement Collection	Map
객체 추가	boolean add(Obj o)             / addAll(Collection c)		boolean add(Obj o) //중복객체면 false		주어진 객체 및 컬렉션의 객체들을 컬렉션에 추가
				Object put(Obj key, Obj value)	주어진 키로 값을 저장. 해당 키가 새로운 키일 경우 null을 리턴, 같은 키가 있으면 기존의 값을 대체하고 대체되기 이전의 값을 리턴.
		void add(int index, Obj element)			주어진 인덱스에 객체 추가
		boolean addAll(int index, Collection c)			주어진 인덱스에 컬렉션 추가
		Object set(int index, Object element)		Object setValue(Object value)	- 주어진 위치에 객체 저장 - Entry 객체의 Value 객체를 인자로 전달한 value 객체로 바꿈
객체 삭제	void clear()			void clear()	컬렉션에 저장된 모든 객체 삭제 모든 Map.Entry(키와 값)을 삭제
		Object remove(int index)		Object remove(Object key)	주어진 인덱스에 저장된 객체를 삭제하고, 삭제된 객체 반환 주어진 키와 일치하는 Map.Entry를 삭제하고 값을 리턴
	boolean remove(Object o)             / removeAll(Collection c)	boolean remove(Object o)			주어진 객체를 삭제하고 성공여부 리턴
	boolean retainAll(Collection c)				주어진 컬렉션을 제외한 모든 객체를 컬렉션에서 삭제하고, 컬렉션에 변화가 있는지를 리턴
객체 검색	boolean isEmpty()			boolean isEmpty()	컬렉션이 비어있는지를 확인합니다.
	boolean equals(Obj o)			boolean equals(Obj o)	컬렉션이 동일한지 확인
	int size()			int size()	저장된 전체 객체(Entry 객체) 수 리턴
	boolean contains(Object o)               / containsAll(Collection c)				주어진 객체 및 컬렉션이 저장되어 있는지를 리턴
				boolean containsKey(Object key)	주어진 키가 있으면 true, 없으면 false
				boolean containsValue(Object value)	주어진 값이 있으면 true, 없으면 false
	Iterator iterator()				컬렉션의 iterator를 리턴
				int hashCode()	Entry 객체의 해시코드를 반환
		Object get(int index) <linkedList> - getFirst() - getLast()		Object get(Object key) Object getKey() Object getValue()	주어진 인덱스에 저장된 객체를 반환
				Set entrySet() Set keySet()	- 키와 값의 쌍으로 구성된 모든 Map.Entry 객체를 Set에 담아서 리턴 - 모든 키를 Set 객체에 담아서 리턴
				Collection values()	저장된 모든 값을 Collection에 담아서 리턴
		int indexOf(Obj o)    / lastIndexOf(Obj o)			순방향 / 역방향으로 탐색하여 주어진 객체의 위치를 반환
		Listiterrator listIterator()                    / listIterator(int index)			List의 객체를 탐색할 수 있는 ListIterator 반환 / 주어진 index부터 탐색할 수 있는 ListIterator 반환
		List subList(int fromIndex, int toIndex)			fromIndex부터 toIndex에 있는 객체를 반환
객체 변환	Object[] toArray()				컬렉션에 저장된 객체를 객체배열(Object [])로 반환
	Object[] toArray(Object[] a)				주어진 배열에 컬렉션의 객체를 저장해서 반환
객체 정렬		void sort(Comparator c)			주어진 비교자(comparator)로 List를 정렬