[알고리즘 - 연결리스트] 연결 리스트 c언어로 구현하기

기본세팅

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

int main(void) {
	ListNode* p1, * p2, * head;
	p2 = (ListNode*)malloc(sizeof(ListNode));
	p1 = (ListNode *)malloc(sizeof(ListNode));

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

	p2->data = 20;
	p2->link = NULL;
	p1->link = p2;

	head = p1;
  }

ListNode라는 구조체를 만들고 ListNode의 포인터를 이용하여 연결 리스트를 만든다.

 

삽입

//phead : head를 가리키는 포인터 -> head의 손상 방지
//p : 삽입할 위치의 이전 노드
void insert_node(ListNode** phead, ListNode* p, ListNode* new_node) {
	if ((*phead) == NULL) {  //1. 공백 리스트인 경우 - head 변경
		new_node->link = NULL;
		*phead = new_node;
	}
	else if (p == NULL) {  //2. 맨 처음에 노드 삽입 - head 변경
		new_node->link = *phead;
		*phead = new_node;
	}
	else { //3. 평범하게 p 다음에 삽입
		new_node->link = p->link;
		p->link = new_node;
	}
}

삽입의 경우 크게 3가지 경우를 고려해야 한다.

1. 공백 리스트 (즉, 아무것도 없는 리스트인 경우)

2. p == NULL (즉, 첫 노드에 삽입하는 경우)

3. 나머지 (중간이나 끝에 삽입하는 경우)

 

1번과 2번이라는 예외경우는 head가 바뀐다는 특성이 있다!!!

 

또한 head가 아니라 이를 가리키는 포인터의 포인터인 phead를 쓴 이유는 head가 포인터므로 원본 head가 손상될 위험이 있으므로 head를 쓰지않고 이를 가리키는 phead를 사용한다.

삭제

void remove_node(ListNode** phead, ListNode* p, ListNode* removed) {
	if (p == NULL)  //1. 맨 처음 노트 삭제 - head 변경
		* phead = (*phead)->link;
	else  // 2. 나머지
		p->link = removed->link;
	free(removed);
}

 

 

탐색

ListNode* search(ListNode* head, int x) {
	ListNode* p = head;

	while (p != NULL) {
		if (p->data == x)
			return p;
		p = p->link;
	}
	return p;
  }

 

역순

ListNode* reverse(ListNode* head) {
	ListNode* p, * q, * r;
	p = head;
	q = NULL;
	while (p != NULL) {
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}
	return q;
}

r, q, p로 순회하여 연결 리스트를 역순으로 만들어준다.

r은 이전 노드(링크 연결할 때 사용됨)

q는 현재 노드

p는 앞의 노드

 

여기서 중요한 점은 q의 링크가 r로 연결해주면 된다는 점이다.

이를 p가 NULL 즉, 연결 리스트 마지막까지 반복한다(p가 NULL이 되는 순간은 q가 head가 되는 순간이다).