List
List 인터페이스는 중복을 허용하면서 저장 순서가 유지되는 컬렉션을 구현하는데 사용된다.
List 인터페이스에서 지원하는 클래스는 ArrayList, LinkedList 등이 있다.
동일한 특성의 데이터들을 묶는다는 것과 반복문 내에 변수를 이용해서 하나의 묶음 데이터들을 모두 접근할 수 있다는 점에서 배열과 비슷하다.
하지만, 리스트는 길이가 가변적이다. 이를 동적 할당이라고 하는데, 처음 선언하고 그 길이를 변경할 수 없는 배열과 달리 리스트는 데이터를 추가하고, 삭제함에 따라 길이를 변경할 수 있다.
또한, 데이터들이 연속적으로 나열된다. (메모리에 연속적으로 나열되지 않고, 각 데이터들은 주소로 연결되어 있다.)
그리고, 각각의 데이터들 사이에 빈 공간을 허용하지 않는다.
List 장단점
장점
1. 데이터의 개수에 따라 해당 개수만큼 메모리를 동적 할당해주기 때문에 메모리 관리가 편리해진다.
2. 빈 공간을 허용하지 않기 때문에 데이터 관리에도 편하다.
3. 포인터(주소)로 각 데이터들이 연결되어 있기 때문에 해당 데이터에 연결된 주소만 바꿔주면 되기 때문에 삽입 삭제에 용이하다.(ArrayList는 예외)
단점
1. 객체로 데이터를 다루기 때문에 적은양의 데이터만 쓸 경우 배열에 비해 차지하는 메모리가 커진다.
ex) primitive type인 Int는 4Byte를 차지한다. 반면에 Wraaper class인 Integer는 32bit JVM에선 객체의 헤더(8Byte), 원시 필드(4Byte), 패딩(4Byte)으로 '최소 16Byte를 차지한다. 거기에다가 이러한 객체데이터들을 다시 주소로 연결하기 때문에 16 + α 가 된다.
2. 기본적으로 주소를 기반으로 구성되어있고 메모리에 순차적으로 할당하는 것이 아니기 때문에(물리적 주소가 순차적이지 않다) 색인(검색)능력은 떨어진다.
List 인터페이스에 정의된 메서드
ArrayList / LinkedList
ArrayList
ArrayList 클래스는 내부적으로 Object[] 배열을 이용하여 요소를 저장한다. 배열을 이용하기 때문에 인덱스를 이용해 요소에 빠르게 접근할 수 있다.
크기가 고정되어있는 배열과 달리 데이터 적재량에 따라 가변적으로 공간을 늘리거나 줄인다. 그러나 배열 공간이 꽉 찰때 마다 배열을 copy하는 방식으로 늘리므로 이 과정에서 지연이 발생하게 된다.
데이터를 리스트 중간에 삽입/삭제 할 경우, 중간에 빈 공간이 생기지 않도록 요소들의 위치를 앞뒤로 자동으로 이동시키기 때문에 삽입/삭제 동작은 느리다. 따라서 조회를 많이 하는 경우에 사용하는 것이 좋다.
LinkedList
Linked List는 ArrayList와 같이 인덱스로 접근하여 조회 / 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다는 점이 특징이다. ArrayList는 내부적으로 배열을 이용하여 메서드로 이리저리 조작이 가능하게 만든 컬렉션이라면, Linked List는 노드(객체) 끼리의 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조이다.
불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어있기 때문에 공간의 제약이 존재하지 않으며, 삽입 역시 노드가 가리키는 포인터만 바꿔주면 되기 때문에 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어 삽입 / 삭제 처리 속도가 빠르다.
하지만, 요소를 찾는 과정에서 ArrayList는 무작위 접근이 가능하지만, LinkedList에서는 순차 접근만이 가능하기 때문에 요소에 접근하는 과정에서 엄청난 성능 차이를 보인다.
Set
중복을 허용하지 않는 값들을 모아놓은 컬렉션이다.
셋에 키가 없는 값이 저장된다.
- 데이터를 비순차적(unordered)으로 저장할 수 있는 자료구조
- 삽입(Insertion) 순서대로 저장되지 않는다.
- 수정이 가능하다
- 동일한 값을 여러번 삽입이 불가능하다. 동일한 값이 여러번 삽입되면 나중에 들어온 값으로 치환된다.
- Fast Lookup 이 필요할 때 사용된다.
- 고유값을 찾고자 할 때 사용된다.
- set는 array에 저장된다(Bucket)
- Array와 달리 Set는 element들을 순차적으로 저장하지 않는다.
- Set에서 element들이 저장될 때는 다음과 같이 저장된다.
1. 저장할 element의 값의 hash 값을 구한다.
2. hash값에 해당하는 공간(bucket)에 값을 저장한다.
- set은 저장하고자 하는 값의 hash값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없다. (no indexing)
- hash값 기반의 bucket에 저장하기 때문에 중복된 값을 저장할 수 없다hash값을 기반으로 저장하기 때문에 Lookup이 빠르다.
Look up) 특정 값을 포함하고 있는지를 확인 하는 것 ex) if 5 in my_set:set의 총 길이와 상관없이 단순히 hash값을 계산한 후 해당 bucket을 확인한다 ex) 0(1)
set 인터페이스에 정의된 메서드
Map
Key와 Value로 이루어진 자료구조이다.
그림처럼 키와 값이 하나의 쌍으로 연결되어 있어 키를 통해 값에 접근을 할 수 있도록 만들어진 자료 구조이다.
흔히 key와 value가 메칭 되는것을 맵핑(mapping)한다고 일컫는다.
Key는 Map 자료구조에서 대응하는 값을 찾기 위한 요소로 중복을 허용하면 안된다. 만약 중복이 된다면 접근하는데 문제가 생길 수 있기 때문이다.
List형태의 자료구조들은 순서대로 값을 차곡차곡 집어넣는 일련의 하나의 줄과 같은 형태이다. 반면 Map 형태의 자료구조는 각각의 Key와 매칭 되는 Value들이 존재한다. 즉, 순서보다는 정의된 이름(Key)과 상응하는 데이터들을 묶기 위한 자료 구조로서 효과적이라고 할 수 있다.
Map 자료구조의 대표적인 종류
Map의 개념을 이용하여 사용하는 대표적인 자료구조는 크게 3가지 정도가 있다.
각 자료구조와 특징은 다음과 같다.
- HashMap
- key와 value의 쌍으로만 구성이 될뿐 자료구조 안에 묶인 쌍들에 대한 순서는 보장할 수 없다.
- 즉, 사용자는 키와 값이 구성되는 위치를 결정 하거나 알 수 없다.
- TreeMap
- key의 값을 이용해 순서대로 정렬하여 데이터를 저장하는 자료구조이다.
- key값을 통한 탐색 뿐 아니라 key값의 정렬을 통한 탐색 등을 하기에 용의 하다.
- LinkedHashMap
- 데이터를 입력한 순서대로 쌓아지며 데이터를 저장하는 자료구조
- 배열, 리스트처럼 인덱싱 접근을 하기에 용의 하다.
Map 인터페이스에 정의된 메서드
'Algorithm' 카테고리의 다른 글
| 시간 복잡도, 공간 복잡도 (0) | 2023.07.28 |
|---|---|
| 프로그래머스 - 신규 아이디 추천 (JAVA) (1) | 2023.04.09 |
| 프로그래머스 - 콜라츠 추측 (JAVA) (0) | 2023.04.08 |
| 프로그래머스 - 조회수가 가장 많은 중고거래 게시판의 첨부파일 조회하기 (MYSQL) (0) | 2023.03.25 |
| 프로그래머스 - 자동차 평균 대여 기간 구하기 (MYSQL) (0) | 2023.03.24 |