[C로 쓴 자료구조] 단일 연결 리스트 (Singly Linked Lists)

단일 연결 리스트

 

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

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

리스트의 이름 = 첫 번째 노드의 주소

 

 

노드 생성

 

C언어에서 연결 리스트의 노드는 자기 참조 구조체를 이용하여 구현한다.

 

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

int main(void){
	struct node *ptr = NULL;	
	ptr = (struct node *)malloc(sizeof(struct node));
 	
    ptr->data = 10; //(*ptr).data=10;
    ptr->link = NULL;
 }

 

 

두 개의 노드 연결

 

구조체의 link에 다음 노드를 가리키는 포인터를 저장한다

data = 10인 A노드를 B노드에 연결

 

int main(void) {
	struct node* a, * b;

	a = (struct node*)malloc(sizeof(struct node));
	a->data = 10;

	b = (struct node*)malloc(sizeof(struct node));
	b->data = 20;

	a->link = b;
	b->link = NULL;
 }

 

 

연결 리스트 출력

 

연결 리스트의 중간값을 알기 위해서는 반드시 처음 노드부터 출발하여 해당 값이 나올 때까지 전진해야 한다

struct node *ptr;
	for (ptr = a; ptr != NULL; ptr = ptr->link)
		printf("%d\n", ptr->data);

 

 

노드 삽입

 

 

 

새로 추가되는 노드의 링크부터 연결 후,

이전 노드의 링크를 연결하는 로직이 중요하다

void Insert(struct node **start, struct node *before) { //data=50인 새로운 노드를 start가 가리키는 리스트의 before 노드 다음에 삽입.
	struct node* temp; 
	temp = (struct node*)malloc(sizeof(struct node)); //새 노드 생성

	if (temp == NULL) {
		fprintf(stderr, "the memory is full\n");
		exit(1);
	}

	temp->data = 50;

	if (*start != NULL) {
		temp->link = before->link; //새로 추가되는 노드의 링크부터 연결
		before->link = temp;       //이전 노드의 링크 연결
	}
	else {						  //존재하던 노드가 없었을 때
		temp->link = NULL;
		*start = temp;
	}
}

 

 

노드 삭제

 

start가 가리키는 리스트에서 노드 a를 삭제

before는 a 노드의 이전 노드를 가리키고 있음

void Delete(struct node **start, struct node *before, struct node *a) { //start가 가리키는 리스트에서 노드 a를 삭제, before는 a노드의 이전 노드를 가리킴
	if (before != NULL)
		before->link = a->link;
	else
		*start = (*start)->link;
	free(a);
}

 

 

연결 리스트 연산을 통한 노드 추가

 

만약 이전 노드의 값만 알고 있다면 리스트 연산을 통해 노드 추가가 가능하다

	struct node *temp;                // 노드 추가
	temp = (struct node*)malloc(sizeof(struct node));
	temp -> data = 45;
	for (ptr = start; ptr->data != 20; ptr = ptr->link); //ptr의 data가 20이 아닐때 까지 전진

	temp->link = ptr->link;
	ptr->link = temp;

	for (ptr = a; ptr != NULL; ptr = ptr->link)
		printf("%d\n", ptr->data);
	printf("\n");

 

연결 리스트 연산을 통한 노드 삭제

 

마찬가지로 이전 노드에 대한 정보 before가 없을 때 노드를 삭제하는 방법

struct node *target;                    //45 노드 삭제
	for (ptr = start; ptr->link->data != 45; ptr = ptr->link); //ptr이 가리키는 링크의 값이 45일때 까지 전진 (즉 45의 이전 노드까지 전진)

	target = ptr->link; //ptr은 45의 이전 노드
	ptr->link = target->link;
	free(target);

	for (ptr = a; ptr != NULL; ptr = ptr->link)
		printf("%d\n", ptr->data);
	printf("\n");

 

 

 

연결 리스트의 방향 변경

 

연결 리스트 chain의 방향을 반대로 변경하는 함수

 

struct node* invert(struct node* lead) { //lead가 가리키는 리스트의 방향을 반대로 변경
	struct node* middle, * tail;
	middle = NULL;
	while (lead) {
		tail = middle;
		middle = lead;
		lead = lead->link;
		middle->link = tail;
	}
	return middle;
}

 

 

두 개의 연결 리스트를 연결

 

struct node* concatenate(struct node* ptr1, struct node* ptr2) { 
	/* ptr1다음에 ptr2를 연결한 새로운 리스트를 반환. 
	   ptr1이 가리키는 리스트는 새로운 리스트로 변경됨. */

	struct node* t;

	if (ptr1 == NULL)
		return ptr2;
	else {
		if (ptr2 != NULL) {
			for (t = ptr1; t->link != NULL; t = t->link);
			t->link = ptr2;
		}
		return ptr1;
	}
}