2026. 11. 20. 14:20ㆍComputer Science/DS(ADT)&AL

Linked List는 오브젝트들로 정렬된 DS라고 할 수 있다. 다만 진짜로 물리적으로(뭐 OS단으로 들어가면 얘기가 좀 달라지긴 하오나) Lineary하게 배열되어 있는 array랑은 다르게, Linked list는 각각의 오브젝트가 다음이나 앞/뒤의 오브젝트에 대한 포인터를 가지고 있다. 이때 포인터가 뒤로만 이어지면 Singly Linked List, 앞/뒤로도 이어지면 doubly linked list라고 하게 된다. 그리고 경우에 따라서는 Circular하게 순환할 수도 있을 것이다.
세부 동작과 구현은 너무 귀찮으니까 넘어가자.
Implementing pointers and objects in doubly linked list
근데 문제는, CPP같이 사용자에게 자유도(직무유기)를 보장하는 언어면 모를까.. 포인터가 존재하지 않는 언어에서 Linked List를 어떻게 구현해야만 할까? 먼저 첫번째로는, 여러개의 배열을 사용해서 객체를 표현해 내는 방법이 있다. 쉽게 말하면 key[x], next[x], prev[x]와 같은 배열들을 만들어서 linked list를 구현하는데 쓰는 것이다.

예를 들어 첫번쨰 element가 있다고 해보자. 그러면 그 elemnt의 인덱스는 x가 된다. 이때 key는 key[1]에 있을 것이며, 다음 노드는 next[1]에 인덱스로서 저장되어 있을 것이다. 참 쉽죠?

근데 배열을 3개 써야하니까 조금 거시기 할 수 있다. (DOTS와 같은 관점에서는 사실 오히려 적절하다고 할 수 있겠지만.) 그래서 배열에 객체를 저장한다고 생각해보자. 예를 들어서 2차원 좌표면 (x, y)를 연달아서 저장할 수 있을것 아닌가? 마찬가지로 한 배열에 (key, next, prev)를 쑤셔 박는 것이다.
다만 컴퓨터 프로그래머는 데이터의 수명에도 관심을 써야하는데, 대부분 포인터가 없는 언어같은 경우에는 Gabage Collector가 참조가 사라진 객체들을 정리하는 편이다. 즉 메모리 관리를 사용자가 직접 안하는데... 위와 같은 자료 구조에 대해서 데이터를 정리하려 하면은 살짝 머리가 아파지지 않겠는가?
예를 들면 중간에 요소를 하나 치우고 싶다고 해보자. CPP같은 언어면 그냥 메모리 할당을 해제해 버리면 끝이지만. GC가 있는 언어에서 요소 자체를 "숙청"하는걸 구현하려면 GC가 눈물을 흘려야 하고.. 또 프로그래머는 저 배열을 다시 재배열 해서 OS에 일부를 뱉어줘야 하고.. 컴퓨터도 아프고.. 나도 아프고....

그래서 전체 DS에서 여유분을 가져다가 Free List라는걸 만들어서, 삭제되었거나 아직 사용하지 않는 노드들을 여기에 쳐박아둔다. 이렇게 하면은 미리 선언된 공간을 가져다가 써서 할당/해제 비용을 낮추는 것은 물론이요 GC 비용도 낮출 수 있다.
물론 저거를 구현하는데 있어서 코드로 작성하면 처음에는 조금 어려울 수는 있는데.. 나중에 가면 쉬워진다. 지울놈의 앞/뒤 노드에 각각 접근한 다음에 그 둘의 next/prev를 수정하고 지울놈은 free list에 쳐박으면 되는것 아닌가? 물론 이것을 실체적으로 한 줄 한 줄 짜는 것은 본래 프로그래머들의 사명이었으나, 이제는 GPT 님께서 다 해주시니 걱정하지 마시라.
'Computer Science > DS(ADT)&AL' 카테고리의 다른 글
| Sorting in Linear Time (0) | 2026.10.27 |
|---|---|
| QuickSort (0) | 2026.10.23 |
| Heapsort (0) | 2026.09.10 |
| R.I.P 백준 (0) | 2026.04.16 |
| 암시적 그래프 구현과 명시적 그래프 구현 (0) | 2026.04.15 |