c로 배우는 쉬운 자료구조 5장(연결자료구조)

목차

없음

본문내용

1. 순차 자료구조와 연결 자료구조를 비교 설명하시오.

순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 연결 자료구조는 다음 원소의 주소에 의해 순서가 연결되는 방식이기 때문에 순차 자료구조와 달리 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.
연결 자료구조에서 원소는 연결될 다음 원소에 대한 주소를 저장해야 하기 때문에 <원소, 주소>의 단위구조인 노드를 사용한다.

2. 단순연결리스트와 원형 연결 리스트, 이중 연결 리스트의 특징을 설명하시오.

단순연결리스트

하나의 데이터에 하나의 링크로 일자형으로 연결됩니다. 데이터가 있고 링크가 그 다음 데이터가 있는 위치를 포함하게 됩니다. 맨 끝은 NULL이 있습니다.
단점은 다른 연결 리스트에 비해서 구현이 쉽습니다만 오로지 일자 진행으로만 움직이므로 만일 이전 데이터를 접근 할려면 리스트의 처음 위치에서 다시 돌아야 합니다.
[출처] 단순연결리스트, 원형연결리스트, 이중연결 리스트|작성자 케넌

원형연결리스트

하나의 데이터에 하나의 링크로 돌고 도는 형식으로 이루어져 있습니다. 마지막 부분은 NULL이 아닌 첫 노드를 가리킵니다. 한바퀴 도는거죠. 단순연결리스트에 비해서 바로 한바퀴를 돌아 접근하는 특징이 있지만 단순연결리스트와 별다른 차이는 없습니다.
[출처] 단순연결리스트, 원형연결리스트, 이중연결 리스트|작성자 케넌

이중연결리스트

하나의 데이터에 왼쪽링크(헤드)와 오른쪽링크(테일)가 있습니다. 헤드는 이전 데이터의 위치를, 테일은 다음 데이터의 위치를 가지고 있습니다.
일자형으로 진행되는 다른 연결 리스트와는 달리 이 연결 리스트는 앞뒤로 왔다갔다 하는게 자유롭습니다.
데이터 접근이 용이해집니다. 단점은 윗 연결 리스트보다 복잡하고 연결을 하나씩 더 먹으므로 공간도 그만큼 더 차지합니다.
[출처] 단순연결리스트, 원형연결리스트, 이중연결 리스트|작성자 케넌

3. 다음의 포인터 연산의 의미를 설명하시오.
① p = p.link;
포인터p가 가리키는 노드의 다음노드로 포인터를 이동하라.

참고 자료

없음