[자료구조] Linked List와 Array를 알아보자.

Linked List는.. 2학년 자료구조 시간에 처음으로 접했던 친구인데요,

당시 Doubly Linked List를 직접 구현하고 접근, 탐색, 삽입/삭제를 모두 구현해오라는 과제에

심히 충격을 받았던 기억이 있습니다.

 

 

Singly Linked List

요건 Doubly Linked List

 

Singly Linked List, Doubly Linked List가 있고요,

Singly는 한쪽 방향으로 접근하고, Doubly는 전/후 노드로 접근(탐색) 가능하다는 점이 차이가 있겠네요.

Head의 Left는 NULL, Tail의 Right는 NULL로 구성해야 한다는 특이점이 있었구요.

 

Singly는 메모리 사용이 적고, 

Doubly는 노드의 삽입, 삭제가 상대적으로 빠르다는 특징이 있습니다.

 

오늘은 구현보다는, 시간복잡도를 복습해보고 Array와 비교해보는 시간을 가졌습니다.

	Linked List	Array
Access	O(n)	O(1)
Find	O(n)	O(n)
Insertion / Deletion	O(1)	O(n)
메모리 사용	- 필요할 때 마다 생성 - 메모리 효율적으로 사용(동적 할당) - 데이터 저장 공간 및 다음 노드 주소 저장공간 추가 필요	- 크기 미리 선언 - 수정 불가능(정적 할당)
방식	Node 존재	Index 존재
언제 유리한가?	추가, 삭제가 빈번할 때	접근, 탐색이 빈번할 때

 

테이블 하나로 정리되니 너무 편하네요.

 

그럼 각종 언어에서는 어떻게 사용되고 있을까요?

1. C++의 경우, 내장된 list가 내부적으로는 Doubly Linked List로 구현되어 있습니다.

2. Java의 경우, LinkedList 라는 클래스(자료형)가 존재하고, 이 역시 Doubly Linked List로 구현되어 있습니다.

3. 파이썬의 경우, 그냥 dynamic array라고 합니다.

4. 놀랍게도 Swift는 list가 따로 없고 Array만 있답니다. ㄷㄷ

 

삼성전자 Expert C형은 C++ STL보다 빠르게 구현해야 한다던데

이건 대체 누가 하는걸까요?

 

끝.