[알고리즘] 연결 리스트

연결 리스트(linked list)

; 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

 

단일 연결 리스트

; 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킴

노드 구조체

struct list{			// 연결 리스트의 노드 구조체 
	int *score; 		// 데이터를 저장할 멤버 
	struct list *link; 	// 다음 노드의 주소를 저장할 포인터 
};

 

- list 포인터형 link에는 list구조체로 만든 다른 노드의 메모리 주소 저장

 

연결리스트의 생성과 사용 예시

#include <stdlib.h>
struct list{
	char *name[10];
	int *score;
	struct list *link;
};
struct list *head,*list1,*pre,*nxt; // head는 가장 앞머리, list1은 생성된 노드, pre는 이전 노드, nxt는 다음노드(출력할 때 사용)	
	
int main() {
	head=NULL;
	for(int i=0;i<3;i++){
		list1=(struct list*)malloc(sizeof(struct list)); // list구조체의 사이즈만큼 list1에 동적 할당
		scanf("%s%d",list1->name,&(list1->score));
		if(head==NULL) head=list1;	// 가장 첫 노드라면, head에 부여 
		else pre->link=list1;		// 이전 노드의 포인터에 다음 노드 부여
		list1->link=NULL;			
		pre=list1;					// 다음 노드 생성을 위해, 이전 노드=현재 노드로 바꿈 
	}
	for(nxt=head;nxt!=NULL;nxt=nxt->link){
		printf("%s %d\n",nxt->name,nxt->score);
	}
	while(head!=NULL){
		nxt=head->link;
		printf("%s%d deleted\n",head->name,head->score);
		free(head);
		head=nxt;
	}
	return 0;
}

 

이중 연결 리스트

; 포인터 공간이 두개가 있고, 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킴

 

원형 연결 리스트

; 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조