- 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조
● 링크드 리스트
- 리스트 내 각 요소는 노드
typedef struct tagNode
{
int Data; //데이터 필드
struct tagNode* NextNode; //다음 노드를 가리키는 포인터
} Node;
Node MyNode;
C언어로 작성된 프로그램은 세 가지 종류의 메모리 영역을 가짐
- 정적 메모리 : 전역 변수나 정적 변수 등이 저장
프로그램을 실행하면서 프로그램에 사용될 전역 변수 / 정적 변수를 메모리에 할당한 후 프로그램이 종료될 때 해제
- 자동 메모리 : 지역 변수 저장
스택 구조로 구성. { 블록 } 이 종료되면 해제
- 자유 저장소
프로그래머가 직접 메모리를 관리하는 메모리 영역
자유롭게 메모리를 할당해서 사용할 수 있지만 안전하게 해제하는 것도 프로그래머가 책임
* 장점
- 새로운 노드의 추가/삽입/삭제가 쉽고 빠름
* 단점
- 다음 노드를 가리키는 포인터 때문에 각 노드마다 4byte의 메모리가 추가로 필요
- 특정 위치에 있는 노드를 얻는데 드는 비용이 크고 속도가 느림
● 더블 링크드 리스트
- 노드를 찾기위해 양방향으로 탐색 가능
typedef struct tagNode
{
int Data; //데이터 필드
struct tagNode* PrevNode; //이전 노드를 가리키는 포인터
struct tagNode* NextNode; //다음 노드를 가리키는 포인터
} Node;
● 환형 링크드 리스트
- 머리(Head)가 꼬리(Tail)를 물고 있는 형태의 링크드 리스트
- Tail의 다음 노드 포인터가 Head를 가리키게
- Tail에 접근하는 비용이 거의 없는 것이나 다음 없을 정도로 작아져 뒤에서부터 노드를 찾아 나가는 노드 탐색 루틴을 구현할 수도 있음
- Tail은 Head의 '앞 노드'
- Head는 Tail의 '뒷 노드'
출처 : 뇌를 자극하는 알고리즘 (한빛미디어)
댓글