[번역] thank u, next: 연결 리스트(linked list)알아보기

본 아티클은 thank u, next: an introduction to linked lists 의 번역글 입니다

이번 포스트에서는 아리아나 그란데의 “thank u, next” 의 가사를 빌려서 연결 리스트(linked list) 데이터 구조에 대해 알아보도록 하겠습니다. 아직 이 곡의 뮤직비디오를 본 적이 없으시다면, 저희가 본격적으로 시작하기 전에 잠깐 멈추고 감상해 보세요.

연결 리스트란 데이터(data)와 포인터(pointer)로 구성된 노드(node)들이 한 줄로 연결된 데이터의 모음입니다. 저희는 데이터와 다음 노드를 가리키는 포인터로 구성된 노드를 가지는 단일 연결 리스트(singly linked list)에 집중하도록 하겠습니다. 연결 리스트는 이중 연결 리스트(doubly) 또는 원형 연결 리스트(circular)와 같은 다른 종류의 것들이 있지만, 지금은 단일 연결 리스트에만 집중해보도록 하겠습니다.

몇 가지 정의들을 빠르게 훑고 지나갈께요. 저희가 이해하고 있는게 맞나 확인해 보죠.

  • 포인터는 메모리 내에서 특정 값의 주소를 저장하고 있다. 포인터는 아무것도 가르키지 않을 수 있다. 레퍼런스(reference)는 포인터와 비슷하지만, 반드시 무언가를 가르켜야 한다.
  • 데이터 구조(data structure)란 어떤 프로그래밍 언어에서도 구현할 수 있는 데이터의 집합이다.

본 포스트에서는 다음의 연결 리스트 예제를 활용하도록 하겠습니다:

위의 도표에 따르면, 총 5개의 노드가 존재하는것을 확인할 수 있습니다. 그리고 각 노드는 데이터 값을 가지고 있죠. 첫번째 4개의 노드는 아리아나 그란데의 전 남친들을 순서대로 나타내고 있습니다.

Thought I’d end up with Sean / 난 내가 Sean이랑 평생갈 줄 알았어
But he wasn’t a match / 그런데 내 짝이 아니더라
Wrote some songs about Ricky / Ricky에 대해서 노래를 몇 곡 썼었는데
Now I listen and laugh / 지금 다시 들으니 웃기기만 하더라
Even almost got married / 거의 결혼할 뻔 했지 뭐야
And for Pete, I’m so thankful / 그리고 Pete한테는 너무 고마워
Wish I could say, “Thank you” to Malcolm / Malcolm에게도 “고마워"라고 말할 수 있으면 좋을 텐데
’Cause he was an angel / 왜냐면 완전 천사였거든

그리고 마지막 노드(Ari 노드)는 아리아나 그란데를 의미합니다.

Plus, I met someone else / 아, 그리고 나 다른 사람 만났어
We havin’ better discussions / 더 좋은 얘기들을 나누고 있어
I know they say I move on too fast / 사람들은 내가 너무 빨리 갈아탄다고 하지만
But this one gon’ last / 이번에는 마지막이야
’Cause her name is Ari / 왜냐면 그 애의 이름은 Ari거든
And I’m so good with that (so good with that) / 아 지금 너무 만족해 (너무 만족해)

데이터 뿐만 아니라 각 노드들은 다음 노드에 대한 포인터를 가지고 있습니다. 노래에서는 언제나 순서대로 전남친에 대해 이야기 하고, 그리고 마지막에 그녀 자신에 대해 노래하고 있죠. 저희가 위의 연결 리스트를 반복하게 되면 노래와 마찬가지로 같은 순서가 적용될 것입니다. 연결 리스트의 맨 첫번째 노드인 머리 노드(head node)에서 시작하여 그 다음 노드들로 이어지게 됩니다. 단일 연결 리스트는, 순서를 역행하거나 무작위로 노드가 연결되지 않습니다. 대신 머리에서 시작하여 마지막 노드까지, 언제나 같은 순서로 연결되죠.

다음과 같이 노드와 연결 노드들을 만들어 초간단 연결 리스트를 만들 수 있습니다:

본 포스트에서 활용한 코드의 파이썬 버전은 여기에서 확인하실 수 있습니다.

이 코드에서 Sean 노드를 출력해보면, 해당 노드는 data 속성에 이름을 가지고 있을 뿐 아니라 Ricky 라는 다음 노드에 대한 참조값을 가지고 있는 것을 알 수 있습니다. 여기서 next 속성을 활용하여 모든 노드들을 훑고 지나갈 수 있어요!

