앞서 말했었지만 처음 배운(과제로 나온) 자료구조들은 정말 기초적이고 간단한 형태의 자료구조들이었다. 한마디로 앞으로 구현해볼 자료구조들은 구현하기 매우 간단한 편에 속하니 부담없이 따라오다보면 구현할 수 있을 것이다.
연결 리스트(Linked List)란?
우리가 해야 할 일을 쭉 적어 ToDo 리스트를 만들고, 장을 볼 때 사야 하는 물건을 쭉 적어서 쇼핑리스트를 만들어 사용하듯이 연결 리스트란, 데이터들을 쭉 나열하듯이 저장하는 자료구조를 말한다. 언뜻 보면 그럼 그냥 배열에 저장하는 것과 무엇이 다르냐고 물어볼 수 있다. 배열은 한번 선언하고 만들면 배열의 크기가 변하지 않는다.
프로그램을 만들면서 100개의 데이터가 들어올 것이라고 예상하여 100개의 배열을 만들었다고 하자. 하지만 200개의 데이터가 들어왔다면 어떻게 대응해야 할까? 여러 가지 방법이 있을 수 있겠지만 간단하게 생각하면, 200개짜리 배열을 B를 동적으로 만들고 100개짜리 배열 A의 데이터를 배열 B로 복사하는 방법이 있을 것 같다. 좀 더 큰 배열을 동적으로 크게 만들고 데이터를 복사해야 하므로 그렇게 성능이 좋거나 효율적이지 못할 것 같다.
다시 말하면, 데이터가 얼마만큼 저장되어야 하는지 한정되지 않은 상황에서 단순한 배열을 사용하여 저장하면 효율적이지 못하다. 이런 문제를 해결하고 싶어서 나온 자료구조가 바로 연결 리스트이다. 연결리스트는 간단한 동작을 하고 있다. 어떤 방식으로 동작하는지 알아보고, 그중에서도 가장 간단한 단일 연결 리스트 (Singly Linked List)를 구현해보도록 하자.
연결리스트의 동작
노드(Node)란 보통 자료를 저장하고 있는 상자 같은 녀석을 말하는데, 연결리스트에서는 이 노드들을 한 줄로 쭉 연결하면 된다. 그렇기 위해선 어떤 방법이 적절할까? 초중고등학교 때 "비상 연락망"이라는 것을 작성해본 적이 있을 거다. 보통 자신의 다음 출석번호의 친구 전화번호를 기억하고 있어야 하는데, 연결 리스트에서 이 방법을 이용한다.
LinkedList(1) 그림을 보면 Node는 Data(데이터)와 Tail(꼬리)로 구성되어있고 Node의 머리 부분을 Head(헤드)라고 하고 있다. Tail은 다음 Node의 Head 부분을 가리키고 있고 (다음 노드가 어디에 있는지 알고 있다는 의미, 포인터를 사용하여 만들 수 있다) 종점 Node는 Tail이 Null을 가리키고 있다. 만약 여기서 데이터를 추가하는 동작이 이루어진다고 하자.
LinkedList(2) 그림을 보면 Node 3을 생성하고, Node 2의 Tail에 Null 대신 Node 3의 Head를 연결하게 된다. 비교적 간단한 동작이고 이런 식으로 동작하게 되면데이터가 100개면 100개 200개면 200개의 노드를 만들어 연결만 하면 된다.
소스코드
원래는 소스코드 구현부를 하나 하나 설명하면서 넘어가려 했지만 Linked List나 다음 포스팅에서 다룰 Stack과 Queue는 정말 간단하게 동작하기 때문에 직접 소스코드를 분석해보면 좋겠다.