[자료 구조] 여기 까지 구현해본 단일 연결 리스트의 장점과 단점에 대한 생각

단일 연결 리스트를 구현해보면서 느낀 장점과 단점

배열과 비교했을 때는 이런게 장점인 것 같다.

일단 본인이 판단하기로 단일 연결 리스트의 장점은 배열과 달리 연속적인 메모리 공간 할당을 필요로 하지 않기 때문에, 메모리 관리 측면에서 매우 효율적이라는 생각이 들었다.

 

또한, 노드의 추가 및 삭제, 검색, 조회 등에 있어서도 일반적인 배열에 비해서, 참조관계를 바탕으로 노드를 순회하며 찾아가면 되기 때문에, 비번한 삽입 및 삭제가 반복되는 상황에서는 배열 보다 더 활용하기 좋아보였다.

 

자바스크립트에서 기본적으로 사용되는 arr =[ ]  의 경우에는 배열의 앞 부분에 요소를 추가하게 되면, 각 요소들이 메모리 공간을 연속적으로 할당받아 사용하므로 기존의 요소들이 새요소로 인해서 한 자리씩 뒤로 밀리게 되는 문제가 발생한다. 이는 결국 일반적인 배열에서 시간복잡도나 공간복잡도가 선형적으로 증가할 수 밖에 없는 원인이 된다.

 

반면에, 단일 연결 리스트의 경우에는 횡단으로 밖에 이동하지 못한다는 단점이 있긴하지만, 새로운 노드를 추가하거나 삭제할 때도 각 노드는 모두 메모리 공간 상에 독립된 영역을 차지하고 있기 때문에, 아무리 빈번한 삽입과 삭제가 이루어지더라도 다른 노드에는 아무런 영향을 미치지 않는다.

 

그럼에도 순회가 효율적으로 가능한 이유는 .next 로 나타내는 다음 노드에 대한 참조를 가지고 있기 때문에, 아무리 멀리떨어져 있다고 하더라도 참조관계를 따라서 리스트를 순회하면 되기 때문에, 상당히 메모리 관리 면에서 매우 효율적으로 보였다.

 

그럼에도 이것은 단점이다.

단일 연결 리스트를 구현해보면서 절실하게 느낀 단점은 무조건 모든 노드를 순회해야한다는 점인 것 같다. 특히 횡단으로만 이동이 가능하기 때문에, 내가 목표로 하는 노드를 안다고 해도 일반적인 배열처럼 인덱스를 사용하여 즉시 접근할 수가 없기 때문에, 리스트의 구성이 길고 복잡한 경우에는 검색, 삭제 등에 있어서 접근하는 것이 그리 편해보이지는 않았다.

 

그 외에도 더 있을 것 같긴한데, 현재 까지는 이 부분이 제일 큰 단점인 것 같다.

 

한 가지 더 있다면, 직접 구현해야 하는 문제로 배열보다는 사용하기가 까다롭다는 점인 것 같다.