자료 구조에 따른 시간 복잡도 비교 - linked list편

오늘은 지난 배열편에 이어

linked list(연결 리스트)라고 불리는 자료구조에 대해서

시간 복잡도와 연관해서 분석해보고,

현실에서 어떤 것과 닮아있는지를 통해서

심화학습 해보도록 하겠습니다 :D 

 

먼저, linked list(연결 리스트)에 대해서 간략하게 정의해보면,

우리가 아는 배열의 특징(메모리가 이미 정해져있음, 인덱스를 통해 자료를 저장 및 관리함)과는 달리!

인덱스가 없고, 본래 정해져있는 크기가 없습니다.

 

즉, 배열과 달리 자료의 크기에 유동성이 있고, 자료는 인덱스를 통해서 관리되지 않고

단일 연결 리스트(singly linked list) 의 경우 이전의 자료에 의해서 다음 자료가 유지가 되는 형태로

자료가 저장 및 관리됩니다.

 

좀 더 구체적으로 이해해보면,

linked list는 먼저, '노드(node)'라는 단위로 구성이 되어있습니다.

이 때, 노드를

이런 모양이라고 생각했을 때,

즉, 뭔가를 담을 수 있는 두칸이 있는 형태의 자료구조라고 했을 때

첫 번 째 칸에는 여기에 넣을 '자료(data)'를 넣고,

두 번 째 칸에는 다음 '노드(Node)'를 가리키는 레퍼런스 값을 넣어줍니다.

 

자료 출처 :  GeeksforGeeks

그러면 이런 식으로 linked list가 완성되게 됩니다.

여기서 화살표는 노드 안의 다음 노드의 위치 값(레퍼런스 값)을 바탕으로

실제로 다음 노드를 가리키는 '포인터'가 됩니다.

그리고 이렇게 한 방향으로 노드가 연결되어 있는 연결 리스트를 단일 연결 리스트라고 합니다(singly linked list)

 

앞서 말했듯이 linked list는 이렇게 추가할 때마다 메모리가 같이 추가되는, 즉,

배열처럼 메모리가 정해져있지 않은 구조로 되어있고,

인덱스로 자료를 관리하지 않고, head 노드(맨 첫 번 째 노드)부터 차례대로 그 다음 노드의

'존재를 보증' 해주는 식으로 자료 구조를 유지합니다.

추상적인 표현이지만, 이전 자료(이전 노드)가 다음 자료(다음 노드)의 위치 값을 가지고 포인터로 가리키고 있지 않다면

그 다음 노드는 아무도 찾아주지 않는 혹은 아무도 그것이 존재하는지 조차 모르게 되기 때문에

이전 노드가 다음 노드의 존재를 보증해준다는 표현을 써봤습니다.

그리고 이런식의 구조라면, 맨앞의 head 노드가 사라진다면, 그 head 노드부터 차례대로 존재를 보증 받았던 

그 다음 노드, 그 다다음 노드들도 존재의 이유를 상실해 모두 사라지게 됩니다.

이 때, head노드가 없어졌다고 하더라도, 

나머지 노드들끼리는 연결되어 있기 때문에 제거되는건 아니지 않는가 라고 생각할 수 도 있지만,

 

나머지 노드들 모두 head 노드를 통해서만 탐색, 조회가 가능하기 때문에

head노드가 사라지면, 더이상 탐색, 조회가 불가능해지고,

그러면 자동적으로 js 혹은 자바에도 있는 garbage collector(가비지 콜렉터 : 자동 메모리 관리 시스템 정도라고 생각하고 넘어가기)가

아무도 알아주지 않는 자료이고, 쓰지 않는다고 판단해 제거해버립니다:D 

 

그렇다면 doubly linked list는 뭘까요??

이번에는 한개의 노드가

이런 식으로 3칸을 가지고 있다고 생각해봅시다.

그리고 가운데 칸에는 자료(data)가 들어가고, 왼쪽, 오른쪽에는 각각

이전 노드의 참조값, 다음 노드의 참조값이 들어갑니다. 

그리고 앞서 말한 단일 연결 리스트가 한 방향으로만 가리키며 유지되는 자료구조인데 반해

이중 연결 리스트는 양방향으로 서로를 키리키며 유지 및 관리되는 자료구조 입니다:D 

 

자, 여기까지 단일 연결 리스트 그리고 이중 연결 리스트의 정의에 대해서 간략하게(?)

살펴봤는데요!

이제 이 연결 리스트에 자료를 추가, 삭제, 조회 ,탐색하는 작업을 바탕으로

시간 복잡도가 어떻게 되는지를 살펴보고자 합니다 :D 

 

먼저, 단일 연결 리스트를 살펴보면, 

 

이러한 시간 복잡도를 가지는데요!

하나하나 설명을 해보면,

 

먼저, 조회(lookup)이 왜 O(n)의 시간 복잡도를 가질까를 생각해보면,

배열에서는 인덱스로 자료를 관리했기 때문에 

'3번째 자료좀 줘봐!' 하면 단번에[O(1)] 자료를 조회할 수 있었습니다.

 

그러나, 연결 리스트에서는 특정 위치의 자료를 조회하기 위해서는

말 그대로 앞에서부터 하나하나 세면서 찾아야합니다.

why? : 애초에 연결 리스트에는 지정된 인덱스가 없기 때문입니다.

사전을 예로 들었을 때, ㄱ,ㄴ,ㄷ,ㄹ,ㅁ,ㅂ,ㅅ.... 를 표시해 뒀기에 저희는

