본문 바로가기

CS 과목(CS科目)/자료 구조(Data Structure)

Array List vs Linked List

 

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를 만들었지만, 정작 본인은 안 쓴다고 함" ㅋㅋㅋㅋㅋ