[C/C++]연결리스트 - 단순 연결리스트 SLL

연결리스트를 제가 이해한 대로 서술해보겠습니다.

연결리스트는 크게 세가지 인데 단순연결리스트, 원형연결리스트, 이중연결리스트가 있습니다. 이번 글에서는 단순연결리스트에 대해 복습해 볼 겁니다.

노드

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode *link;
}ListNode;

연결리스트는 링크필드와 데이터필드를 갖고있는 노드들로 형성됩니다. 링크필드가 다음노드를 가리키는 형태이기 때문에 자연스럽게 자기참조를 이용하게 되죠.

이 형태를 이해 할 때는 링크필드를 밧줄이라고 생각하면 편합니다. 각각의 노드는 밧줄을 걸어놓는 고리라고 생각을 하시구요.

고리에 밧줄이 묶여있고 묶여 있는 밧줄은 다음 고리에 묶을 수 있다고 생각하면 됩니다.

헤드포인터

ListNode* head = NULL;

단순연결리스트는 head만 있어도 됩니다. head는 첫 노드를 가리키는 포인터로, 단순연결리스트에서는 어떤 동작을 수행하려면 무조건 head를 거쳐야 합니다.

삽입/삭제

연결리스트의 삽입/삭제 함수는 4개인데, 이들의 공통점은 위에서 밧줄로 설명한 링크필드가 핵심이라는 것입니다.

insert_first()
insert()
delete_first()
delete()

이렇게 4개가 있습니다.

ListNode* insert_first(ListNode* head, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head; 
	head = p;
	
	return head;
}

insert_first함수 먼저 보겠습니다.

이 함수는 리스트 맨 앞에 삽입을 수행하며, 매개변수로 헤드포인터와 삽입될 값을 받아옵니다.

연결리스트는 배열과 달리 삽입 삭제에 대해 자유도가 높다는 사실을 알고 계실 겁니다. 그 부분을 동적으로 조절하기 위해 malloc으로 삽입할 노드를 만들어 줍니다.

만들어진 변수 p가 연결리스트의 첫 노드를 가리킨다면 그것이 head포인터라고 볼 수 있습니다.

p->data에 삽입될 값을 저장해주고, head포인터가 가진 밧줄을 p->link에게 넘겨줍니다. p->link는 변수 p 가 가리키고 있는 노드가 가리키는 위치입니다.

삽입될 노드가 가리키는 위치가 원래 head가 가리키던 위치가 되는 것이죠.

return 값은 head입니다. 쉽게 생각하면 변경사항 저장같은 느낌입니다.

아래 그림으로 나타내 봤습니다.

insert함수도 크게 다를 것은 없습니다.

달라진 점은 리스트 중간에 삽입하기 때문에 삽입할 위치에 선행노드를 반드시 알아야한다는 것이죠.

ListNode* insert(ListNode* head, element value, ListNode* pre) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = pre->link;
	pre->link = p;

	return head;
}

ListNode* pre라고 선행노드를 가리키는 포인터변수가 하나 생겼습니다.

리스트 중간에 삽입할 때는 head값을 직접 사용하지않습니다. 선행노드가 가리키던 것을 삽입할 노드가 가리키게하고, 선행노드가 가리키던 자리에는 삽입할 노드가 들어갑니다.

이번에도 그림으로 나타내 봤습니다.

삭제함수들의 특징은 버리는 변수입니다.

이걸 removed라고 구현했는데 코드랑 같이 보시죠.

ListNode* delete_first(ListNode* head) {
	ListNode* removed;
	if (head == NULL) return NULL;
	removed = head;
	head = removed->link;

	free(removed);
	return head;
}

삭제연산인 만큼 매개변수로는 head하나만 옵니다. delete_first의 경우 첫번째 노드를 삭제하는 것이다보니까 공백인 경우도 확인을 해야합니다.

head == NULL이어도 단순연결리스트임은 맞으니 이걸 먼저 확인해주고 진행합니다. removed와 head가 같은 걸 가리키게 합니다. head는 removed가 가리키고 있던 노드가 가리키는(link field)것을 가리키게 됩니다.

사용이 끝난 removed는 메모리 해제를 통해 삭제해줍니다.

가리킨다는 표현이 계속 반복되기 때문에 혼동이 생길 수 있다는 점 주의해주세요.

리스트 중간에 있는 노드 삭제는 더 쉽습니다. 리스트 중간에 위치하므로 선행노드의 정보는 반드시 필요합니다.

ListNode* delete(ListNode* head, ListNode* pre) {
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;

	free(removed);
	return head;
}

removed가 선행노드가 가리키고 있는 것을 가리키게 하고, removed가 가리키는 노드가 가리키고있는 걸 선행노드의 링크필드에 달아줍니다.

사용이 끝난 removed는 메모리 해제를 해주고요.

delete_first에 비교했을때 head가 pre->link가 된 것일 뿐 나머지는 동일하므로 그림을 따로 그리지 않겠습니다.

삭제연산을 잘 살펴보면 스왑과 비슷한 느낌이 듭니다. 임시로 저장할 공간을 만들고, 자리를 바꿔주는 게 그 모양새가 닮았다고 느꼈어요.

전체 코드도 올려드리니 한번 쭉 살펴보시길 바랍니다. 책에 있는 코드 그대로이고 주석으로 달아놓은 부분은 리스트 중간에 것을 삭제해본 겁니다.

#include <stdio.h>

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode *link;
}ListNode;

void error(char* message) {
	fprintf(stderr, "%s", message);
	exit(1);
}

ListNode* insert_first(ListNode* head, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head;
	head = p;
	
	return head;
}

ListNode* insert(ListNode* head, element value, ListNode* pre) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = pre->link;
	pre->link = p;

	return head;
}

ListNode* delete_first(ListNode* head) {
	ListNode* removed;
	if (head == NULL) return NULL;
	removed = head;
	head = removed->link;

	free(removed);
	return head;
}

ListNode* delete(ListNode* head, ListNode* pre) {
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;

	free(removed);
	return head;
}

//ListNode* pre;

void print_sll(ListNode* head) {
	for (ListNode* p = head; p != NULL; p = p->link) {
		printf("%d->", p->data);
		//if (p->data == 3) pre = p->link; data가 3인 경우에 그때 링크를 전달하므로 pre가 가리키고있는 노드의 data값은 2가 된다.
	}
	printf("NULL \n");
}

int main() {
	ListNode* head = NULL;
	for (int i = 0; i < 5; i++) {
		head = insert_first(head, i);
		print_sll(head);
	}
	for (int i = 0; i < 5; i++) {
		head = delete_first(head, i);
		print_sll(head);
	}
	/*printf("\n\n");
	head = delete(head, pre); //4->3->2->0->>NULL
	print_sll(head);*/

	return 0;
}

이해 안가는 부분 있으시면 댓글로 남겨주시면 됩니다.