[자료구조] 연결 자료구조

순차 선형 리스트는 논리적인 순서와 물리적인 순서가 같기 때문에 원소의 위

치를 찾아 엑세스 하기 쉽다는 장점이 있지만, 삽입 연산이나 삭제 연산 후에

연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과

시간이 소요된다. 원소들의 이동 작업으로 인한 오버헤드는 원소의 개수가 많

고, 삽입,삭제 연산이 많이 발생하는 경우에 더 많이 발생한다. 또한 순차 자료

구조는 배열을 이용하여 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비

효율성 문제를 그대로 갖는다.

순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선

한 자료 표현 방법으로 연결 자료구조 또는 비순차 자료구조가 있다. 연결 자료

구조에서는 순차 자료구조에서처럼 원소의 논리적인 순서와 물리적인 순서가

일치할 필요가 없다. 연속한 물리주소에 의해 원소의 순서를 표현하는 것이 아

니라 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식

이기 때문에 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다. 하나

의 순차 자료구조를 위해서는 하나의 고정크기 메모리 공간을 사용하지만, 연

결 자료구조에서는 여러개의 작은 공간을 연결하여 전체를 표현하므로 크기 변

경이 유연하고 좀더 효율적으로 메모리를 사용할 수 있다.

연결 리스트는 리스트를 연결 자료구조로 표현한 구조로서 연결하는 방식에 따

라 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리

스트로 나눌수 있다.

연결 자료 구조에서 원소는 연결될 다음 원소에 대한 주소를 저장해야 하기 때

문에 <원소, 주소> 의 단위로 저장해야한다. 이러한 단위 구조를 노드 라고 한

다. 노드는 원소의 값을 저장하는 데이터 필드와 다음 노드의 주소를 저장하는

링크 필드로 구성된다. 데이터 필드는 저장할 원소의 형태에 따라서 하나 이상

의 필드로 구성되기도 한다. 링크 필드는 포인터 변수를 사용하여 주소값을 저

장하며, 포인터 또는 링크, 참조 라고도 한다.

그리고 연결 자료 구조에서는 헤드 라고 불리는 시작 주소가 있다. 그 헤드는

시작 주소이면서, 첫 데이터를 가르키는 역할도 한다. 연결 리스트의 마지막 노

드는 다음에 연결되는 노드가 없으므로 링크 필드에 저장할 주소값이 없는데,

이럴때는 노드의 끝을 표시하기 위해 마지막 노드의 링크 필드에 NULL을 저장

한다. 만약 아무런 노드도 없다면 헤드에 NULL을 저장하여 널 포인터로 만들면
된다.