연결 리스트라는 자료 구조의 실용성에 대해 고찰해 보자.
연결 리스트는 포인터를 사용하기는 하지만 그리 복잡하지는 않고 관리 함수들도 상식 수준에서 어렵지 않게 이해할 수 있다. 내부 구조가 직관적이며 링크를 조작하는 기법도 나름대로 재미 있어서 자료 구조를 처음 접하는 사람에게는 상당히 흥미로운 주제이다.
또한 자료 구조의 가장 기본적이고도 고전적인 주제로서 학술적인 가치도 높다. 연결 리스트를 처음 배운 사람들은 다음에 실무를 할 때 한번씩 꼭 써보고 싶다는 생각이 들 정도로 매력적이기도 하다.
그러나 사실 현대의 컴퓨터 환경에서 연결 리스트의 실용성은 거의 빵점에 가까울 정도로 형편없다. 연결 리스트의 주요 단점들을 간략하게 정리해 보면 다음과 같다.
① 읽기 속도가 형편없이 느리다. 노드간의 관계가 링크로만 저장되기 때문에 중간의 한 노드를 찾으려면 순회해 보는 것만이 유일한 방법이다. 10만개의 노드 중 78000번째 노드를 읽어야 한다면 정말 끔찍할 것이다. 링크에 의해 삽입, 삭제는 빨라졌지만 대신 검색 속도가 느려진 것이다. 자료를 다루는 동작의 90%는 읽기이며 삽입, 삭제는 상대적으로 흔한 동작이 아니므로 읽는 동작이 느리다는 것은 치명적인 단점이다.
② 메모리 효율이 아주 좋지 못하다. 데이터 외에 링크를 별도로 가져야 하므로 링크분만큼의 메모리가 더 소모됨은 물론이고 개별 노드를 동적으로 할당해야 하므로 할당 헤더에 의한 메모리 소모도 만만치 않다. 게다가 삽입, 삭제를 빈번하게 할 경우 메모리 단편화가 심해져 시스템의 전체적인 성능도 떨어진다. 똑같은 자료를 저장하는 배열과 비교한다면 최소한 2배, 많게는 6배 정도의 메모리가 더 필요하다.
③ 코드가 그리 어렵지는 않지만 배열과 비교했을 때 상대적으로 복잡하고 포인터 구문이 많아 개발자가 실수를 할 가능성이 많다. 링크 자체가 포인터인데다가 데이터에 포인터가 포함되어 있으면 a->next->b->data[3].c 따위의 복잡한 구문도 자주 사용된다. 이런 다단계 참조문을 다룰 때는 항상 주의해야 하며 직관적이지도 못해서 읽기 어렵고 유지, 보수 비용도 증가한다. 개발 시간이 더 오래 걸리며 개발 비용도 결국 비싸진다.
④ 자료 구조의 내부적인 모양이 선형(linear)이 아닌 입체적인 모양을 하고 있어 스트림 입출력이 번거롭다. 연결 리스트를 파일로 저장하려면 링크는 빼고 데이터만 저장해야 하며 다시 불러 올때는 일일이 링크를 복원해야 한다. 링크는 메모리상에서만 의미가 있는 값이므로 저장 대상이 될 수 없다. 리스트 전체를 화면으로 출력하거나 네트웍으로 전송할 때도 여러 모로 불편한 점이 많다.
⑤ qsort, bsearch 등의 알고리즘을 구현하는 표준 함수들은 기본적으로 배열에 대해 동작하도록 작성되어 있다. 연결 리스트는 이런 표준 함수의 서비스를 받을 수 없다.
물론 연결 리스트는 삽입과 삭제가 엄청나게 빠르다는 장점도 있다. 그러나 그 뿐이며 이 장점만 제외하면 단점 투성이인 자료 구조라고 할 수 있다. 동적 배열도 밀고 당기는 식으로 삽입, 삭제가 가능하기는 하지만 연결 리스트보다는 느렸다. 그러나 이런 사정이 컴퓨터가 빨라지면서 달라지기 시작해 현대의 컴퓨터 환경에서 수천~수만 건의 자료는 배열로 밀고 당겨도 속도 감소를 체감하지 못할 정도이며 수백건인 경우는 오히려 배열이 더 빠르다. 메모리 이동 함수인 memmove는 CPU가 하드웨어적으로 처리하기 때문에 상상을 불허할 정도로 고속으로 동작한다.
연결 리스트의 빠른 삽입 속도가 배열을 압도할 정도가 되려면 자료가 수십만 건 정도 되어야 하며 백만건 정도 된다면 배열보다 연결 리스트가 확실히 나은 성능을 보여줄 것이다. 그러나 이 정도의 자료라면 당연히 트리 구조를 쓰는 것이 합리적이다. 결국 연결 리스트는 중소 규모에서는 배열에게 밀리고 대규모에서는 트리에게 밀려 지금은 설 자리가 마땅치 않은 자료 구조가 된 것이다. 연결 리스트가 월등히 우월한 경우라면 PDA나 핸드폰 등 느린 프로세서를 가진 기계에서 삽입, 삭제가 아주 빈번하고 자료의 양이 많을 때 정도에 국한된다.
연결 리스트는 동적 메모리 할당과 포인터에 대한 생생한 실습 도구로서 학술적 가치가 높고 또한 상위 자료 구조인 트리에서 노드를 관리하는 기법은 그대로 적용되므로 자료 구조의 한 과목으로서 생략할 수 없는 주제이기도 하다. 분석해 볼만한 예제들 중에 연결 리스트로 작성되어 있는 것들도 많기 때문에 이런 좋은 예제들의 기법을 흡수하기 위해서라도 연결 리스트는 꼭 연구해야 봐야 한다.
실무에서 연결 리스트를 쓸 것인가 동적 배열을 쓸 것인가는 개인의 취향과 문제의 특수성에 따라 결정되어야 할 것이다. 사실 최근의 객체 지향 기법에서는 둘 다 객체로 포장해 버리면 외부에서 보기에는 차이점이 거의 없어 어떤 쪽을 선택하나 결과는 마찬가지라고 할 수 있다. 아뭏든 삽입과 삭제가 필요할 때 쓸 수 있는 자료 구조는 연결 리스트뿐이며 오로지 연결 리스트만이 최선의 해결책이라는 고정관념은 버려야겠다.
