4장 - List

배열을 이용한 순서화 리스트: 임의의 위치에 대한 삽입과 삭제 연산이 곤란. 가변 길이의 순서화 리스트 지원 불가.

 

연결 리스트를 이용한 순서화 리스트: 리스트는 노드들로 구성, 각 노드는 데이터와 링크로 구성됨. 링크는 리스트의 다음 노드를 가리킴. (마지막 노드의 링크는 NULL)

 

단일 연결 리스트(Singly Linked Lists)

각 노드들은 메모리의 인접한 곳에 위치하지 않는다.

각 노드의 주소는 프로그램 실행시 매번 다를 수 있다.

 

리스트의 이름 = 첫 번째 노드의 주소가 된다.

 

배열에 비해) 삽입과 삭제시 기존 노드들의 위치를 변경할 필요가 없다

배열에 비해) 링크 필드를 위한 추가적인 메모리 공간이 필요하다

 

연결 리스트의 구현(C)

struct node{
	int data;
	struct node* link;
};

자기참조 구조체를 이용함.(node 구조체 안에 node를 가리키는 포인터변수가 있음)

 

int main() {

	struct node* ptr = (struct node*)malloc(sizeof(struct node));
	struct node* A = (struct node*)malloc(sizeof(struct node));
	A->data = 10;
	struct node* B = (struct node*)malloc(sizeof(struct node));
	B->data = 20;
	A->link = B;
	B->link = NULL;

	for (ptr = A; ptr != NULL; ptr = ptr->link) {
		printf("%d\n", (*ptr).data);
	}
}

간단한 동작 예시.

for(ptr = A ; ptr != NULL ; ptr = ptr->link) 는 많이 사용하니까 잘 알아두자.