LinkedList(C언어)

LinkedList

 LinkedList는 자료구조의 일종으로, 배열과 같이 여러 개의 자료를 저장할 수 있는 새로운 자료형이라고 이해하면 된다. 여러 개의 정수, 심지어 여러 개의 구조체도 저장할 수 있다.

 

 LinkedList의 개념은 다음과 같다. 우선, LinkedList 구조체부터 선언한다.

struct LinkedList {
	int data;//Linked List가 가지는 데이터
	LinkedList* next;//다음 Linked List의 주소
} typedef LinkedList;

 

그림으로 보면 다음과 같다.

 

이제, next에 다른 LinkedList*를 넣어 다음(next) LinkedList에 연결해 주자

이렇게 하면 두 개의 LinkedList가 연결되었다. a의 next가 b의 주소를 가지게 되었으니, a->next로 b에 접근이 가능하다. 코드로는 이렇게 나타낼 수 있다.

LinkedList* a = (LinkedList*)malloc(sizeof(LinkedList));
a->data = 1;
LinkedList* b = (LinkedList*)malloc(sizeof(LinkedList));
b->data = 2;
b->next = NULL;
a->next = b;

 

 

배열과의 차이점

1. 크기를 미리 정할 필요가 없다

2. 배열은 새로운 값 추가 시 비효율적이지만, LinkedList는 보다 효율적이다.

 

3. 배열은 값 삭제 시 메모리가 낭비되지만, LinkedList는 값 삭제 시 메모리가 낭비되지 않는다.

 외에도 다른 차이점들이 있지만, 우선적으로 알아두어야 할 것은 아니니 여기서 마무리한다(기초 강의 용도이므로 자세하게 다루지 않는다).

 

 

 

LinkedList에 데이터 삽입

 LinkedList에 데이터를 어떻게 삽입할 수 있을까? 위에서 눈치챘을 수도 있지만, 새로운 LinkedList 구조체를 하나 만들어 중간에 끼워 넣으면 된다. 말로 하면 어려우니 그림과 코드를 통해 이해해 보자.

//데이터 삽입
LinkedList* a = (LinkedList*)malloc(sizeof(LinkedList));
a->data = 1;
LinkedList* b = (LinkedList*)malloc(sizeof(LinkedList));
b->data = 2;
b->next = NULL;
a->next = b;
//a->b 인 상황

//새로운 LinkedList 생성
LinkedList* c = (LinkedList*)malloc(sizeof(LinkedList));
c->data = 3;

//a의 next를 c로
a->next = c;

//c의 next를 b로
c->next = b;

//a->c->b가 됨

 

함수 구현

 함수를 사용해서 데이터를 추가하는 예제이다. 맨 마지막에 데이터를 삽입하는 함수이며, 특정 위치에 데이터를 삽입하는 함수는 직접 구현해 보는 것을 권장한다.

/*
* Description: Linked List의 마지막에 데이터를 추가하는 함수
* 
* Parameter:
* linkedList: Linked List의 시작점을 가리키는 Linked List포인터
* data: Linked List에 추가할 데이터
* 
* Return: void
*/
void addDataInLinkedList(LinkedList** linkedList, int data) {

	LinkedList* head = *linkedList;//head는 linkedList의 주소를 가지고 있음
	LinkedList* newLinkedList = (LinkedList*)malloc(sizeof(LinkedList));//새로운 Linked List를 만들어줌
	newLinkedList->data = data;//새로운 Linked List의 data에 data를 넣어줌
	newLinkedList->next = NULL;//새로운 Linked List의 next는 NULL(마지막 Linked List이므로)

	//linkedList가 NULL이면 새로운 Linked List를 linkedList로 만들어줌
	if (*linkedList == NULL) {
		*linkedList = newLinkedList;
		return;
	}
	
	//마지막 Linked List까지 head 이동
	while (head->next != NULL) {
		head = head->next;
	}

	//현재 head는 마지막 Linked List를 가리키고 있고, head의 next는 NULL임
	//head의 next에 새로운 Linked List의 주소를 넣어줌
	//그럼 마지막 Linked List는 위에서 만든 새로운 Linked List가 될 것임
	head->next = newLinkedList;
}

