이번 주 스터디에서 저희 그룹원들은 링크드 리스트(Linked List)에 대해서 공부했습니다.
일단, 배열을 먼저 생각해보면 같은 타입의 연관된 데이터를 연속적으로 저장하여 한 변수에 통합하여 관리하는 자료구조라고 할 수 있습니다.
반면에, 링크드 리스트는 연결 리스트라고 하며, 연속된 위치는 아니고 떨어져있는 곳에 존재하는 데이터를 포인터로 연결하여 관리하는 구조로 되어있습니다.
여기서 배열과 링크드 리스트 구조를 볼 때, 어떤 차이가 있을지 생각해보면, 배열은 연속된 데이터가 저장되어 있기 때문에 추가/삭제 동작이 유연하지 못합니다. 왜냐하면 연속된 데이터 중간에 추가나 삭제 동작이 발생하게 되면, 공간을 만들어 줘야하는 비용이 크기 때문이고, 링크드 리스트는 포인터를 통해 연결되어 있기 때문에 포인터를 새로 생성된 데이터에 연결하거나 포인터 연결을 끊기만 해도 삭제가 이루어 질 수 있기 때문에 추가/삭제 동작에는 링크드 리스트가 더 효율적으로 동작합니다.
하지만, 배열은 어떤 데이터를 탐색할 때는 접근하고자 하는 인덱스만 알고있으면 바로 찾을 수 있기 때문에 링크드 리스트보다 데이터 탐색할 때는 더 효율적이라고 할 수 있습니다.
링크드 리스트가 어떤 데이터를 탐색하고자 할 때는 포인터를 통해 순차적으로 접근해야하기 때문에 탐색 속도 면에서는 불리할 수 있습니다. 마치, 겉으로는 내용물을 알 수 없는 여러 개의 상자들 중에서 자신이 원하는 물건을 찾기 위해, 어떤 물건이 들어있을지 모를 상자를 일일이 찾는 방식으로 동작한다고 할 수 있습니다.
이런 링크드 리스트에 관련된 알고리즘 문제를 그룹원 분들과 함께 풀었는데, 릿코드에서 JAVA를 통해 링크드 리스트를 구현하는 문제를 풀면서 링크드 리스트에 대한 이해도가 한 층 더 올라가는 계기가 되었습니다. 예전에 C나 C++로 구현할 때는 전혀 구현도 못하고 다른 분들이 구현 해놓은 링크드 리스트 또한 이해도 못했던 적이 있었기 때문에 그때보다 이해도가 높아졌다고 볼 수 있습니다.
그 후 백준에서 골드 4 정도 난이도의 알고리즘 문제 풀기를 시도했는데, 다른 그룹원 분들을 해결하셨지만 저는 풀지를 못했습니다. 조금만 더 생각하면 풀 수 있을 것 같았는데, 답답해서 다른 분 것을 참고하여 풀었습니다. 참고해보니 답답했던 마음이 사라지고 '아, 리스트를 이런 식으로 사용하여 간단하게 해결했구나...' 라는 생각이 들면서 한 수 배웠습니다.
문제를 해결 못했을 때는 자신에 대한 실망감과 자신감을 조금 잃을 뻔 했지만 그래도 아직은 더 발전해야 한다는 마음과 발전할 수 있다는 긍정적인 마음이 더 컸습니다. 저에게는 이런 마음가짐을 갖고 있는 것이 중요하다고 생각하고 더 노력하겠습니다.
