[자료구조] 선형 자료구조
선형 자료구조
데이터를 일렬로 나열한 형태로 저장하는 자료구조
배열
배열은 인덱스(index)로 해당 원소(element)에 접근할 수 있어 찾고자 하는 원소의 인덱스 값을 알고 있으면 O(1)에 해당 원소로 접근. RandomAccess가 가능해 속도가 빠르다는 장점
하지만 삽입 또는 삭제의 과정에서 각 원소들을 shift 해줘야 하는 비용이 생겨 이 경우 시간 복잡도는 O(n)이 된다는 단점
연결리스트
각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있기 때문에 이 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1)로 해결
하지만 LinkedList는 원하는 위치에 한 번에 접근할 수 없다는 단점. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인해봐야 함
데크
양방향 큐
맨 앞과 뒤에 데이터를 삽입하고 삭제할 수 있게 해주는 자료형
양 끝 엘리먼트에 대한 append, pop이 빠르다는 장점
삽입 제거 시, **일반적인 리스트는 연산에 O(n)**인 데에 반해, 데크는 O(1)로 성능이 매우 빠르다.(리스트는 pop을 하면 모든 값들이 앞으로 당겨지는 현상 이 발생, 당겨지는 연산을 안한다. 이는 덱을 사용하는 결정적 이유)
스택
선입 후출(Last In First Out)의 자료구조
한쪽 끝에서만 자료를 넣거나 뺄 수 있다
큐
선입 선출(First In First Out)의 자료구조
삽입(rear), 삭제(front)가 각각 다른 끝(front, rear)에서 이루어진다.
List
리스트는 순서와 중복이 있는 자료구조
내부적으로 인덱스 존재
가변적인 배열, 배열이 자동으로 늘어남
- ArrayList
- 단방향 포인터 구조 데이터 순차적 접근(조회)가 빠름
- LinkedList
- 양방향 포인터 구조 데이터 삽입, 삭제가 빠름
Set
순서 없고 중복이 존재할 수 없는 자료구조
인덱스를 사용하지 않는다
빠른 검색 속도를 갖고 있다.
인덱스가 따로 존재하지 않기 때문에 iterator 사용
- HashSet
- 입력 순서를 보장하지 않으며, 데이터의 중복을 허용하지 않음
- LinkedHashSet
- 입력 순서를 보장하며, 데이터의 중복을 허용하지 않음
- TreeSet입력하는 데이터가 사용자 정의 객체인 경우 Comparable을 구현하여, 정렬 기준 설정 가능
- (default) 입력한 데이터의 크기가 비교 가능한 경우 오름차순으로 정렬되며, 데이터의 중복을 허용하지 않음
Map
키와 데이터를 같이 저장할 수 있는 자료구조
Key, Value의 한 쌍으로 이루어진 데이터의 집합
순서가 유지되지 않는다
Key에는 중복된 값이 입력될 수 없다
Value의 중복은 허용된다
뛰어난 검색 속도를 갖고 있다
인덱스가 따로 존재하지 않기 때문에 iterator 사용
- HashMap
- Key(키)에 대한 입력 순서를 보장하지 않으며, 중복 Key(키)를 허용하지 않음
- LinkedHashMap
- Key(키)에 대한 입력 순서를 보장하며, 중복 Key(키)를 허용하지 않음
- TreeMap(default) 입력한 Key(키)데이터의 크기가 비교 가능한 경우 오름차순으로 정렬되며, 중복 Key(키)를 허용하지 않음
- 입력하는 데이터가 사용자 정의 객체인 경우 Comparable을 구현하여, 정렬 기준 설정 가능
- 레드-블랙 트리(Red-Black Tree)를 기반으로 Key&Value를 저장
질문
자료구조 중 많이 사용해본 것과 사용한 이유?
배열, 구현이 쉽고 정해진 데이터가 있을 때 인덱스로 쉽고 빠르게 값들에 접근할 수 있다. 하지만 데이터 삽입 삭제 할 때는 직접 데이터를 옮겨야 하는 번거로움이 있어 이때는 연결 리스트를 사용.
Stack과 Queue의 차이점은 무엇인가요?
스택은 후입선출(LIFO), 큐는 선입선출(FIFO)라고 말한다.
List와 Set의 차이점과 사용해본 경험
List는 기본적으로 데이터들이 순서대로 저장되며 중복을 허용한다.
Set은 순서가 보장되지 않고 데이터들의 중복을 허용하지 않는다.
Array와 ArrayList의 차이가 무엇인가요?
Java에서 Array는 고정 크기인 반면, ArrayList는 크기가 가변적으로 할당된다.
ArrayList에 요소들이 꽉 차면, 크기를 자동으로 1.5배 정도 늘린다.
요소를 추가, 삭제 시 메모리를 재할당 하기 때문에 Array보다 속도가 느리다.
Array에는 primitive type(int, byte, char)와 object type이 가능하지만, ArrayList는 object type만 가능하다.
Array와 LinkedList의 차이가 무엇인가요?
메모리 할당
Array : 선언시 컴파일 타임에 할당(정적 메모리 할당) ⇒ stack 섹션에 할당 됨
LinkedList : 새로운 요소가 추가 될 때 런타임에 메모리 할당(동적 메모리 할당) ⇒ heap 섹션에 할당 됨
검색
Array : 데이터가 연속된 메모리 공간에 저장되어 인덱스를 통한 빠른 접근 가능
LinkedList : 데이터가 연속된 메모리 공간에 저장되지 않아, 직접 각 요소를 탐색해서 접근 가능
ArrayList와 LinkedList의 차이가 무엇인가요?
기본적으로 Array, LinkedList의 차이와 비슷.
ArrayList는 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해서 임시 배열을 생성해 데이터를 복사하는 방법을 사용한다.
LinkedList는 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 위치를 저장한다.
순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다
중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다