[Algorithm] 배열과 연결리스트 (Array & Linked List)

1. 개요
배열과 연결리스트는 둘 다 데이터를 저장하는 방식의 일종이다. 이 두 가지 기본적인 형태가 수많은 자료구조들을 만드는 뼈대가 된다.
과장을 살짝 보태자면, 배열 또는 연결리스트에 데이터를 어떤 식으로 효율적으로 저장하고 관리할 것인지를 궁리하는 것이 알고리즘이라고 할 수 있고, 그 배열 또는 연결리스트에 특정 알고리즘을 구현한 것을 자료구조라고 할 수 있다. 물론, 배열과 연결리스트도 또한 하나의 자료구조이다.

2. 배열(Array)이란?
배열이라는 것은 특정 자료형(Data Type)들이 메모리 공간상에서 연속적으로 이루어져 있는 자료구조를 의미한다.
예를 들어, 32bit 운영체제를 기준으로 4 Byte의 int형 정수들을 담는 배열은, 메모리 공간상에서 비엔나 소시지 처럼 연속적인 4 Byte의 공간으로 연결되어 있다.

그리고, 이 공간들은 0으로 시작하는 Index값(그림에서의 0~9)에 의해 즉각적으로 참조될 수 있다. 그 이유는 메모리 공간상에서 연속적으로 이루어져 있음을 알기 때문입니다. 실제로 배열을 하나 만들 경우, 컴퓨터는 그 배열의 시작주소와 각 원소들의 자료형 정보를 저장하게 된다. 따라서, 위처럼 4 Byte의 int형 정수들로 이루어진 배열의 시작주소를 1024이라고 한다면, 배열의 i 번째 원소에 접근을 하고 싶을 때는 단순히 1024 + i * 4 Byte에 접근하여 데이터를 참조하면 된다.
이 배열이라는 자료구조는 거의 모든 프로그래밍 언어에 기본적으로 탑재되어 있다. 대부분의 경우 배열의 이름과 대괄호([, ])를 사용하여 배열을 표현한다.
예를 들어, 배열의 이름을 myArray라고 한다면, 네 번째 칸에 7이라는 정수를 집어 넣고 싶을 때 myArray[3] = 7과 같이 표현하면 된다. 배열의 Index가 0부터 시작한다는 사실을 망각하면 안된다.
만약 두 번째 칸에 저장되어 있는 값을 불러오고 싶을 때, int temp = myArray[1]과 같이 표현하면 된다.
그렇다면, 배열의 특징은 무엇일까? 배열은 데이터를 메모리상에 연속적으로 나열해두었다는 특성 때문에, 데이터에 대한 접근이 엄청나게 빠르다는 장점이 있다. 앞서 언급했듯이, Index 값을 통해 바로 원하는 공간에 가서 자료를 확인할 수 있기 때문에, 딱 한 번의 접근만 필요하므로, 수학적으로 O(1)의 시간복잡도를 가지게 된다.
따라서, 데이터를 검색하거나 정렬할 때, 빠른 접근이 필수적인 자료구조에 많이 활용된다.
하지만, 단점으로는 배열의 최대 크기를 변경할 수 없다는 점이다. 처음에 10개의 연속된 공간을 만들었다면, 자료를 최대 10개까지만 저장할 수 있으며, 만약에 3개만 저장하고 싶다면 7개의 공간을 낭비하게 되는 셈이다. 특히, 배열을 제공하는 쪽에서 10개의 칸만 제공했는데, 사용자(User)가 10개 이상의 데이터를 넣으려고 하면 문제가 발생할 수 있다.
또한, 데이터의 추가 기능만 존재하면 상관없지만, 만약 배열에 저장된 데이터를 삭제할 수 있는 상황이라면, 골치 아픈 문제가 발생한다. 중간에 있는 데이터가 삭제되면, 빈 공간을 어떻게 처리해야 할까? 두 가지 방법이 있다. 첫 번째는 빈 공간을 그대로 두는 것이고, 두 번째는 그 빈 공간을 메꾸는 것이다.
만약 그대로 두는 방식을 따른다면, 데이터를 추가할 때마다 빈 공간이 어디에 있는지 찾아야 하는 수고를 감수해야 한다. 최악의 경우, 크기 N의 배열에 데이터를 추가 할 때, N - 1개의 공간을 탐색하면서 빈 공간을 찾아야 한다. N개의 데이터를 추가한다면, O(N^2)의 시간복잡도를 따르게 된다.
그렇다면, 메꾸는 방식을 따른다면 어떨까? 배열의 중간에서 삭제 연산이 수행될 경우, 해당 빈 공간의 뒤에 있는 모든 데이터들을 한 칸씩 앞으로 이동시키는 것이다. 이 경우, 모든 데이터들이 빈 공간 없이 붙어있기 때문에, 데이터의 추가 과정에서 별도의 빈 공간 탐색이 필요하진 않지만, 삭제를 할 때마다 많은 데이터들을 이동시켜야 한다는 단점이 있다. 최악의 경우, 크기 N의 배열에서 데이터 하나를 삭제할 때 만약 그 데이터가 가장 첫 번째 데이터라면, N - 1개의 데이터를 한 칸씩 앞으로 이동시켜야 한다. N개의 데이터를 삭제한다면, O(N^2)의 시간복잡도를 따르게 된다. 앞선 경우와 동일한 비용이 발생한다.
따라서, 데이터의 삽입 또는 삭제 등의 연산이 빈번하게 발생하여 데이터의 수가 다이나믹하게 변하게 되는 자료구조에서는 배열을 활용하는 것이 비효율적이다.

