Ch4 연결 자료구조와 연결 리스트
학습목표
- 연결 자료구조를 이해한다.
- 순차 자료구조와 연결 자료구조의 차이점과 장단점을 알아본다.
- 연결 리스트의 종류와 특징을 알아본다.
- 연결 자료구조를 이용한 다항식의 덧셈 연산 방법을 알아본다.
내용
- 연결 자료구조와 연결 리스트의 이해
- 단순 연결 리스트
- 원형 연결 리스트
- 이중 연결 리스트
- 연결 리스트의 응용 및 구현
수천 페이지가 넘는 문서를 순서대로 묶어서 정리하는 것이 가능할까? 몇 백개의 자료 중 특정 자료를 고를 때 혹은 삭제할 때 순서대로 하는 것이 과연 효율적일까?
정답은 아니다.
양이 많다면 고정해서 순서대로 찾는 것이 아닌 웹 페이지처럼 하이퍼링크를 클릭하여 확장하는 구조를 쓰는 편이 효율적이다. 이렇게 링크를 통해 확장 가능한 문서를 하이퍼 문서라고 한다. 연결 자료구조는 링크를 통해 확장 가능한 하이퍼 구조의 자료구조 방법이다.
순차 자료구조란 ? 논리적인 순서 = 물리적인 순서
순차 자료구조의 문제점
- 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가 작업과 시간 소요된다.
- 원소들의 이동 작업으로 인한 오버헤드로 원소의 개수가 많고 삽입・삭제 연산이 많이 발생하는 경우에 성능 상의 문제 발생한다.
- 순차 자료구조는 배열을 이용해 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가진다.
- 순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방법 필요하다.
→ 연결 자료구조
연결 자료구조란 ? 논리적인 순서와 물리적인 순서가 불일치
- 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식
- 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음
- 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현
- 크기 변경이 유연하고 더 효율적으로 메모리를 사용
연결 리스트 ?
▶ 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
- 리스트의 연결 자료구조로 표현
- 연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트
연결 리스트의 노드
: 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조
<원소, 주소> 단위로 구성되며, 이를 노드라고 한다. 노드는 원소값을 저장하는 데이터 필드와 다음 노드의 주소를 저장하는 링크 필드로 구성된다.
데이터 필드
- 원소의 값을 저장
- 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성
링크 필드
- 다음 노드의 주소를 저장
- 포인터 변수를 사용하여 주소값을 저장
| 구분 | 순차 자료구조 | 연결 자료구조 |
| 메모리 저장 방식 | 필요한 전체 메모리 크기를 계산하여 할당하고, 할당된 메모리의 시작 위치부터 빈자리 없이 자료를 순서대로 연속하여 저장 | 노드 단위로 메모리가 할당되며, 저장 위치의 순서와 상관없이 노드의 링크 필드에 다음 자료의 주소를 저장한다. |
| 연산 특징 | 삽입 및 삭제 연산 후에도 빈자리 없이 자료가 순서대로 연속 저장되어, 변경된 논리적인 순서와 저장된 물리적인 순서가 일치 | 삽입 및 삭제 연산 후 논리적인 순서가 변경되어도 링크 정보만 변경되고 물리적 위치는 변경되지 않음 |
| 프로그램 기법 | 배열 이용 | 포인터 이용 |