List
선형 자료 구조 : 끊어지지 않고 한 줄로 계속 이어져있는 상태
- 원하는 순서로 요소 삽입 가능하며 각 요소들은 index 번호를 부여 받는다.
- 순서를 가진 데이터의 집합
- 중복을 허용한다.
Array vs list
Array의 경우 각각 index를 할당하지만 삭제 시 그 해당 index의 데이터만 삭제되고 데이터가 있던 자리는 사라지지 않는다.
list의 경우 데이터 삭제 시 데이터 공간도 같이 삭제된다.
-> 덕분에 메모리를 효율적으로 사용할 수 있다.
-> list에서 중요한 것은 원들 간의 순서이다.
list 특징
- list는 두 개의 종류로 나눠진다
--> ArrayList, LinkedList - list는 크기 조절이 가능하다.
- list는 초기 크기를 지정하지 않아도 된다.
- list의 삭제는 공간 자체를 지우는 것이다.
list 사용 방법
List<자료형> 리스트명 = new ArrayList<자료형>();
List<자료형> 리스트명 = new LinkedList<자료형>();
list 기능
- List.add(값) : 삽입
- list.add(index, value) : 중간 삽입, 삽입 시 뒤로 한 칸씩 밀림
- list.set(index, value) : 치환
- list.remove(index) : 삭제
- list.clear() : 전체 삭제
- list.get(index) : 출력
- list.size() : 리스트 크기 확인
ArrayList
배열을 이용해 리스트를 구현한 것이다.
- 크기를 정해주지 않아도 되고 가변적으로 크기가 변하는 선형 리스트
- 요소를 추가하면 index 0 부터 저장되고 중간 index에 추가 또는 삭제하면 index 이후에 위치한 data 모두 한 칸씩 앞 뒤로 옮겨주어야 해서 비효율적이다.
- 중복 가능하나 정렬은 안된다.
-데이터의 크기가 가변적이고 중간에 데이터를 삽입, 학세하는 경우가 거의 없는 조회를 사용할 시에 적절하다. - thread-safe 하지 않는다.
thread-safe 란?
어떤 함수나 변수, 객체가 여러 스레드로부터 동시 접근이 이루어져도 문제가 없음을 말한다.
LinkedList
서로 링크되어 있으며 필요할 때마다 data 할당 받아 추가할 수 있다.
특징
- 미리 메모리 영역 할당이 필요 없다.
- 공간 효율이 좋지 않으며데이터 접근 속도가 느리다.
- 중간에 데이터 추가 또는 샂게할 경우 간단하지만 데이터 연결을 재구성해야 한다.
- 중복 허용, 순서 보장되며 정렬은 안된다.
- thread-safe 하지 않는다.
LinkedList 종류
-
단순 연결 리스트
-
이중 연결 리스트 - 데이터 앞 뒤로 이동 / 탐색이 가능
-
원형 연결 리스트 - 마지막 노드의 포인터가 1을 가리킨다.
Set 컬렉션
- 저장 순서가 유지되지 않는다.
- 객체를 중복해서 저장할 수 없으며 하나의 null만 저장할 수 있다.
- index로 관리하지 않으며 특정 순서를 정할 수 없다.
- 중복 여부를 쉽게 확인할 수 있다.
HashSet
Set<자료형> set = new HashSet<자료형>();
- 객체들을 순서 없이 저장하고 중복, 정렬 모두 안된다.
- thread-safe 하지 않는다.
LinkedHashSet
입력 순서대로 저장되며 중복과 정렬은 안된다.
thread-safe 하지 않는다.
TreeSet
입력 순서대로 저장되며 오름차순으로 정렬된다.
중복은 안된다.
thread-safe 하지 않는다.
Map 컬렉션
key, value로 구성된 자료구조
key 중복은 안되나 value는 중복이 허용된다.
HashMap
Map<K, V> map = new HashMap<K,V>();
key 중복 허용 안되며 순서가 보장되지 않는다.
null값 저장은 허용되며 정렬 가능하다.
thread-safe 하지 않는다.
LinkedHashMap
순서가 보장되며 중복과 정렬은 안된다.
그러나 key는 삽입한 순서대로 정렬된다.
thread-safe 하지 않는다.
HashTable
중복, 정렬 안되며 순서도 보장되지 않는다.
thread-safe 한다.
TreeMap
중복 안되며 순서와 정렬은 보장된다.
thread-safe 하지 않는다.
예상 면접 질문
Array(List)의 가장 큰 특징과 장, 단점?
Array의 가장 큰 특징은 순차적으로 저장한다는 점이다. 0부터 시작하는 index가 존재하여 index를 이용해 특정 요소를 찾고 조작이 가능한 것이 장점이다.
그러나 중간에 데이터를 추가/삭제할 경우 그 뒤 요소들을 한 칸씩 밀거나 당겨줘야 한다는 단점이 있다. Array는 자주 삭제, 축다ㅚ는 데이터를 담기에 적절하지 않다.
Array를 사용하면 좋은 예시?
--> 주식 차트
날짜 별로 주식 가격이 차례대로 저장되어야 하는 데이터
array를 사용하지 않으면 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어야 한다.
Stack, queue, Tree, Heap의 구조를 설명하세요.
stack과 queue는 선형 자료구조이며 Array, linkedList로 구현 가능하다.
Stack는 후입선출, queue는 선입선출이다.
Tree는 비선형구조로 계층적 관계를 표현하기에 적합하다.
Heap은 최대, 최소값을 찾아내는 연산을 쉽게하기 위해 고안된 구조이며 완전 이진 트리이다.
Stack, queue 실사용 예시
stack : 자바의 stack 메모리 영역
지역변수와 매개변수 데이터 값이 저장되는 영역으로 메소드 호출 시 메모리에 할당, 종료되면 메모리 해체 후입 선출 구조
queue : os 스케쥴러
자원의 할당과 회수를 하는 스케쥴러 역할과 같다.
메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가 그 순서를 결정하는 것이 자원의 효율적인 사용에 있고 선입선출이다.
우선순위 큐에 대해 설명하세요.
들어간 순서에 상관없이 우선 순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조이다. 구현 방식에는 배열, 연결리스트, 힙이 있지만 일반적으로 완전 이진 트리의 힙을 이용해 구현한다.
Array와 ArrayList 차이를 설명하세요.
Array : 크기가 고정적이며 초기화 시 메모리에 할당되어 ArrayList보다 빠르다.
ArrayList : 크기가 가변적이며 데이터 추가, 삭제 시 메모리를 재할당하기 때문에 Array보다 느리다.
Array와 LinkedList 장, 단점을 설명하세요.
Array 검색이 빠르지만 데이터 삽입, 삭제가 느리다.
LinkedList는 데이터 삽입, 삭제가 빠르지만 검색이 느리다. 왜냐하면 원하는 위치에 한 번에 접근이 어렵기 때문이다.
HashMap, HashTable 차이를 설명하세요.
동기화 지원 여부와 null 값 허용 여부의 차이가 있다.
HashTable
--> 병렬처리를 할 때 thread-safe하며 null 허용한다.
HashMap
--> 병렬처리를 할지 않을 때 thread-safe하지 않으며 null 허용한다.
BST(이진 탐색 트리)와 Binary Tree를 설명하세요.
이진 트리는 자식 노드가 최대 2개인 노드를 말하며 이진 탐색 느리는 이진 탐색과 연결 리스트를 결합한 구조를 말한다.
이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 입력과 삭제가 가능하며 이진 탐색 트리는 왼쪽 트리 부모>값, 오른쪽 트리는 부모<값으로 구성되어 있다.
