[C언어] 연결리스트 - 개념과 기본 동작들(3)

이번 포스팅에서는 연결 리스트를 순회하고, 연결 리스트에서 특정 인덱스에 값을 추가하거나 삭제하는 방법에 대해 알아보겠습니다.

---

우선 연결 리스트를 순회하는 방법입니다. 메모리상에 순서대로 저장되는 배열과 달리 연결 리스트는 주로 동적 할당을 통해 메모리 상에 순서 관계없이 저장되지만, 그럼에도 연결된 순서는 분명 존재합니다. 때문에 연결 리스트에 저장된 값을 찾기 위해선 역시 연결 리스트를 처음부터 순서대로 찾아보는 메커니즘으로 데이터를 찾아야 합니다.

Node* get_node(int index)
{
	if (index < 0)
		return NULL;
	Node* p = head;
	for (int i = 0; i < index && p != NULL; i++) // index가 연결 리스트의 길이보다 크면 null 리턴
		p = p->next;	// 연결 리스트에서 i번째 인덱스에 위치한 리스트의 주소 리턴
	return p;
}

방법은 위와 같습니다. get_node 함수는 연결 리스트에서 자신이 찾고 싶은 순서의 인덱스를 매개변수로 받고 그 주소를 리턴하는 함수입니다.

우선 함수 내에서 연결 리스트를 처음부터 순회할 Node 구조체 포인터 변수 p를 선언하여 head를 복사해줍니다.

그리고 p의 주소를 p의 다음 주소인 next로 변경하는 것을 for문을 통해 연결 리스트의 처음인 인덱스 0부터 찾으려는 인덱스 순서까지  반복하여 최종적으로 인덱스의 node 주소를 리턴해줍니다.

---

특정 인덱스에 위치한 연결 리스트를 찾는 방법을 알아봤으니, 이번에는 특정 인덱스를 지정하고 그 인덱스 순서의 연결 리스트에 데이터를 추가하는 방법을 알아보겠습니다.

int add(int index, char* item)	// 특정 인덱스에 노드를 추가
{
	if (index < 0)	// 예외처리
		return 0;

	if (index == 0)	// 맨 앞에 추가할 때 add-first에서 노드 생성
	{
		add_first(item);
		return 1;
	}
		
	Node* prev = get_node(index - 1);	// 추가하려는 인덱스 하나 이전 노드의 주소 필요
	if (prev != NULL)
	{
		add_after(prev, item);
		return 1;
	}
	return 0;
}

add 함수에서는 추가하려는 인덱스와 그 인덱스에 저장하려는 데이터를 매개변수로 받습니다. 그리고 함수 내에서는 추가하려는 인덱스가 0, 즉 첫 번째 인덱스일 경우는 add_first 함수를 호출합니다.

그 이후의 인덱스에 데이터를 추가할 때에는 우선 위에서 정의한 get_node 함수를 통해 매개변수로 받은 인덱스보다 하나 앞선 노드를 prev에 저장합니다. 앞선 포스팅에서 다뤘듯이 연결 리스트에서 특정 인덱스에 데이터를 추가하거나 삭제하려면 하나 이전의 노드 주소가 필요하기 때문입니다.

그렇게 prev 노드를 설정하면 이전 포스팅에서 만든 add_after 함수를 통해 데이터를 추가합니다.

---

Node* remove(int index)
{
	if (index < 0)
		return NULL;
	if (index == 0)
		remove_first();
	Node* prev = get_node(index - 1);
	if (prev == NULL)
		return NULL;
	else
		return remove_after(prev);
}

인덱스를 받아 연결 리스트를 삭제하는 방법은 추가하는 방법과 메커니즘이 거의 동일합니다.

 

Node* remove(char* item)
{
	Node* p = head;
	Node* q= NULL;
	while (p != NULL && strcmp(p->name, item) != 0)
	{
		q = p;			// q는 p의 한 칸 이전을 저장
		p = p->next;	// 찾는 값이 나올 때 까지 연결
	}
	if (p == NULL)
		return NULL;
	if (q == NULL) // 삭제할 노드가 첫 번째 노드일 때
		return remove_first();
	else
		return remove_after(q); // prev 노드를 통해 데이터 삭제
}

인덱스를 받아 연결 리스트를 수정하지 않고, 저장된 데이터를 입력받아 그 데이터가 저장된 노드를 삭제하는 방법은 이전의 방법들과 조금 다릅니다. 이 함수에서는 head를 저장하는 포인터 하나와, 반복문에서 p보다 하나 이전의 주소를 저장할 포인터, 이렇게 총 2개의 포인터를 사용합니다.

그 이유는 연결 리스트에서 특정 인덱스의 데이터를 삭제하거나 추가하려면 그 이전 노드의 주소가 필요한 특징 때문입니다. 이점만 이해하고 있으면 크게 다르거나 어려운 점은 없습니다.

---

void add_to_ordered_list(char* item)
{
	Node* p = head;
	Node* q = NULL;
	while (p != NULL && strcmp(p->name, item) <= 0)
	{
		q = p;
		p = p->next;
	}
	if (q == NULL)
		add_first(item);
	else
		add_after(q, item); // item보다 순서가 낮은 q의 다음에 추가하기 때문에 add_after 사용
}

오름차순, 혹은 내림차순 등의 순서대로 데이터를 저장하는 add_to_ordered_list 함수 또한 바로 위의 remove 함수와 같이 포인터를 두 개 사용하여 데이터를 연결 리스트에 추가합니다.