순차 자료구조
구현할 자료들을 논리적 순서로 메모리에 연속 저장하는 구현 방식
논리적 순서 == 물리적 순서
순차 자료구조의 구현 방식을 제공하는 프로그램 기법 = 배열
리스트 :자료를 나열한 것
선형 리스트
선형 리스트의 ...
| 표현 | 순서 리스트 이용 (자료 간 순서 가짐) |
| 저장 | 원소를 논리적인 순서대로 메모리에 연속하여 저장 |
| 원소 삽입 | step1. 삽입할 빈자리 만들기 : 삽입할 자리 이후의 원소들을 한 자리씩 뒤로 자리 이동 -> 물리적 순서 == 논리적 순서 step2. 준비한 빈 자리에 원소 삽입 |
| 원소 삭제 | step1. 삭제 step2. 한 자리씩 앞으로 이동 -> 물리적 순서 == 논리적 순서로 만듦 |
| 문제점 | 1. 연산시간 문제 삽입 or 삭제 연산 후 연속적 물리 주소를 유지해야함 -> 원소 이동 작업으로 인한 성능상 문제 발생 가능 2. 저장공간 문제 배열을 이용해 구현하기 때문에 메모리 사용 비효율성 존재 |
연결 자료구조
순차 자료구조의 연산시간 관련 issue 와 저장공간 관련 issue 를 개선하기 위한 자료구조
자료의 논리적 순서 != 물리적 순서
- 각 원소에 저장되어있는 다음 원소의 주소에 의해 순서가 연결
- 물리적 순서를 맞추기 위한 오버헤드가 발생하지 않음
연결 리스트
리스트의 연결 자료구조로 표현
연결 리스트의 구성
| 노드 | 연결 자료구조에서 하나의 원소를 표현하기 위한 단위구조 <원소(data), 주소(link)> |
| 데이터 필드 | 원소의 값을 저장 저장할 원소의 형태에 따라 하나 이상의 필드로 구성 |
| 링크 필드 | 다음 노드의 주소를 저장 포인터 변수를 사용하여 주소값 저장 삽입, 삭제 연산시 논리적 순서가 바뀌므로 링크 필드 바뀜 |
연결 방식에 따라
1) 원형 연결 리스트
단순 연결 리스트에서 마지막 노드가 리스트의 첫번째 노드를 가리키는 리스트
단순 연결 리스트의 마지막 노드의 링크 필드에 첫번째 노드의 주소를 저장
링크를 따라 순회하면 이전 노드에 접근 가능
2) 이중 연결 리스트
양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
llink : 왼쪽 노드와 연결하는 포인터
rlink : 오른쪽 노드와 연결하는 포인터
3) 이중 원형 연결 리스트
이중 연결 리스트를 원형으로 구성