오늘도 돌아온 c언어 공부시간 ㅎㅎ
오늘은 링크드 리스트를 공부해보고자 한다.
먼저 c언어의 Linked List란 순차적으로 연결된 선형 자료구조를 의미한다.
각 저장 단위를 Node라고 하며, 일반적으로 structure를 통해 그 형태를 선언한다.
Node의 구성 요소는 다음과 같다
Data: 각 단위별로 저장할 내용
Link: 다음 Node를 가리키는 포인터
단일 Linked List
단일 연결 리스트는 각 노드가 다음 노드를 가리키는 데이터 구조이다.
배열과 달리 연결 리스트는 요소 추가/삭제가 효율적이지만, 요소 접근은 비효율적이다.
단일 연결 리스트의 구조
- 노드 구조체: 데이터와 다음 노드를 가리키는 포인터로 구성
- 헤드 포인터: 리스트의 첫 번째 노드를 가리킴
이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 가지는 데이터 구조이다. 이를 통해 양방향 탐색이 가능하며, 단일 연결 리스트에 비해 더 유연한 조작이 가능하다.
이중 연결 리스트의 구조
- 노드 구조체: 데이터와 이전 노드, 다음 노드를 가리키는 두 개의 포인터로 구성
- 헤드 포인터: 리스트의 첫 번째 노드를 가리킴
- 테일 포인터: 리스트의 마지막 노드를 가리킴
원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 특별한 형태의 연결 리스트이다. 이를 통해 리스트의 처음과 끝을 구분할 필요가 없어지며, 노드의 삽입과 삭제가 용이해진다.
원형 연결 리스트의 구조
- 노드 구조체: 데이터와 다음 노드를 가리키는 포인터로 구성
- 헤드 포인터: 리스트의 마지막 노드를 가리킴, 이를 통해 리스트의 처음과 끝을 구분할 수 있음
STACK
가장 나중에 넣은 것을 가장 먼저 빼는 구조, 보통 맨 앞의 Node를 추가/삭제함
QUEUE
가장 나중에 넣은 것을 가장 나중에 빼는 구조, 보통 맨 뒤에 Node를 추가, 맨 앞에서 Node를 삭제