연결 리스트에서는 각 데이터 항목들이 기억장소내의 어떤 위치에 어떤 항목이 있는 지를 표시해 주어야 한다. 이를 위해 데이터 항목에는 값뿐만 아니라 다음 항목의 위치 정보도 함께 저장해둔다. 위치정보의 저장에는 포인터가 사용된다.


3. 연결리스트 에서의 포인터

연결 리스트에서 포인터는 각 항목의 다음 순서인 항목이나 앞 순서인 항목의 위치를 가르키는 지시자이다. 연결 리스트의 마지막 노드에는 다음 순서인 항목이 없고, 첫번째 노드에는 이전 순서인 항목이 없으므로 이들 포인터는 null로 해주어야 한다.

포인터는 연결 리스트의 핵심이다. 연결 리스트에서 공통적인 사항은 데이터 항목 간의 결합이 데이터 항목 자체 내에 포함되어 있는 정보에 의해 포인터의 형식으로 정의된다는 것이다. 이런 사실은 데이터 항목 간의 결합이 배열의 배치와 저장을 기반으로 하는 배열과 링크드 리스트를 분명히 구분하는 기준이다.

위의 그림에서 입력자료는 4칸의 분량인데, 저장장치에 연속된 공간은 최고 3칸밖에 없다. 이럴 경우 배열로는 입력자료를 수용하지 못한다. 그러나 연결리스트를 이용하면 연속되지 않은 빈 공간들을 효율적으로 사용할 수 있다. 다음 그림을 보자.

링크를 통해 데이터의 연결성이 보장된다.

배열과 비교하여 또다른 장점도 있다.

항상 정렬 상태가 유지되어야만 할 어떠한 배열이 있다고 하자. 새 값이 중간에 들어가야 할 경우, 배열은 다음의 모든 데이터를 뒤로 한칸씩 밀어야만 한다. 막대한 낭비가 아닐 수 없다. 소규모의 정보를 다룰 때는 사실 별로 문제가 되지 않을 것이다. 하지만 대용량의 정보를 다룰 때는 문제가 매우 심각해진다. 정부에서 국민의 주민등록정보를 배열로 저장했다고 치자. 누군가가 태어나고 죽을 때마다 움직여야 할 배열의 수는 천문학적일 것이다. 하드는 쓸데없는 자료이동에 대부분의 시간을 소모할 것이고, 막상 데이터를 읽으려면 많은 시간을 기다려야 할 것이고 공무원의 흰머리만 늘어날 것이다.따라서 이러한 것은 연결리스트를 이용하는 것이 훨씬 낫다. (그러나 앞으로 배우게 될 더 나은 자료구조들이 실제로는 이 일에 더 적합하다.)

그러나 단점도 있다. 이러한 링크는 실제적으로 다음 번 저장장소의 주소값인데, 그 값을 저장하기 위해 추가로 저장장소가 필요하게 된다. 따라서 본연의 데이터 외에 추가로 Overhead가 발생한다.

4. 연결리스트의 효율 계산

각 노드는 사용자 데이터와 다음 노드를 가리키는 포인터로 이루어진다. 이 때 효율성을 따져 보아야 한다. 예를 들어 어떤 환경에서 이 포인터가 4 바이트를 차지한다면 데이터는 4보다 훨씬 큰 용량이어야 한다. 예를 들어 데이터의 크기가 2 바이트라면 하나의 노드에 필요한 공간은 최소 6 바이트가 될 것이고, 실제 10 바이트를 저장하기 위해서는 10 / 2 = 5 개의 노드가 필요할 것이며, 이는 메모리 공간을 최소 5 * (2 + 4) = 40 바이트를 필요로 한다. 생각해 볼 필요도 없이 10 바이트를 저장하기 위해 40 바이트를 쓴다는 것은 메모리의 낭비일 것이다. 낭비되는 공간을 퍼센트로 나타내면 30 / 40 * 100 = 75(%)가 된다. 따라서 한 노드에 더 많은 데이터를 저장하여 이러한 손실을 상대적으로 줄일 수 있다. 예를 들어 한 노드에 40 바이트 크기의 데이터를 저장한다면 80 바이트를 저장하기 위한 노드의 개수는 80 / 40 = 2가 될 것이고, 필요한 메모리 공간은 최소 2 * (40 + 4) = 88이 된다. 즉 80 바이트를 저장하기 위해 88 바이트가 필요한 셈이므로 낭비되는 공간은 8 / 88 * 100 = 9(%) 정도이다.

그러나 여기에서는 리스트 구현 방법에 중점을 두고 설명할 것이기 때문에 이러한 효율성은 무시할 것이다.