단순 연결 리스트

단순 연결 리스트

- 노드들이 하나의 링크 필드를 가짐

- 이 하나의 링크 필드를 이용하여 모든 노드들이 연결

- 마지막 노드의 링크 필드 값은 NULL

---

노드의 정의: 자기 참조 구조체

- 자기 참조 구조체는 자기 자신을 참조하는 포인터를 포함하는 구조체

- element 타입의 데이터를 저장하는 data 필드

- 포인터를 저장하는 link 필드

- link 필드는 ListNode를 가리키는 포인터로 정의

typedef int element;
typedef struct {	//노드 타입을 구조체로 정의
	element data;
	struct ListNode* link;
}ListNode;

- 노드의 구조는 정의하였지만 아직 노드는 생성되지 않음

- 구조체 ListNode는 노드를 만들기 위한 설계도에 해당

- ListNode로 실제 구조체를 생성하려면 구조체 변수를 선언해야 함

---

공백 리스트의 생성

- 헤드 포인터만 있으면 단순 연결 리스트의 모든 노드를 찾을 수 있음

ListNode* head = NULL;

- 헤드 포인터 head를 정의하면 하나의 단순 연결 리스트가 만들어졌다고 간주

- 현재는 노드가 없으므로 head의 값은 NULL

- 어떤 리스트가 공백인지를 검사하려면 헤드 포인터가 NULL인지 검사하면 됨

---

노드의 생성

- 필요할 때마다 동적 메모리 할당을 이용해 노드를 동적으로 생성

head = (ListNode*)malloc(sizeof(ListNode));

- malloc() 함수를 이용하여 노드 크기만큼의 동적 메모리를 할당

- 이 동적 메모리가 하나의 노드가 됨

head->data = 10;
head->link = NULL;

- 새로 만들어진 노드에 데이터를 저장하고 링크 필드를 NULL로 설정

---

노드의 연결

ListNode* p;
p = (ListNode*)malloc(sizeof(ListNode));
p->data = 20;
p->link = NULL;

- 두 번째 노드 p를 동적으로 생성

head->link = p;

- head->link에 p를 저장하면 head 노드의 링크가 p노드를 가리키게 되므로 아래와 같은 연결 리스트가 됨

- 노드를 더 생성하여 연결하려면 위와 같은 과정을 반복