찾고자하는 단어를 '최대한 효율적으로' 찾을 수 있습니다.

그러나, 그런 표시도 없고, 그런 순서로 사전이 구성되어 있지 않다면?

저희는 언제 등장할지 모르는...예를 들어, 뭐 '용기'라는 단어를 

앞에서부터 순차적으로 찾아야 합니다.

 

연결 리스트에서의 조회는 위의 상황과 같습니다.

한 페이지가 다음 페이지(한 노드와 다음 노드)와 연결되어있고(포인터로 다음 노드를 가리키기에)

따라서, n번째 노드를 찾아 그 안의 자료를 조회하려면, O(n)의 시간 복잡도로 작업이 가능해집니다.

 

그렇다면 탐색은(find)?

똑같이 O(n)이 됩니다.

이 역시 앞에서부터 하나하나 노드 속의 data를 살펴보면서 이건가? 이건가? 하면서 찾아나가야 하기 때문에 그러합니다.

 

그럼 삽입과 제거는 다를까요?

먼저, linked list에서의 삽입과 추가는 배열과는 다른 원리로 이루어지는 데요.

모든 노드들이 한 방향으로 다른 노드를 가리키며(포인터) 자료가 이어지기 때문에

만약, 특정 노드 뒤에 노드를 추가하려면,

추가하려는 노드 이전 노드가 가리키는 노드를 새로 추가하는 노드로 바꿔주고,

새로 추가한 노드의 다음 노드를 

추가하려는 노드의 이전 노드가 본래 가리켰던 노드로 대체해주면

추가가 이루어집니다.

여기서 추가(insert)의 시간 복잡도는 O(1)인데, 전제가 있습니다.

자신이 추가하려는 위치의 이전 노드를 알 경우에 O(1)이 됩니다.

그 외에는, 즉, 모르는 경우에는 추가하려는 위치의 이전 노드를 먼저 조회한 뒤에 

작업이 이루어지기 때문에 O(n)이 됩니다.

 

다음으로 제거는 추가와 달리

제거하려는 요소의 위치를 알아도

결국 제거를 할 때는 그 이전 노드를 건드려야하는데,

단일 연결 리스트에서는 이전 노드로 가는 포인터가 없기 때문에

결국 제거하려는 위치를 알아도

O(n)의 시간복잡도로 작업을 수행해야 합니다. 

 

마지막으로 수정, 할당(assign) 또한,

똑같이 인덱스를 통해 자료를 관리하지 않기 때문에

특정 노드를 일단 찾고 자료를 수정해야하기에

O(n)의 시간 복잡도가 됩니다:D 

 

자료 출처 : 코드스테이츠

그렇다면 위와 같이

이중 연결 리스트는 어떨까요 ?

 

이중 연결 리스트는 단일 연결 리스트와 

포인터가 두개인가 한개인가의 차이로 구분되는데,

포인터가 두개면 어떤 장점이 있고, 단점이 있을까를 생각해봅시다 :D 

 

먼저, 

조회를 한다 했을 때는 단일 연결 리스트와 동일한 

시간 복잡도를 갖습니다.

포인터가 두개더라도 

결국 인덱스가 없으니 하나하나 찾아야하는 것은 같으니까요!

이런 원리로 결국, 이중 연결 리스트도 조회, 탐색, 수정(할당)은 모두 O(n) 의 시간 복잡도를 갖습니다(단일 연결 리스트와 동일)

 

또한, 같은 원리로 추가(insert)도 단일 연결 리스트와 같이 O(1)이 되는데[물론 이 경우도, 삽입하고자 하는 위치의 노드를 정확히 하는 경우에만 O(1)이 됩니다]

제거의 경우 차이가 있습니다 

제거의 경우 아까 단일 연결 리스트에서는

제거할 위치의 노드를 알아도 결국

그 이전 노드에 작업을 해줘야하는데, 포인터가 다음 노드만을 가리키기 때문에

그 이전 노드에 설정을 해줄 수 없었는데

이렇게 포인터가 두개인 (양 옆으로) 이중 연결 리스트의 경우에는

제거할 위치의 노드만 안다면, 바로 이전 노드가 가리키는 노드를 바꿔주면 되기에

O(1)의 시간 복잡도를 가진다는 차이를 가집니다 :D 

 

여기까지 각각의 연결 리스트 (두 종류)를 

살펴보면서 시간 복잡도를 확인했는데요.

 

마지막으로 연결 리스트의 사례를 살펴보면,

기차 혹은 기차 놀이를 생각해볼 수 있을 것 같습니다(단일 연결 리스트).

기차에는 head 섹션이 있고, tail 섹션이 있습니다(연결 리스트와 같이)

그리고 각각의 섹션은 다음 섹션을 지탱해주고 있습니다(기차와 기차를 연결하는 장치 = 노드의 포인터)

그리고 만약 맨 앞 섹션의 뒤 섹션과의 연결 장치가 끊어졌다면??..head 섹션이 전체를 끄는 구조로 되어있는

기차의 head 섹션이 아닌 나머지 섹션은 멈추게 되고, 기차를 하나의 연결 리스트라고 봤을 때

더이상 그 리스트에 속하지 않은 것이 될 것입니다(head노드의 포인터를 지우면 일어나는 일과 같음)

 

그럼 여기까지 linked list와 시간복잡도에 대한 이해

그리고 현실 사례를 바탕으로 이해해보는 시간이였습니다 :D