니들이 병맛을 알아?

시험과목

비 시험과목&과제물

연결 리스트를 처음 배운 사람들은 다음에 실무를 할 때 한번씩 꼭 써보고 싶다는 생각이 들 정도로 매력적이기도 하다. 그러나 사실 현대의 컴퓨터 환경에서 연결 리스트의 실용성은 거의 빵점에 가까울 정도로 형편없다. 연결 리스트의 주요 단점들을 간략하게 정리해 보면 다음과 같다.

① 읽기 속도가 형편없이 느리다. 노드간의 관계가 링크로만 저장되기 때문에 중간의 한 노드를 찾으려면 순회해 보는 것만이 유일한 방법이다. 10만개의 노드 중 78000번째 노드를 읽어야 한다면 정말 끔찍할 것이다. 링크에 의해 삽입, 삭제는 빨라졌지만 대신 검색 속도가 느려진 것이다. 자료를 다루는 동작의 90%는 읽기이며 삽입, 삭제는 상대적으로 흔한 동작이 아니므로 읽는 동작이 느리다는 것은 치명적인 단점이다.

② 메모리 효율이 아주 좋지 못하다. 데이터 외에 링크를 별도로 가져야 하므로 링크분만큼의 메모리가 더 소모됨은 물론이고 개별 노드를 동적으로 할당해야 하므로 할당 헤더에 의한 메모리 소모도 만만치 않다. 게다가 삽입, 삭제를 빈번하게 할 경우 메모리 단편화가 심해져 시스템의 전체적인 성능도 떨어진다. 똑같은 자료를 저장하는 배열과 비교한다면 최소한 2배, 많게는 6배 정도의 메모리가 더 필요하다.

③ 코드가 그리 어렵지는 않지만 배열과 비교했을 때 상대적으로 복잡하고 포인터 구문이 많아 개발자가 실수를 할 가능성이 많다. 링크 자체가 포인터인데다가 데이터에 포인터가 포함되어 있으면 a->next->b->data[3].c 따위의 복잡한 구문도 자주 사용된다. 이런 다단계 참조문을 다룰 때는 항상 주의해야 하며 직관적이지도 못해서 읽기 어렵고 유지, 보수 비용도 증가한다. 개발 시간이 더 오래 걸리며 개발 비용도 결국 비싸진다.

④ 자료 구조의 내부적인 모양이 선형(linear)이 아닌 입체적인 모양을 하고 있어 스트림 입출력이 번거롭다. 연결 리스트를 파일로 저장하려면 링크는 빼고 데이터만 저장해야 하며 다시 불러 올때는 일일이 링크를 복원해야 한다. 링크는 메모리상에서만 의미가 있는 값이므로 저장 대상이 될 수 없다. 리스트 전체를 화면으로 출력하거나 네트웍으로 전송할 때도 여러 모로 불편한 점이 많다.

⑤ qsort, bsearch 등의 알고리즘을 구현하는 표준 함수들은 기본적으로 배열에 대해 동작하도록 작성되어 있다. 연결 리스트는 이런 표준 함수의 서비스를 받을 수 없다.

물론 연결 리스트는 삽입과 삭제가 엄청나게 빠르다는 장점도 있다. 그러나 그 뿐이며 이 장점만 제외하면 단점 투성이인 자료 구조라고 할 수 있다. 동적 배열도 밀고 당기는 식으로 삽입, 삭제가 가능하기는 하지만 연결 리스트보다는 느렸다. 그러나 이런 사정이 컴퓨터가 빨라지면서 달라지기 시작해 현대의 컴퓨터 환경에서 수천~수만 건의 자료는 배열로 밀고 당겨도 속도 감소를 체감하지 못할 정도이며 수백건인 경우는 오히려 배열이 더 빠르다. 메모리 이동 함수인 memmove는 CPU가 하드웨어적으로 처리하기 때문에 상상을 불허할 정도로 고속으로 동작한다.

연결 리스트의 빠른 삽입 속도가 배열을 압도할 정도가 되려면 자료가 수십만 건 정도 되어야 하며 백만건 정도 된다면 배열보다 연결 리스트가 확실히 나은 성능을 보여줄 것이다. 그러나 이 정도의 자료라면 당연히 트리 구조를 쓰는 것이 합리적이다. 결국 연결 리스트는 중소 규모에서는 배열에게 밀리고 대규모에서는 트리에게 밀려 지금은 설 자리가 마땅치 않은 자료 구조가 된 것이다. 연결 리스트가 월등히 우월한 경우라면 PDA나 핸드폰 등 느린 프로세서를 가진 기계에서 삽입, 삭제가 아주 빈번하고 자료의 양이 많을 때 정도에 국한된다.

연결