Linked List : 연결 리스트 & Array

연결 리스트는 배열과 연속한 형태 내용을 나열한다라는 공통점이 있지만 그 상세한 방식에는 다소 차이가 있다.

빠르게 생각해보면

• 연결 리스트는 원소가 본인의 contents 뿐만 아니라, 같이 이전 원소 또는 다음 원소에 대한 위치 정보를 가지고 있다.
  
  • 굳이 따지고 들어가면 연결 리스트의 원소는 기억해야 할게 다량 있기 때문에 메모리상 cost가 다소 있는 편이다.
  • 또 메모리 상에서 연속적이지 않다. 이건 컴퓨터의 cache memory랑 연결되는 건데, cache에 많이 의존하는 프로그램은 연결리스트 사용에 다소 조심스럽게 접근해야 할 것 같다.
    • cache는 지역성 성질 때문에 물리적으로 위치가 유사한 곳에 있을 때 보다 빠른 성능으로써의 사용이 가능한 점을 참고하기
  • 하지만 처음 정의에서 특정한 크기를 정의하지 않아도 되고, 사용 하고 싶은 만큼만 사용 할 수 있는 것이 큰 메리트이다.
• 배열은 index에 대해 원소가 직접 어쩌니를 논하진 않는다. 심지어 C언어인 경우에는, int array 기준으로 [1]과 [2]의 주소 상 차이는 4바이트에 불과하다. 그 뜻은 그냥 옆에 있는거다! 라고 할 수 있다는 것이다. 원소는 자기 자신의 값만 잘 보전하고 존재하면 된다.
  • 연속적인 데이터를 가장 효율적으로 저장하기 위한 방법은 아직까지도 배열이 압도적이다. 메모리 상으로도 속도상으로도 아주 적합하다.
  • 정말 큰 단점은 처음 정의에서 공간 배정이 필요하다는 점이다. 요즘엔 dynamic array라는 식으로 동적 공간 배열을 아무렇지 않게 사용 할 수 있지만, 공간을 특정하게 고정한다는 것에서 오는 profit보다 non-profit의 여지가 크게 와닿는 경우가 많다.

특정한 원소를 찾기 위한 시도는 각 특징이 있으니 그에 대해선 논하지 않겠다.
내 생각에 둘 중 하나만 써야한다면 dynamic array 형태가 매우 우수하지 않나 생각한다.

그럼 이제 언어별 기본으로 제공되는 라이브러리는 어떻게 구성되있는가를 간략하게 보겠다. 파일럿 코를 동원하겠다.

Python

1. list : 제일 기본적인데 아주 강력한 동적 배열이다.
2. array : 고정 크기, 데이터 타입은 고정되어야 하는 배열이다.
   • 1번과 2번은 모두 배열 기반으로 동작한다. 연속적 메모리, 캐시 친화성에 대해 중요도가 있다.
3. deque : 양쪽 끝에서 데이터를 삽입/삭제 할 수 있는 구조의 나열형 자료구조이다.
   • deque는 내부적으로 이중 연결 리스트 기반으로 작동한다. 따라서 캐시 메모리의 적중률은 다른 자료구조에 비해 낮다.

C++ STL

1. array : 그냥, 흔하게 알고 있는 그런 배열이다.
2. vector : 동적 배열이다.
   • 여기까지의 내부 구조는 배열이다.
3. deque - 배열과 연결 리스트 사이 그 어딘가
   
   
4. list
5. forward_list
   • 이 두 개는 연결 리스트에 좀 더 가깝다.