(2020.12.19)
참고도서
https://book.naver.com/bookdb/book_detail.nhn?bid=10896666
C로 배우는 쉬운 자료구조
단계별 그림과 삽화로 이론을 다지고 C 언어로 구현해 보는 자료구조 입문서 자료를 구조화하는 다양한 방법을 단계별 그림과 삽화를 곁들여 쉽게 설명하고, 자료구조의 핵심 알고리즘을 C 프로
book.naver.com
연결 자료구조
▶ 연결 자료구조의 개념
각 원소에 저장되어 있는 다음 원소의 주소(링크)에 의해 순서가 연결되는 구현 방식
--> 작은 공간을 여러 개 연결하여 전체를 표현
--> 크기를 유연하게 변경 가능 & 메모리를 좀 더 효율적으로 사용 가능
▶ 연결 자료구조의 메모리 저장 방식
노드 단위로 메모리가 할당되며, 저장 위치의 순서와 상관없이 노드의 링크 필드에 다음 자료의 주소를 저장한다.
▶ 연결 자료구조의 연산 특징
삽입 삭제 연산 후 논리적인 순서가 변경되어도 링크 정보만 변경되고 물리적 위치는 변경되지 않는다.
▶ 연결 자료구조의 프로그램 기법
포인터를 이용한 구현
단순 연결 리스트
▶ 단순 연결 리스트의 개념
노드의 링크 필드가 하나이고, 그 링크 필드는 다음 노드와 연결되는 구조
리스트 week의 노드를 다음과 같이 구조체로 정의할 수 있다.
struct Node로 정의한 노드 자료형의 링크 필드는
같은 구조의 다음 노드를 가리키는 포인터여야하므로
자료형이 struct Node*가 된다.
▶ 단순 연결 리스트에서의 삽입 연산
| 1. 삽입할 노드를 준비한다. 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드의 링크값을 지정한다. 4. 리스트의 앞 노드에 새 노드를 연결한다. |
1. 삽입할 노드 준비
삽입할 새 노드를 만들고, 포인터 변수 new가 새 노드를 가리키게 한다.
2. 새 노드의 데이터 필드값 저장
new 노드의 데이터 필드에 '수요일'을 저장한다.
3. 새 노드의 링크 필드값 지정
new 노드를 삽입할 자리에서 앞 노드의 링크필드값을 new 노드의 링크 필드에 저장한다.
new 노드는 토요일 노드로 연결된다.
4. 리스트의 앞 노드에 새 노드 연결
삽입 자리의 앞 노드의 링크 필드에 new 노드의 값을 저장한다.
월요일 노드는 new 노드로 연결된다.
▶ 단순 연결 리스트에서의 삭제 연산
| 1. 삭제할 노드의 앞 노드를 찾는다. 2. 앞 노드에 삭제할 노드의 링크 필드 값을 저장한다. 3. 삭제한 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다. |
1. 앞 노드를 찾는다.
삭제할 노드의 앞 노드(선행자)를 찾는다.
2. 앞 노드에 삭제할 노드의 링크 필드값 저장
삭제할 노드의 앞 노드의 링크 필드에 삭제할 노드의 링크 필드값을 저장한다.
3. 삭제한 노드의 앞뒤 노드 연결
삭제한 노드 앞의 노드를 삭제한 노드 다음 노드에 연결한다.
원형 연결 리스트
▶ 원형 연결 리스트의 개념
단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 해서 리스트 구조를 원형으로 만든 것
이중 연결 리스트
▶ 이중 연결 리스트의 개념
원형 연결 리스트를 보완하여 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
이중 연결 리스트의 노드는 링크 필드 2개와 데이터 필드 1개로 구성된다.
llink필드는 왼쪽노드와 연결하는 포인터이고, rlink필드는 오른쪽 노드와 연결하는 포인터이다.
이중 연결 리스트에서 첫번째 노드와 마지막 노드가 아닌 임의의 노드 p는
p = p.llink.rlink = p.rlink.llink위의 관계가 성립된다.
이중 원형 연결 리스트
이중 연결 리스트를 원형으로 구성하면
블로그에 포스팅 했던 자료구조는 다 옮겼다!! 종강했으니까 일주일에 두 번 올리기로 했는데... 벌써 목요일이다... 주말에 해야지...
'Computer Science > 자료구조' 카테고리의 다른 글
| [자료구조] DFS 깊이 우선 탐색 (3) | 2021.07.19 |
|---|---|
| [자료구조] 그래프 (0) | 2021.07.19 |
| [자료구조] 순차자료구조와 선형리스트 (0) | 2020.12.31 |
