공부한 내용!🤓
자료 구조(Data Structure)
자료를 효율적으로 이용할 수 있는 방법론.
데이터를 구조적으로 표현하는 방식들을 자료 구조라고 한다.
자료 구조의 종류를 나누어 보자면...
원시 구조 / 선형 구조 / 비선형 구조
- 원시 구조 : 정수, 실수, 문자...
- 선형 구조: 배열, 연결 리스트, 스택, 큐, 덱
- 비선형 구조 : 트리, 그래프
물리적 구조 / 추상적 구조
- 물리적 구조 : 정수, 실수, 문자, 배열, 연결 리스트
- 추상적 구조 : 스택, 큐, 덱, 트리, 그래프
1. 배열
같은 타입의 데이터가 순차적으로 저장된 구조.
index를 통해 index번째에 해당하는 요소에 접근할 수 있다.
데이터의 크기와 메모리상 저장된 위치가 고정적이다. 한 번 배열을 만들어두면 원소의 갯수만큼 메모리에서 공간을 차지하게 된다.
장점 : n번째 요소에 접근 속도가 빠르다.
2. 리스트
데이터가 순서에 따라서 빈틈없이 연속적으로 위치하는 데이터 구조.
1) Array List
... java에서만 사용되는 개념이라고 하던데...그럼 자료구조의 한 종류로 볼 수 없나요?
배열을 이용해서 리스트를 구현한 구조.
배열의 경우 중간의 요소를 삭제하게 되면 그 공간은 null이 된다. 따라서 메모리 낭비가 생길 수 있는 단점이 있다.
array list는 중간의 빈 공간을 그 다음 요소가 순차적으로 메꾸면서, 빈틈이 없는 연속적인 배열이다.
장점 : array의 장점인 index를 사용할 수 있어, n번째 요소 접근이 빠르다.
단점 : 데이터 추가와 삭제가 느리다.
2) Linked list
요소간 연결을 이용해서 리스트를 구현한 구조.
linked list에서는 연결된 요소를 node라고 한다. node는 값(value)과 다음 노드의 주소(next)가 담겨져있다.
장점 : 추가와 삭제가 빠르다
단점 : n번째 요소로 접근하는 속도가 느리다. n(O)
- 단순 연결 리스트
- 이중 연결 리스트
- 원형 연결 리스트
더 궁금한 점🧐
Swift의 array는 엄밀히 말해서 자료구조-배열로 볼 수 있을까?
자료구조-리스트에 해당하는 것이 아닐까?
그렇게 생각한 근거는 아래와 같다.
- swift array는 요소를 삭제했을 때, array list처럼 뒤의 요소들이 한칸씩 당겨지며 빈틈을 채운다. 그래서 배열의 크기가 가변적이다.
- 자료구조- 배열은 크기가 고정적이다. 하지만 swift array는
appendremove와 같은 메서드로 요소를 추가, 수정할 수 있기 때문에 크기가 유동적이다. append메서드의 시간 복잡도는 O(1)이다. 단,append하기 전, 메모리 저장공간을 재할당하거나 다른 복사본과 메모리를 공유하고 있다면 시간 복잡도는 O(n)이 된다.
swift의 array는 내부적으로 어떻게 구현이 되어 있을지 궁금하다.
