배열과 연결 리스트

배열과 연결리스트

컴퓨터의 자료구조에 대해서 배울때 처음 언급되는 것은 변수 이후에는 배열이다. 이러한 배열은 메모리 동적할당에 대해서 배우고 나서 연결리스트와 구분되어 한번 말이 나오게된다.

다음의 그림을 보자

배열은 간단히 말해서 메모리상에서 연속되어 할당되는 것이고 연결리스트는 메모리에서는 떨어져서 할당되나 특정 링크를 통해 연결되어 있는 것이다.

연속되어 할당되어있다는 것은 성능면에서 우수할수밖에 없는게 특정 데이터 타입으로 선언된 배열은 해당 타입의 크기 만큼 메모리를 할당 받고 있기 때문에 해당 크기만큼만 메모리 주소를 이동하면 바로 다음 데이터를 열람 할 수 있다. 하지만 연결리스트의 경우는 다르다. 현 노드가 다음 노드의 위치를 갖고 있기 때문에 배열과 같이 연속된 할당처럼 단순 연산만으로 다음 주소를 얻어낼수없고 때문에 모든 노드를 순회해서 읽어야하기 때문에 배열에 비해서 성능이 떨어진다.

그렇다면 연결리스트는 왜 쓰는 것일까?
바로 배열의 연속된 메모리 영역 할당때문에 크기 제한이 생겨버리는 한계때문이다. 연속된 메모리를 할당하여 쓰다가 추가적인 크기가 필요하다면 어떻게 될까? 배열의 경우에는 원하는 만큼 더 큰 메모리 영역을 미리 할당해두고 이전 배열에서 데이터를 읽어와서 하나하나 복사해야한다. 하지만 연결리스트의 경우에는? 제일 끝노드에 내가 원하는 만큼 붙이면 그만이다.

따라 간단히 정리하면 이렇다.

배열은?

• 데이터 삭제 및 추가가 적고 읽기 성능이 중요시될때 사용

연결리스트

• 데이터 삭제 및 추가가 많고 읽기 성능이 그보단 덜 중요할 때 사용

이러한 특징은 C언어와 같은 로우 레벨 언어에서 그렇고 사실 javascript나 python 같은 경우에는 또 조금 달라진다.

Javascript의 경우

Javascript에서도 array라는 이름의 자료형은 존재한다. 하지만 우리가 c언어에서 배운 배열과는 조금 궤를 달리한다. 기본적으로 javascript의 배열은 해시테이블 형태이다. javascript에서 배열을 쓸 때 자료형에 대해서 미리 선언하거나 걱정하지 않아도 되는 이유가 이것때문이다. 그렇다면 객체와 배열의 차이가 없을까? 그건 아니다. Javscript를 구동하는 V8엔진에서 해당 부분에 대해서 최적화를 해주기 때문이다. 배열처럼 구동할 수 있는 부분은 배열처럼 구동되게끔 해주기 때문에 일반 객체와는 2배정도 성능차이가 난다.

Python의 경우

Python의 경우도 마찬가지인데, C언어에서와 같은 배열은 아니다. ob_item이라는 리스트가 있고 이 리스트에 해당 배열의 주소값이 들어가있는 형태이다. 이러한 이중 포인터형태의 배열이라도 크기는 정해져있는데 이러한 크기를 꽉 채우게 되면 더블링이라는 형태로 추가 크기 할당을 진행한다.