또, 연결 리스트의 맨 끝에는 널 포인터(null pointer)가 있네요. 여기서 Ari는 여왕이기 때문에 스스로에게 만족하고 더 이상 다른 좋은 사람을 만날 필요가 없습니다. 그래서 다음 노드는 노땡큐(no thank u, next).

연결 리스트는 배열(array)과 비교했을 때 여러가지 장점이 존재합니다. 배열은 선형 데이터 구조(linear data structure) 세계에서 연결 리스트의 주요 대안 중의 하나이죠. 배열은 전통적으로 메모리에서 연속적인 블록에 저장되는데, 이를 통해 빠른 인덱스 공식인 배열_시작점_메모리 + 배열의_각_항목에_할당된_공간 * 우리가_원하는_항목의_인덱스 를 사용할 수 있게 되죠. 배열은 특정 인덱스의 항목을 가져올 때에는 굉장히 효율적( O(1) )이지만, 여러 항목들을 추가하거나 삭제할 때에는 비효율적입니다. 왜냐하면 메모리 내에서 모든 것을 다른 블록으로 옮겨야 하기 때문이죠. 그리고 새 항목을 추가할 배열의 앞이나 뒤에 공간이 있는지 보장 할 수도 없습니다. 배열의 중간에 추가하고자 할 때에도 같은 로직이 적용되는데, 주변의 항목들을 옮겨야 새 공간을 만들거나 공백을 메울 수 있죠.

배열과 달리, 연결 리스트는 메모리에서 연속적인 블록에 저장할 필요가 없기 때문에 연결 리스트의 맨 앞에 추가하거나 삭제하는 것이 더 편리합니다. 또, 포인터는 메모리에서 어떤 위치든지 가르킬 수 있기 때문에, 새 노드를 추가하기 위해 모든 데이터를 옮길 필요가 없죠.

그 말인즉슨, 연결 리스트에 대해 검색을 하거나, 중간에 항목을 추가하거나 삭제할 때에는 이 과정이 비효율적입니다. 왜냐하면 머리부터 작업을 수행하고자 하는 노드까지 전부 훑어야 하기 때문이죠.

연결 리스트의 또 다른 단점 중의 하나는 배열보다 조금 더 많은 메모리를 차지한다는 것입니다. 왜냐하면 단지 데이터만을 포함하고 있는 배열과 달리, 데이터 뿐만아니라 다음 노드에 대한 포인터를 가지고 있기 때문이죠.

이런 작업들 중 일부를 구현한 코드를 살펴 보겠습니다. 연결 리스트의 맨 앞에 항목을 추가하고, 특정 인덱스의 항목을 삭제하는 작업에는 어떤 과정들을 거쳐야 하는지 나타내고 있습니다:

다음은 도표는 저희의 연결 리스트에서 Ari가 빌어먹을 Ricky에게 좀 덜 고맙다고 느꼈을 때 Ricky를 없애는 모습을 나타내고 있습니다.

붉은 색으로 표시된 노드가 삭제 되죠.

또 다른 유용한 메소드로는 searchiterate 가 있네요:

그래서 저희는 연결 리스트에 아리아나 그란데의 전 남친들을 저장하는 것이 해당 데이터 구조의 좋은 활용처라는 것을 알게 되었습니다. 이제 저희가 “thank u, next”를 따라 부를 때 마다 전 남친들의 순서를 항상 같은 순서로 나열하기 때문이죠. 그렇다면 연결 리스트를 활용할 만한 또 다른 좋은 예제가 있을까요? 또 다른 예제로는 작업 큐(task queue)가 있을 겁니다. 예를 들어, 프린터의 경우에는 한 번에 한 장 밖에 인쇄하지 못하지만, 저희는 인쇄 할 때 마다 인쇄버튼을 누르는 것 대신, 작업들을 한번에 쌓아두고 싶을테죠! 저희가 작업 리스트를 만들 때에는, 새로운 항목은 언제나 큐(queue)의 맨 끝에 추가하고 인쇄할 때에는 맨 앞의 항목부터 인쇄할 겁니다! 뒤로가기 버튼도 마찬가지죠! 아니면 되돌리기(undo) 단축키도요! 그래서 스택(stack)이나 큐(queue)와 같은 자료구조를 연결 리스트를 활용하여 구현할 수 있습니다. 저는 여러가지 코딩 문제를 풀 때 연결 리스트가 큰 도움이 되었거든요.

이 포스트가 여러분에게 끈기나 고통대신 사랑을 전해드릴 수 있었으면 좋겠네요.