List ADP의 사용 예시
문제1 ~100까지의 정답을 저장해야 한다고 해보자.
1. 정답들을 저장할 때, 문제의 [순서]대로 저장을 해야 하며,
2. 그 정답들 중, [중복]되는 정답들이 있을 것이다.
인기가 있는 프로그래밍 언어일수록 [순서] 상 되도록 앞에 저장을 해야 할 것이다.
( 이 예시에서는 중복이 없다 )
-> Set이나 Map을 사용하는 것이 더 적절한 상황이 아니라면 거의 대부분 List ADT를 사용한다고 보면 된다.
(Set,Map은 추후에 다룸)
List ADT의 구현체 1 - ArrayList
배열을 기반으로 구현되고, 구체적인 것은 너무 쉬우므로 넘어 간다.
List ADT의 구현체 2 - LinkedList
노드를 연결(linked)시키는 형태로 구현
ArrayList와 LinkedList의 차이점1
-> 메모리를 차지하는 방식이 다르다.
ArrayList는 배열을 기반으로 구현이 되므로, 메모리 상에 [연속적]으로 위치를 한다.( 배열의 타입이 기본형일 때는 맞는 소리이지만, 만약 배열의 타입이 레퍼런스 타입일 때는 그렇지가 않다)
LinkedList는 노드를 Pointer로 연결시키는 방식으로 구현을 하였기 때문에, heap 메모리에 [연속적]으로 저장되지 않는다.
ArrayList와 LinkedList의 차이점 2
-> 특정 데이터 조회시, ArrayList의 경우 O(1)이고, LinkedLIst의 경우 O(N)이다.
ArrayList는 배열로 구현이 돼 있기에, [인덱스]로 direct로 접근이 가능하다. 그러나,
LinkedList는 노드와 포인터 기반으로 구현이 돼 있기에, 예를 들어 4번째 노드의 key값을 알고 싶다 할 경우,
최악의 경우 head부터 tail까지 순차적(sequential) 탐색을 해야 하므로
탐색 속도에 있어서 LinkedList가 상대적으로 느리다.
ArrayList와 LinkedList의 차이점 3
-> 특정 데이터를 삽입 및 삭제 시 LinkedList의 시간 복잡도는 O(1)이고, ArrayList의 시간복잡도는 O(N)이다.
ArrayList는 배열을 기반으로 구현이 돼 있다.(정확히는 Dynamic Array로 구현이 돼 있다.)
고로, 배열의 중간에 데이터를 삽입 및 삭제를 하게 되면, 그 뒤의 데이터들을 모두 한 칸씩 뒤로 보내거나( 삽입 시 )
모두 한 칸씩 앞으로 당겨야 한다(삭제 시).
그러나, LinkedList는 노드와 포인터를 기반으로 구현이 돼 있기 때문에, 데이터 삽입 및 삭제 이외의 부가 작업이 없다.
ArrayList vs LinkedList
요즘 JAVA와 같은 경우에는, ArrayList가 최적화가 매우 잘 돼 있어서, LinkedList와 거의 차이가 없을 뿐더러, 오히려 성능
면에서 LinkedList를 뛰어 넘어서, 대부분의 개발자들이 LinkedList 대신에 ArrayList를 사용한다고 함.
JAVA의 LinkedList Class를 만든 사람이, "자기가 실제로 LinkedList를 만들었지만, 정작 본인은 안 쓴다고 함" ㅋㅋㅋㅋㅋ
'CS 과목(CS科目) > 자료 구조(Data Structure)' 카테고리의 다른 글
Tree Traversal - Pre-Order, In-Order, Post-Order(feat.이진 탐색 트리(binary search tree) (0) | 2023.04.01 |
---|---|
동적 배열(Dynamic Array) vs 연관 배열(Associative array) (0) | 2023.03.30 |
ADT 관점에서의 Map 개념 && Map의 구현체인 HashTable의 동작 원리 (0) | 2023.03.30 |
Priority Queue와 Heap의 차이점 (0) | 2023.03.30 |
DB Index에서 사용되는 B-Tree (데이터 삭제) (0) | 2023.03.10 |