알고리즘을 공부하는 사람이 자료구조를 이해하지 못한다는 것은 어불성설이라고 생각합니다. 그만큼 알고리즘을 학습하는 사람에게 자료구조는 기본소양과 같습니다. 하지만 일반적으로 구현되어 있는 라이브러리를 이용하는 경우가 대부분이기 때문에 직접 구현해보라는 요구를 받게 되었을 때, 실제 구현하지 못하는 경우가 상당히 많습니다.
자료구조를 정확히 이해하지 못한다면, 어떤 알고리즘을 풀이할 때 어떤 자료구조를 사용하는 것이 옳은가에 대한 판단도 스스로 내리지 못하고 특정 알고리즘을 풀 때는 이 자료구조를 사용해야한다고 기계적으로 암기해버리는 경우가 많습니다.
이러한 문제가 발생하는 원인은 자료구조의 원리를 제대로 이해하지 못하고 있으며, 어떤 방식으로 구현되어 있는지를 이해하지 못하고 있기 때문입니다. 제대로 자료구조를 이해하고 있다면, 자료구조를 구현하는 것을 두려워하지 않을 것이며, 어떤 방식으로 작동하는가를 정확하게 설명할 수 있을 것입니다. 그리고 어떠한 자료구조를 사용하여 알고리즘을 풀어야한다고 했을 때, 여러 자료구조 중에서 정확히 어떤 자료구조를 사용해야하는지 판단할 수 있을 것입니다.
예를 들어보겠습니다. 가장 일반적으로 실수하는 경우가 잘못된 List를 사용하는 경우입니다. 일반적으로 List라고 한다면, ArrayList가 있을 수 있을 것이고, LinkedList가 있을 수 있을 것입니다. 얼핏 보면 List라는 이름에 현혹되어 비슷한 것이 아닐까 착각할 수 있습니다. 하지만 둘은 연결방식 면에서 결정적인 차이를 갖고 있습니다. ArrayList의 경우 내부적으로는 Array로 되어 있기 때문에, 실제로는 배열과 동일한 방식으로 구성되어 있다고 생각하시면 됩니다. 그렇기 때문에 자료의 추가, 삭제 측면에서 비효율적이지만, 특정 위치의 자료를 찾는데 있어서는 효율적이라고 할 수 있습니다. 그에 반하여 LInkedList는 이름대로 Link되어 있는 List라고 이해하시면 됩니다. LikedList는 List를 이루고 있는 자료들이 개별적인 노드로 구성되어 있고, 각 노드들은 서로의 주소 값을 갖고 있습니다. 즉 주소 값을 이용하여 마치 chain처럼 연결되어 있는 것입니다. 그렇기 때문에 List에서 특정 값을 추가하거나 삭제하려 한다면, 추가하는 노드의 주소를 기존 노드 리스트에 추가해줌으로써 추가해줄 수 있고, 삭제하려면 삭제하려는 노드의 주소를 List의 어느 노드도 저장하지 않게 함으로써 해당 노드를 고립시켜 삭제시킬 수 있습니다. 하지만 특정 위치의 값을 확인하기 위해서는 List의 시작인 헤드부터 해당 인덱스까지 하나씩 확인해야한다는 단점을 갖고 있습니다.
이처럼 두 List는 삽입/삭제, 검색 측면에서 장점과 단점이 갈리기 때문에 필요에 따라 적절하게 사용해야합니다. 앞으로 자료구조를 하나씩 확인해보고 구현해보면서 그 원리와 기능을 파악해보도록 하겠습니다.