List 관련 질문 답변 정리

금일 면접을 봤는데 List, Map, Set의 차이점에 대해 물어봤다.

 

그런데 대답을 잘 하지 못한 기념(?)으로 이에 대한 내용을 정리하려고 한다. 

 

물론 내가 받은 질문 뿐 아니라, 평소 들엇는데 기억이 잘 안나는 것에 대한 답도 정리하려고 한다. 

 

사실 이게 그냥 코드로 써보면 진짜 별 거 아닌데 사용하는것과 이해하는것은 별개의 문제긴 하다.

 

그런데 내용이 솔직히 어렵지는 않다. 다만 어느 차이점에 대해서 많이 질문을 하니, 그러한 것을 중심으로 정리할 것이다.

 

자세한 사용 방법이나 이런것은 흔히 찾을 수 있는 것이니 알아서 찾아보자. 

---

1. What is Collection Framework?

자바에서 컬렉션 프레임워크(collection framework)란 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 의미

 

컬렉션 프레임웍에서는 컬렉션데이터 그룹을 크게 3가지 타입이 존재한다고 인식하고 각 컬렉션을 다루는데 필요한 기능을 가진 3개의 인터페이스를 정의하였다. 

 

그리고 인터페이스 List와 Set의 공통된 부분을 다시 뽑아서 새로운 인터페이스인 Collection을 추가로 정의하였다.

 

출처 : http://www.tcpschool.com/java/java_collectionFramework_concept

 

 

출처 : https://joooootopia.tistory.com/13

 

 

List<E>	순서가 있는 데이터의 집합으로, 데이터의 중복을 허용함.	Vector, ArrayList, LinkedList, Stack, Queue
Set<E>	순서가 없는 데이터의 집합으로, 데이터의 중복을 허용하지 않음.	HashSet, TreeSet
Map<K, V>	키와 값의 한 쌍으로 이루어지는 데이터의 집합으로, 순서가 없음. 이때 키는 중복을 허용하지 않지만, 값은 중복될 수 있음.	HashMap, TreeMap, Hashtable, Properties

 

List, Set, Map 간단 정리

1. List<E> : 순서 O, 데이터 중복 O
2. Set<E> : 순서 X, 데이터 중복 
3. Map<K, V> : 순서 X, 키는 중복 X, 값은 중복 O

출처 : 자바의 정석 3rd edition

2. HashTable vs HashMap

해싱

해싱은 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것

해싱 자료구조는 array와 linkedList의 조합으로 되어 있다.

해시함수

키 값으로 레코드가 저장되어 있는 주소(혹은 색인)를 산출하는 함수. 데이터가 저장되어 있는 곳을 알려주어 다량의 데이터 중에서 원하는 데이터를 빠르게 찾을 수 있다. 

해시 충돌

다른 내용의 데이터가 같은 키를 같은 상황을 해시 충돌(Hash Collision)이라고 한다

출처: https://preamtree.tistory.com/20

HashTable?

The Hashtable class implements a hash table, which maps keys to values. Any non-null object can be used as a key or as a value. To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.  

 

• 동기화를 지원해 Thread-safe하다. 
• 해쉬 테이블에 키/값 한쌍으로 저장한다. 
• HashTable에서 우리는 키로 사용되는 객체와 그 키와 연관짓길 원하는 값을 지정한다. 키는 그리고 나서 hashed되고 결과의 해쉬 코드는 값이 테이블 내에 저장된 인덱스에 사용된다. 
• Hash Table 클래스의 초기 기본 용량은 11이다. loadFactor는 반면에 0.75이다.
• HashMap은 Enumeration을 제공하지 않지만, 해쉬 테이블은 fail-fast Enumeration을 제공한다. 
• HashMap은 key에 null을 허용하지만 HashTable은 null 허용 안함
• HashMap은 HashTable에 비해 해시 충돌이 덜하다. 

2. ArrayList와 LinkedList의 차이점은 무엇일까? 

ArrayList

ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면이 동일하다. 

 

ArrayList는 Object를 이용해 데이터를 순차적으로 저장한다. 

 

ArrayList는 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해 임시 배열을 생성해 데이터를 복사 하는 방법을 사용 하고 있다.

 

대량의 자료를 추가/삭제 하는 경우에는 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하를 일으킬 수 있다. 반면 각 데이터는 인덱스를 가지고 있기 때문에 한번에 참조가 가능해 데이터의 검색에는 유리한 구현체이다.

 

