Array

Array란?

배열은 같은 타입의 데이터들을 순차적으로 저장하는 자료구조입니다. 데이터들이 순차적으로 저장되기 때문에 배열의 각 원소는 시작 원소로부터의 상대적 위치를 나타내는 index 를 가지며 이 index 를 통해 각 원소에 O(1) 만에 접근할 수 있습니다. 즉, 배열은 Random Access가 가능한 자료구조입니다.

Operation

배열의 각 원소는 연속된 메모리 공간에 순차적으로 저장됩니다. 이러한 특성 때문에 배열은 배열의 시작 주소와 index 를 통해 Direct Access할 수 있고 따라서 배열의 탐색 연산은 O(1) 만에 수행됩니다.

삽입 연산과 삭제 연산도 단순히 배열 원소에 값을 삽입하거나 삭제하는 경우엔 O(1) 만에 수행됩니다. 이 경우 값이 비어 있는 원소가 존재할 수 있고 따라서 메모리가 낭비될 수 있습니다.

반면 원소 자체를 삽입하거나 삭제하는 경우엔 저장된 원소들의 연속성을 위해 다른 원소들을 옮기는 작업이 추가로 필요합니다. 최악의 경우 기존에 배열에 저장되어 있던 모든 원소를 옮겨야 하며, O(N) 의 시간복잡도를 갖습니다.

Memory

각 원소가 연속된 메모리 공간에 저장되기 때문에 기존에 배열에 할당된 메모리 공간을 초과하여 데이터를 저장하는 것은 에러를 발생시킬 수 있습니다. 따라서 배열의 크기를 늘려야 할 경우 크기가 큰 새 배열을 만들고 기존 배열에 있던 데이터를 복사하는 방법을 사용합니다.

Array Doubling

배열의 크기를 증가시킬 때 기존 배열 크기의 두 배만큼 증가시키는 방법. 이 방법에 소모되는 비용은 배열의 한 원소를 복사하는데 드는 비용을 t 라고 할 때, 2 · t · n 보다 작음.

List

List란?

리스트는 배열처럼 데이터를 순차적으로 저장하는 자료구조입니다. 하지만 배열과 달리 값이 비어 있는 원소를 허용하지 않고 데이터가 연속된 메모리 공간에 저장될 필요가 없으며 따라서 인덱스가 필요하지 않습니다. 대신 리스트는 각 원소 간의 순서가 중요한 자료구조입니다. 리스트에서 각 원소는 노드(Node) 라고 부르며 이 노드들의 순서 를 통해 각 노드에 접근할 수 있습니다.

Linked List

연결 리스트에서 각 노드들은 데이터와 다음 노드를 가리키는 포인터를 가지며 이 포인터로 각 노드가 연결되어 순서를 갖습니다. 연결 리스트에서 첫 번째 노드는 Head 라고 부르며 마지막 노드는 Tail 이라고 부릅니다. 그리고 이 Head 와 Tail 을 통해 탐색, 삽입, 삭제 연산을 수행합니다.

Linked List Operation

연결 리스트에서 탐색 연산은 Head 부터 탐색을 시작해서 원하는 원소를 찾을 때까지 포인터를 통해 노드들을 추적해 나가야 합니다. 따라서 최악의 경우 O(N) 시간복잡도를 갖습니다.

삽입 연산은 삽입하려는 노드를 x, 삽입하려는 위치 앞 노드와 뒤 노드를 각각 prev, next 라고 할 때, prev 는 x 를 가리키게 하고 x 는 next 를 가리키도록 해야합니다. 이 과정은 O(1) 시간복잡도를 갖지만 삽입하려는 위치를 찾아야 하기 때문에 최악의 경우 O(N) 시간복잡도를 갖습니다.

삭제 연산은 x 를 삭제하고 prev 가 next 를 가리키도록 해야합니다. 이 과정은 O(1) 시간복잡도를 갖지만 삽입 연산과 마찬가지로 삽입하려는 위치를 찾아야 하기 때문에 최악의 경우 O(N) 의 시간복잡도를 갖습니다.

Doubly Linked List

이중 연결 리스트는 연결 리스트와 달리 각 노드가 이전 노드를 가리키는 포인터를 추가로 갖습니다. 연결 리스트에 비해 메모리를 더 사용하지만 양방향 탐색이 가능하다는 장점이 있습니다.

Memory

각 노드가 포인터를 통해 이전 노드와 다음 노드의 메모리 상 위치를 가리키고 있기 때문에 노드를 연속된 메모리 공간에 저장할 필요가 없습니다. 따라서 리스트 확장이 편리합니다. 하지만 한 노드의 포인터가 잘못됐을 경우 다른 노드에 접근할 수 없게 될 수도 있다는 문제가 존재합니다.