3. 연결리스트(Linked List)란?
연결리스트라는 것은 여러개의 노드(Node)이 연결된 형태의 자료구조를 의미한다. 메모리 공간상에서 각 노드들이 연속적으로 이루어져 있지 않고 흩어져 있으며, 각각의 노드가 자신의 다음 노드의 위치를 알고 있는 형태로 구현된다.
그렇다면 노드(Node)란 무엇일까? 배열에서의 한 칸과 같다고 생각하면 편하다. 각각의 노드들은 내부적으로 자신의 안에 포함할 데이터(Data)와 다음 노드의 위치 정보(Link)를 갖고 있다.

따라서, 노드의 위치 정보를 기반으로 연결이 되어 있는 형태가 바로 연결리스트이고, 다음과 같은 형태로 나타난다.

노드는 원하는 대로 커스터마이징하여 구현할 수 있다. 예를 들어, 한 개의 노드가 두 종류의 데이터를 가지게 할 수도 있다. 또는 노드가 자신의 다음 노드 뿐만 아니라, 자신의 이전 노드의 위치를 알게 해서 두 개의 노드가 서로의 위치를 알게 할 수도 있다. 이것은 이중 연결리스트(Doubly Linked List)라고 부른다. 또한, 마지막 노드가 맨 처음 노드(Head Node)의 위치를 알게 되면, 머리와 꼬리가 연결된 형태가 되어 원형 연결리스트(Circular Linked List)가 탄생하게 된다.
그렇다면, 연결리스트의 특징은 무엇일까? 각 노드들이 메모리 공간상의 어디에 위치하는지는 각각의 노드들만 알고 있다. 그리고 연결리스트의 사용자는 제일 첫 번째 노드의 위치(Head Node)만 알고 있게 된다.
예를 들어, 3번 째 노드의 자료를 보고 싶으면, Head Node에게 2번 째 노드의 위치를 물어보고, 그다음 2번 째 노드에게 3번 째 노드의 위치를 물어본 뒤에 3번 째 노드의 자료를 확인해야 한다.
이는 수학적으로 보면 최악의 경우, 즉, N개의 자료가 있는 연결리스트에서 찾고자 하는 값이 제일 마지막 노드에 위치할 때, N번의 접근을 해야 한다는 의미이다.
따라서, O(N)의 시간복잡도를 따른다. 데이터의 접근에 있어서 O(1)의 시간복잡도를 따르는 배열과 비교했을 때, 연결리스트는 상대적으로 불리하다.
그러므로, 자료에 대한 접근이 잦은 자료구조에서는 연결리스트의 사용을 지양해야 한다.
그런데, 배열과 달리 노드를 추가하고 제거하는 과정을 통해 최대 노드의 수를 언제든지 변경할 수 있기 때문에, 메모리 공간을 유동적으로 사용할 수 있다. 딱 원하는 만큼만 사용할 수 있으며, 예측할 수 없는 사용자가 데이터를 무분별하게 추가하더라도 그에 맞게 연결리스트가 자동으로 확장, 축소되기 때문에 문제가 되지 않는다.
그러면 삽입과 삭제의 경우에는 어떨까? 리스트의 중간에 데이터를 추가하고자 한다면, 단순히 리스트 중간의 연결을 끊은 뒤에 추가될 데이터를 가진 노드로 연결시켜주면 된다.

