가장 기본 자료구조인 Array부터 시작하겠습니다~~
Array
특징
인덱스로 해당 원소에 접근할 수 있는 자료구조
👑 READ
random access가 가능해 인덱스 값을 알고있으면 빠르게 원하는 값에 접근할 수 있음
👉 read 작업에 최적화된 구조
👉 시간복잡도 = O(1)
Search
✅ Worst Case(정렬되지 않은 경우)
-
선형탐색
: 말그대로 선형! 일자로 하나씩 탐색
: 시간복잡도 = O(n) -
이진탐색
: 전체 배열 길이를 절반씩 나눠서 탐색
: 시간복잡도 = O(n)
✅ Best Case(정렬된 array일 경우)
시간복잡도 = O(log(n))
Insert, Delete
Insert와 Delete의 과정에서는 순서가 있다는 특성이 부정적으로 작용
👉 순서 유지로 인한 shift가 cost를 발생시킴
✅ Worst Case(첫 번째 위치에 작업이 이루어질 경우)
모든 정렬을 다시 해야하기 때문에 시간이 가장 오래걸림
시간복잡도 = O(n)
✅ Best Case(배열의 마지막 위치에 작업이 이루어질 경우)
재정렬 필요가 없으므로 시간이 오래걸리지 않음
시간복잡도 = O(1)
이러한 시간복잡도 문제를 해결하기 위한 구조로 Linked List가 있습니다.
Linked List
특징
- 연속적인 메모리 위치에 저장되지 않고 포인터(링크)를 사용해 연결되는 데이터 구조
- 노드 단위로 구성된 선형 구조
Linked List는 배열과 달리 메모리에 연속적으로 배치되지 않고, 각 노드가 임의의 메모리 위치에 할당됩니다. 그래서 중간 위치에 삽입 및 삭제 작업 시 O(1)의 시간 복잡도를 가집니다👍👍
👑 Insert
- 맨 앞에 삽입: O(1)
- 맨 뒤에 삽입: O(1)
- 중간에 삽입: O(1) (단, 삽입할 위치를 찾는 탐색 작업은 O(n)이 소요될 수 있습니다.)
👑 Delete
- 맨 앞 삭제: O(1)
- 맨 뒤 삭제: O(n) (단, 맨 뒤 노드에 바로 접근하는 경우는 O(1)입니다.)
- 중간 삭제: O(n) (삭제할 위치를 찾는 탐색 작업이 필요)
그러나 특정 위치에 접근하려면 첫 번째 노드부터 순차적으로 탐색해야 하기 때문에 탐색 작업은 O(n)의 시간 복잡도를 갖습니다.
Search
- 특정 값 탐색: O(n) (평균적으로 n/2번의 노드를 탐색해야 함)
- 특정 위치 탐색: O(n) (순차적으로 인덱스를 찾아야 함)
💡 자료구조를 선택할 때는 사용하는 연산의 종류와 빈도, 성능 요구 사항을 고려하여 적절한 자료구조를 선택하는 것이 중요합니다!!
🙋♀️: Linked List가 삽입과 삭제엔 효율적이지만 탐색에는 그렇지 않은 이유가 무엇인가요?
Array List
비교
Array: 인덱스로 빠르게 값을 찾을 수 있음(READ에 최적화!)
LinkedList: 링크로 연결되어있어 주소값만 수정하면 됨(Insert, Delete에 최적화)
ArrayList: (Search에 최적화)
자세히>>
Array
- 장점: 인덱스로 빠르게 값을 찾을 수 있음
- 단점: 사이즈와 순서가 고정되어있어 배열 수정(삽입, 삭제) 시 비효율적
이를 해결하기 위해!
Linked List
- 장점: 크기가 정해져있지 않아 삽입과 삭제 시 효율적
- 단점: 검색 시 시간이 오래걸림
Array List
- 장점: 인덱스가 있어 검색이 빠름
