[Algorithm] 1. LinkedList

Linked List는 데이터를 노드의 형태로 저장.

노드에는

데이터와 다음 노드를 가르키는 포인터를 담은 구조로 이루어져 있음.

 

Node
Data	Next

Python 내장 함수의 시간 복잡도에서 List의 삽입과 삭제의 시간복잡도가 O(n)이 걸리는 것은

배열이 물리적인 데이터의 저장 위치가 연속적이어야 하므로 데이터를 옮기는 연산작업이 필요하기 때문이다.

 

하지만 Linked List는 데이터를 삽입, 삭제할 경우, 노드의 Next부분에 저장한 다음 노드의 포인터만 변경해주면 되므로

배열과 비교하였을 때 linked list가 효율적으로 데이터를 삽입, 삭제할 수 있다.

 

그러나, 안타깝게도 Linked List에서 특정 위치의 데이터를 탐색하기 위해서는 첫 노드부터 탐색을 시작해야 한다.

그 시간이 O(n)만큼 걸리게 되므로 탐색에 있어서는 배열이나 트리 구조에 비해 상대적으로 느리다고 할 수 있다.

 

• Linked List의 장점

1. Linked List의 길이를 동적으로 조절 가능

2. 데이터의 삽입과 삭제가 쉬움

 

• Linked List의 단점

1. 임의의 노드에 바로 접근 불가

2. 다음 노드의 위치를 저장하기 위한 추가 공간 필요

3. Cache Locality를 활용해 근접 데이터를 사전에 캐시에 저장하기 어려움

4. Linked List를 거꾸로 탐색 어려움

 

※ cache locality : 대부분 프로그램은 한번 사용한 데이터를 다시 사용할 가능성이 높고, 그 주변의 데이터도 곧 사용할 가능성이 높은 데이터 지역성을 가지고 있다. 데이터 지역성을 활용하여 메인 메모리에 있는 데이터를 캐시 메모리에 불러와 두고, CPU가 필요한 데이터를 캐시에서 먼저 찾도록 하면 시스템 성능을 향상시킬 수 있다.

 

 

• Python으로 Linked List 구현

Jupyter Notebook 사용