예를 들어, 노드 A와 노드 C사이에 데이터 B를 삽입하고자 한다면, 먼저 데이터 B를 포함한 노드 B를 생성한 뒤, 노드 A의 Link 부분에 노드 B의 위치를 기록하고, 노드 B의 Link 부분에 노드 C의 위치를 기록하면 추가가 완료된다.

삭제는 어떨까? 추가와 반대로, 노드 A의 Link에 다시 노드 C의 위치를 기록해버리면 된다. 배열처럼 삭제로 인한 빈 공간에 대해 전혀 걱정할 필요가 없다. 단순히 두 개 정도의 노드의 Link에 위치 정보만 기록하는 것으로 데이터의 추가 및 삭제가 이루어진다. 즉, O(1)의 시간복잡도를 따르는 것이다.
따라서, 연결리스트는 데이터의 빈번한 추가와 삭제로 인해 데이터의 수가 다이나믹하게 변하는 자료구조에 알맞은 형태라고 할 수 있다.

​4. 배열과 연결리스트의 활용
배열과 연결리스트의 특징을 살펴보면, 시간적인 측면과 공간적인 측면의 효율성에 있어서 서로 상충되는 관계라는 것을 알 수 있다. 어떤 자료구조를 선택할 것인지 판단할 때, 앞서 언급한 기본적인 특징들을 잘 고려해야 한다.

배열: 데이터에의 접근은 빠르지만, 메모리 공간활용에 제약이 있으며 데이터의 추가와 삭제가 비효율적이다.
연결리스트: 데이터에의 접근이 다소 느리지만, 메모리 공간활용 및 데이터의 추가와 삭제가 효율적이다.

물론, 이외에도 여러가지 특징들이 더 존재한다. 예를 들어, 배열의 경우 데이터의 추가와 삭제가 배열의 중간에서 발생하지 않고, 반드시 배열의 끝에서만 발생한다는 보장이 있다면, 연결리스트보다 훨씬 효율적인 자료구조가 될 수 있다. 따라서, 스택(Stack)처럼 데이터가 추가되고 삭제되는 위치가 정해져 있는 자료구조의 경우 배열을 사용해도 전혀 문제될 것이 없다.
그리고, 연결리스트의 경우 데이터뿐만 아니라 Link를 위한 별도의 메모리 공간이 필요하기 때문에, 저장된 데이터의 양이 같더라도 배열보다 더 많은 메모리 공간을 점유하게 된다. 만약 int형 정수 하나를 저장하는 노드가 Link를 수십 개 가지고 있다면, 필요한 데이터보다 부가적인 정보가 더 많은, 즉, 배보다 배꼽이 더 큰 기이한 형태가 된다.
또한, 배열은 데이터를 일 열로 늘어놓은, 즉, 순차적인 자료구조의 틀에서 벗어나기 힘들지만, 연결리스트의 경우는 트리나 그래프 등 복잡한 구조를 가진 자료구조를 만들 때 유연하다는 장점이 있다.
이러한 특징들을 종합해보면, 배열은 고정된 양의 데이터를 임시로 저장해두고 수시로 데이터에 접근하는 경우에 유용하게 사용될 수 있으며, 연결리스트는 데이터의 추가와 삭제가 빈번하게 일어나거나, 복잡한 형태의 자료구조를 만들 때 유리하다.
그렇다면, 이 두 가지의 불완전한 자료구조를 바탕으로 데이터에의 접근도 빠르고 메모리 공간도 효율적으로 사용할 수 있는 자료구조로 바꿀 수는 없을지 고민을 해보자. 이 방법을 강구하는 것이 바로 일종의 알고리즘이며, 현재 다양한 알고리즘들을 구현한 자료구조들이 연구되어 세상에 알려져 있고, 실제로 준수한 성능을 보이고 있다.
사실, Java 언어의 java.util 패키지나 C++ 언어의 STL(Standard Template Library) 등 전문가들에 의해 설계되고 검증된 자료구조들이 상용화되어 있기 때문에, 직접 자료구조를 설계하고 만들 일은 거의 없다. 하지만, 프로그래밍 역량 평가나 알고리즘 시험 등을 준비하고 있다면, 배열과 연결리스트의 특징을 잘 숙지해두고 문제에서 요구하는 자료구조를 직접 설계하고 구현까지 할 수 있는 역량 정도는 갖추어야 한다.

5. Source Code
https://github.com/arkainoh/algorithms/blob/master/c/LinkedList.c