연결 리스트가 무엇인가 하면, 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조입니다. 원소들은 이곳 저곳에 흩어져있습니다.
첫 번째로 연결 리스트에서는 k번째 원소를 찾기 위해 O(k)의 시간이 필요합니다. 뭔가 좀 의아할 수 있는데, 연결 리스트의 구조 상 어쩔 수가 없습니다. 배열과 다르게 공간에 원소들이 연속해서 위치하고 있지 않기 때문입니다.
두 번째로 연결 리스트에서는 임의의 위치에 원소를 추가하거나 임의 위치의 원소 제거가 O(1)입니다. 이 성질이 배열과 비교했을 때 큰 차이가 있는 성질이고, 연결 리스트의 굉장히 큰 장점이기도 합니다.
세 번째로 메모리 상에 데이터들이 연속해있지 않으니까 Cache hit rate가 낮지만 할당이 쉽습니다. 물론 이 성질은 코딩테스트를 칠 때는 몰라도 상관없습니다.
첫 번째는 단일 연결 리스트입니다. 단일 연결 리스트는 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트입니다.
두 번째는 이중 연결 리스트입니다. 이중 연결 리스트에서는 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고 있습니다. 단일 연결 리스트에서는 주어진 원소의 이전 원소가 무엇인지를 알 수 없는데 이중 연결 리스트에서는 알 수 있습니다. 다만 원소가 가지고 있어야 하는 정보가 1개 더 추가되니 메모리를 더 쓴다는 단점이 있습니다. 참고로 STL에 연결 리스트가 있는데, 이 컨테이너의 이름은 list이고 구조는 이중 연결 리스트입니다.
세 번째는 원형 연결 리스트입니다. 원형 연결 리스트에서는 끝이 처음과 연결되어 있습니다. 그림의 예시는 단일 연결 리스트로 표현했지만 각 원소가 이전과 다음 원소의 주소를 모두 들고 있어도 상관이 없습니다.
배열과 연결 리스트는 메모리 상에 원소를 놓는 방법은 다르다고 해도 어찌됐든 원소들 사이의 선후 관계가 일대일로 정의가 됩니다. 즉, 원소들 사이에서 첫 번째 원소, 두 번째 원소, … 이런 개념이 존재하는 것입니다.
그래서 배열과 연결 리스트는 선형 자료구조라고 불립니다. 까마득한 후에 배우게 될 트리, 그래프, 해쉬 등은 비선형 자료구조의 대표적인 예시입니다.
배열과 연결 리스트는 둘 다 선형 자료구조여서 면접에서 둘의 비교하는 문제를 구술 시험으로 내기도 합니다. 꼭 면접 대비가 아니라고 하더라도 둘의 차이를 잘 알아야 적재적소에 배열이나 연결 리스트를 잘 써먹을 수 있을테니 둘의 장단점을 비교하는 시간을 가져보도록 하겠습니다.
첫 번째로 k번째 원소의 접근은 배열의 경우 O(1), 연결 리스트의 경우 O(k)입니다.
두 번째로 임의 위치에 원소를 추가하거나 제거하는건 배열의 경우 O(N), 연결 리스트의 경우 O(1)입니다. 그런데 엄밀히 말해서 연결 리스트에서도 3번째 원소 뒤에 20이라는 원소를 추가하고 싶다고 하면, 일단 3번째 원소까지는 찾아간 뒤에야 O(1)에 추가가 가능한거라 상황이 조금 다르긴 한데, 이건 구현 파트에서 자세하게 다루겠습니다.
메모리 상의 배치는 배열의 경우 연속이고 연결 리스트의 경우 불연속입니다. 마지막으로 추가적으로 필요한 공간, 즉 overhead를 생각해보면 배열은 데이터만 딱딱 저장하면 될 뿐 딱히 추가적으로 필요한 공간이 없습니다. 굳이 따지면 길이 정보를 저장할 int 1개가 필요할 수 있지만 이건 너무 미미하니 신경을 쓸 필요가 없을 정도입니다. 그런데 연결 리스트에서는 각 원소가 다음 원소, 혹은 이전과 다음 원소의 주소값을 가지고 있어야 합니다. 그래서 32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위이니 4N 바이트가 추가로 필요하고, 64비트 컴퓨터라면 주소값이 64비트(=8바이트) 단위이니 8N 바이트가 추가로 필요하게 됩니다. 즉 N에 비례하는 만큼의 메모리를 추가로 쓰게 됩니다.
이제 연결 리스트에서 제공되는 연산들을 하나씩 살펴보겠습니다. 첫 번째로 임의의 위치에 있는 원소를 확인/변경하는 연산인데, 계속 언급했듯이 배열과는 다르게 임의의 위치에 있는 원소로 가기 위해서는 그 위치에 도달할 때 까지 첫 번째부터 순차적으로 방문을 해야 합니다.
이건 연결 리스트의 구조 상 어쩔 수 없는건데, 분명 모든 원소들은 메모리 어딘가에 있을테지만, 우리는 그 중에서 첫 번째 원소의 주소만 알고 있습니다. 그러면 우리가 네 번째 원소의 값을 확인하고 싶다고 할 때, 우리는 첫 번째 원소에 기록된 주소를 보고 두 번째 원소로 넘어가고, 두 번째 원소에 기록된 주소를 보고 세 번째 원소로 넘어가고, 세 번째 원소에 기록된 주소를 보고 네 번째 원소로 넘어가서 드디어 도착했습니다.
그렇기 때문에 k번째 원소를 보기 위해서는 O(k)의 시간이 필요하고, 전체에 N개의 원소가 있다고 하면 평균적으로 N/2의 시간이 걸릴테니 O(N)이라고 생각하면 됩니다.
정리를 해보면 임의의 위치에 있는 원소를 확인하거나 변경하는건 O(N)이고, 해당 위치의 주소를 같이 넘겨줄 때 임의의 위치에 원소를 추가하거나 임의 위치의 원소를 제거하는건 O(1)입니다.
그러니까 임의의 위치에서 원소를 추가하거나 임의 위치의 원소를 제거하는 연산을 많이 해야 할 경우에는 연결 리스트의 사용을 고려해보면 좋습니다.
원래 연결 리스트의 정석적인 구현은 지금 보시는 것 처럼 NODE 구조체나 클래스를 만들어서 원소가 생성될 때 동적할당을 하는 방식입니다. 이 방식은 학부에서 자료구조 수업을 들으신 분이라면 분명 보셨을 구현이고, 또 면접에서 손코딩을 시킨다거나 하는 식으로 질문을 할 수가 있기 때문에 개인적으로 공부를 하셔야합니다.
그런데 이 구현은 긴박한 코딩테스트에서 쓰기는 별로 좋지가 않습니다. 코딩테스트에서는 그냥 STL list를 활용하면 됩니다. STL list가 Doubly Linked List 구조를 가지고 있기 때문에 연결 리스트가 필요하면 그냥 가져다 쓰면 됩니다. 그런데 코딩테스트에서 STL을 허용하지 않는다면 직접 연결 리스트를 구현해야 합니다.