다시 말하면, 동적으로 배열이 늘어나는게 아니라, 용량이 다 차면 더 큰 용량의 배열을 만들어 옮기는 작업을 한다. 

 

그러므로 초기 용량을 물론 예상하기 쉽지 않지만, 여유잇는 값을 지정해주는게 좋을 수도 있다. 

LinkedList

LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있다.

 

배열이란 여러 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조이다. 자료구조가 가장 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠르다. 또한, 배열에서는 인덱스는 값에 대한 유일무이한 식별자다.

 

배열의 장점은 다음과 같다.

• 인덱스를 통한 검색이 용이함.
• 연속적이므로 메모리 관리가 편하다.

 

하지만 다음의 문제가 있다.

• 크기 변경 불가. ArrayList의 경우 이 문제로 인해 배열을 새로 만들어서 크기를 늘린다.
• 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다. 배열 중간에 데이터 추가시 빈자리 만들려면 많은 작업 필요. 삭제시에는 빈자리를 매꾸기 위해서 또 많은 작업이 필요하다. 

 

이를 보완하기위해 LinkedList가 탄생했다고 한다. 

 

 

결론적으로 데이터의 검색시에는 ArrayList가 빠르고, 삽입과 삭제시에는 LinkedList가 빠르다고 한다. 

 

검색시에 ArrayList는 인덱스 기반 자료구조로 O(1)의 시간 복잡도를 가지는 반면, LinkedList는 검색 시 모든 요소를 탐색해야 하기 때문에 최악의 경우에는 O(N)의 시간 복잡도를 가진다.

 

삽입, 삭제 시에는 LinkList는 이전 노드와 다음 노드를 참조해 상태만 변경하면 되지만, ArrayList의 경우에는 삽입, 삭제가 이루어 진 후 데이터를 복사해야 해서 O(N)의 시간 복잡도를 가질 수 있다.

 

더 자세한 내용을 다음 사이트들을 보자. 

 

출처 :

https://www.holaxprogramming.com/2014/02/12/java-list-interface/

https://devlog-wjdrbs96.tistory.com/64

 

3. Array와 List의 차이점은 무엇일까?                                                      

Base	Array	ArrayList
Dimensionality	It can be single-dimensional or multidimensional	It can only be single-dimensional
Traversing Elements	For and for each generally is used for iterating over arrays	Here iterator is used to traverse riverArrayList
Length	length keyword can give the total size of the array.	size() method is used to compute the size of ArrayList.
Size	It is static and of fixed length	It is dynamic and can be increased or decreased in size when required.
Speed	It is faster as above we see it of fixed size	It is relatively slower because of its dynamic nature
Primitive Datatype Storage	Primitive data types can be stored directly unlikely objects	Primitive data types are not directly added unlikely arrays, they are added indirectly with help of autoboxing and unboxing
Generics	They can not be added here hence type unsafe	They can be added here hence makingArrayList type-safe.
Adding Elements	Assignment operator only serves the purpose	Here a special method is used known a

 

가장 큰 차이점은 아무래도 길이에 있는것 같다. 

 

Array의 경우는 동적으로 사이즈 변경이 안되는데, ArrayList의 경우는 가능하다.

 

출처 : https://www.geeksforgeeks.org/array-vs-arraylist-in-java/

3. Map vs List! 둘은 언제 써야하나?

Map과 List에 대해 위에서 이야기를 나눠봤는데, 결국 목적에 맞게 사용하면 된다. 

 

Map은 값을 키에 매칭한다. 맵에서 키는 중복될 수 없고, 각각의 키는 하나의 값을 가진다. 

 

List는 순서가 있는 collection이다. 이 인터페이스의 사용자는 리스트에서 각각 원소가 삽입된 위치의 정확한 제어를 한다. 유저는 정수 인텍스로 접근할 수 있고, 리스트에서 원소를 검색할 수 도있다.

 

차이점은 애초에 다르다는 것이다. 

 

https://stackoverflow.com/questions/3770613/when-to-use-a-map-instead-of-a-list-in-java

---

이게 단순히 질문 사항이나 궁금햇던 것에 대해서만 정리를 하려 햇는데 파면 팔수록 이게 너무 다양한 자료구조와 원리가 튀어나오고 있다. 나중에 java의 정석을 토대로 깊이있게 Collection FrameWork에 속한 아이들을 공부해야겠다.