배열 Array
배열은 데이터를 저장하고 구성하는 데 사용하는 가장 기본적인 데이터 구조 중 하나로, 보통 프로그래밍 언어의 밑바탕에 속한다.
배열은 연속된 메모리 공간에 데이터를 할당하는 자료구조이다.
동일한 자료형의 데이터들을 요소로 갖는 배열은 길이가 정해진채로 메모리공간에 할당된다. 배열의 요소들은 이어지는 메모리 주소 위에 순차적으로 할당되므로 요소의 index를 알고있다면 이에 접근 하는 것은 O(1)시간을 갖는다.
특정 요소의 메모리주소는
'배열의 시작점 메모리주소 + 인덱스 x 요소에 할당된 메모리 블록 개수'
로 계산할 수 있다..png)
배열의 크기를 늘리고 싶으나 할당된 공간의 사정이 여의치 않을때 컴퓨터는 메모리의 내용을 복사하여 확장된 크기의 새로운 배열을 다른 메모리 공간에 할당한다. 이런식으로 배열의 크기를 늘리는 것은 꾀나 비싼 작업이다. 또한 할당된 메모리공간은 사용하지 않는다면 잉여공간이 되어버리고 만다.이렇듯 배열은 '덩어리'같은 구조의 특성상 메모리공간 활용에 제약이 있다.
JavaScript에서의 배열
"JavaScript에서의 배열은 Hash Map이다. 이것은 다양한 자료 구조를 사용해서 구현될 수 있고, 그 중 하나가 바로 Linked List이다. 최근의 JavaScript 엔진은 모든 요소가 동일한 타입을 가지고 있는 배열인 경우 연속적으로 메모리를 할당한다. 그러나 이런 동일한 타입 배열에 다른 타입의 원소를 삽입하려고 할 때 JIT(Just in Time)컴파일러는 전체 배열의 구조를 해제하고 다시 예전의 배열처럼 비연속적인 메모리를 할당한다. 즉, 만약 우리가 코드를 제대로 작성한다면 JavaScript의 Array 객체는 실제 배열처럼 작동한다는 것이다."[1]
"배열은 프로토타입으로 탐색과 변형 작업을 수행하는 메서드를 갖는, 리스트와 비슷한 객체입니다. JavaScript에서 배열의 길이와 요소의 자료형은 고정되어 있지 않습니다. 배열의 길이가 언제든지 늘어나거나 줄어들 수 있기 때문에 JavaScript 배열들은 밀집도가 보장되지 않습니다. 보통 이 성질은 편리하지만, 목적에 맞지 않는다면 형식화 배열(typed array)을 사용하는 것을 고려해보세요."[2]
연결 리스트 Linked list
연결리스트는 각각의 데이터를 분리된 메모리 공간에 비연속적으로 할당하는 자료구조로 노드node들의 연결로 구성되어있다. 하나의 노드는 두개의 요소쌍으로 이루어져있으며 한 곳에는 데이터(value)를, 인접한 다른 한곳에는 연결된 노드(next node)의 주소를 저장한다.
배열과 달리 고정된 길이를 가지고있지 않기 때문에 잉여공간이 생기지 않고(대신 포인터 링크를 저장하기 위해 추가로 메모리가 소비된다.), 새로운 노드를 추가하여 길이를 확장하게 될 경우 유연하게 메모리 공간을 사용할 수 있다.양방향 연결 리스트 Doubly Linked list
이전 노드를 가르키는 포인터와 다음 노드를 가르키는 포인터를 모두 가진 연결 리스트이다. 연결 리스트에서 노드를 제거하기 위해선 제거할 노드의 위치와 이전 노드의 위치를 모두 알아야하는데 양방향 연결 리스트에서는 이전 노드의 위치에 쉽게 접근할 수 있으므로 단방향 연결 리스트에 비해 노드 제거에 수월하다.
순환 연결 리스트 Circular Linked list
모든 노드가 연결된 리스트로 마지막 노드가 첫번째 노드와 연결된 구조이다. 노드 사이의 연결은 단방향 또는 양방향일 수 있다. 순환 연결 리스트는 컴퓨팅 분야에서 특히 버퍼링(다양한 처리를 원활하게 실행시키려고 버퍼라는 임시 저장 공간에 데이터를 저장하는 작업)과 관련된 용도로 많이 사용된다.배열과 연결 리스트의 차이점
연결리스트는 연속된 메모리 공간에 할당되는 것이 아니기때문에 배열처럼 인덱스를 가지고 메모리 주소를 계산할 수 없다. 연결리스트에서 유일하게 위치에 대한 정보를 알려주는 것은 포인터 변수 ‘head’로, 리스트의 시작점을 알 수 있다. 구현하기에 따라 마지막 노드의 주소도 ‘tail’변수에 저장할 수 있다. (단방향)연결리스트는 head를 통해서만 접근 가능하며, 마찬가지로 특정 노드에 접근하기 위해서는 head에서 부터 시작해 연결된 모든 노드를 거쳐야만 한다. 이는 O(n)시간을 갖는다.
반면 새로운 노드를 삽입하는 것은 배열에 비해 단순하다. 만약 배열의 가장 앞부분에 새로운 요소를 삽입하게 된다면 모든 요소의 메모리 주소가 변경될 것이다. 그러나 연결리스트에서는 새로운 노드를 만들어 삽입되는 위치의 앞뒤노드와 연결해주기만 하면 된다. 이 작업 자체는 O(1)시간을 갖지만 노드를 탐색하는데 걸리는 시간까지 계산된다면 O(n)시간을 가질 것이다.
reference
[1] JavaScript의 배열(Array)의 발전과 성능에 대해서 자세히 알아보기
[2] Array_MDN
mycodeschool - Introduction to Linked list
mycodeschool - Data Structures: Arrays vs Linked Lists
⌜코드 없는 알고리즘과 데이터 구조⌟ 암스트롱 수베로 2021