int main() {
	LinkedList* linkedList = NULL;
	addDataInLinkedList(&linkedList, 1);
	addDataInLinkedList(&linkedList, 2);
	addDataInLinkedList(&linkedList, 3);
	return 0;
}

 

 

 

 

 

 

 

LinkedList에 데이터 삭제

 LinkedList의 데이터를 삭제하기 위해선 해당 LinkedList의 이전 LinkedList의 next를 해당 LinkedList의 next로 만들면 된다. 그림과 코드를 통해 이해해 보자.

 우선, 2라는 값을 가진 LinkedList를 삭제한다고 가정한다. head를 사용해 2를 가진 LinkedList*를 찾을 때까지 head를 head->next로 만들어준 뒤, 찾았다면 head 이전의 LinkedList(prev)의 next를 head의 next로 만들어준다. 이건 코드로 보면 이해가 더 쉬울 것 같다.

 

함수 구현

/*
* Description: Linked List에서 데이터를 삭제하는 함수
* 
* Parameter:
* linkedList: Linked List의 시작점을 가리키는 Linked List포인터
* data: 삭제하고자 하는 데이터
* 
* Return: 
* 성공 시 1, 실패 시 0
* */
int removeDataInLinkedList(LinkedList** linkedList, int data) {
	//a -> b -> c 에서 b를 삭제하려면
	//a의 next에 c의 주소를 넣어주면 됨
	//그러기 위해선 이전 Linked List의 주소를 알아야 함
	//그래서 prev라는 포인터를 만들어서 이전 Linked List의 주소를 저장해줌
	//b에 head가 도착했을 때 prev는 a의 주소를 가지고 있음
	//만약 c에 head가 도착했을 때 prev는 b의 주소를 가지고 있음
	//b에서 값을 찾았다면, a의 next(prev->next)에 c의 주소(head->next)를 넣어주면 됨
	//이렇게 하면 b는 고립되고, b를 free하면 됨
	LinkedList* head = *linkedList;//head는 linkedList의 주소를 가지고 있음
	LinkedList* prev = NULL;//현재 head의 이전 Linked List의 주소를 저장할 포인터(아직 head가 첫 번째 Linked List이므로 이전 Linked List는 없음)

	//linkedList가 NULL이면 삭제할 데이터가 없으므로 0 반환
	if (*linkedList == NULL) {
		return 0;
	}

	//head->next가 NULL이 아닐 때까지 반복(마지막 Linked List의 next는 NULL이므로)
	while (head != NULL) {
		if (head->data == data) {//head의 data가 찾고자 하는 데이터와 같으면
        	// 삭제할 노드가 첫 번째 노드인 경우
			if (prev == NULL) {
				*linkedList = head->next;
			}
			else {
				prev->next = head->next;//prev의 next에 head의 next를 넣어줌(prev -> (head->next))
			}
			free(head);//head를 free
			return 1;//성공 시 1 반환
		}
		prev = head;//prev에 현재 head의 주소를 넣어줌
		head = head->next;//head를 다음 Linked List로 이동
		//prev -> head ->(head->next) 상태임
	}
	return 0;//실패 시 0 반환
}

int main() {
	LinkedList* linkedList = NULL;
	addDataInLinkedList(&linkedList, 1);
	addDataInLinkedList(&linkedList, 2);
	addDataInLinkedList(&linkedList, 3);
	removeDataInLinkedList(&linkedList, 2);
	removeDataInLinkedList(&linkedList, 1);
	return 0;
}

 

 

 

 

 삽입, 삭제만 다루었지만, 다양한 방법, 다양한 구현 방식에 따라 함수의 기능은 달라질 수 있다. 

 

 

 

 

 

 

 

 

 

 

과제

LinkedList1.cpp

0.00MB

LinkedList2.cpp

0.00MB

LinkedList3.cpp

0.00MB