[자료구조]연결리스트를 이용하는 선형리스트(C)

연결리스트를 이용한 선형리스트에 대해 알아보겠다.

연결리스트를 왜 사용하는가?

연결리스트는 배열과 달리 미리 메모리를 할당해놓는 것이 아니라, 사용자가 필요로 할 때, 메모리를 할당받기 때문에 여분의 공간을 마련할 필요가 없어 메모리를 절약할 수 있다.

연결 리스트에서 원하는 요소에 접근하려면 어떻게 해야 될까?

1. 연결 리스트는 다음 노드에 대한 위치정보를 링크필드에 저장하고 있기 때문에 이를 활용하여 원하는 노드를 찾아간다.

2. 첫 번째 헤더로부터 순차적으로 찾아 들어가야한다.

<그림 출처 | https://yjg-lab.tistory.com/118 >

 노드를 구성하는 요소는 노드 = 데이터필드 + 링크 필드다.
 
 1. 데이터 필드는 원소의 값을 저장하고.
 2. 링크필드는 다음 노드의 포인터 변수를 사용하여 주소값을 저장한다.

노드를 구성하는데 있어 C문법으로 어떻게 효과적으로 표현할 수 있을까? -> 구조체를 이용하면 된다.

연결리스트 구조체

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

리스트를 초기화하는 함수

linkedlist_h* creatnode(void)
{
	linkedlist_h* L; //linkedlist에 접근 할 수 있는 포인터 L를 선언함.
	L = (linkedlist_h*)malloc(sizeof(linkedlist_h));
	L->head = NULL;
	return L;
}

1. 첫번째 노드를 반드시 알아야 된다는 필요성 때문에 헤더를 구현했다.

연결리스트에 노드를 추가하는 함수

void addLastNode(linkedlist_h* L, int x)
{
	ListNode* newnode;
	ListNode* p;

	newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;//newnode에 메모리를 할당하고 (노드를 만듦) x의 값을 넣는다.
	newnode->link = NULL;

	if (L->head == NULL) // 만약에 첫번째로 만들어지는 노드라면, head가 newnode를 가르키도록한다.
	{
		L->head = newnode;
		return;
	}
	
	// 이미 첫번째 노드가 있고 다른 경우에는 
	p = L->head; //헤드노드의 값을 p에 대입한다. p == headnode
	while (p->link != NULL)
	{
		p = p->link; //p가 돌아가면서 null이 될때까지 반복한다.
	}
	p->link = newnode;//맨마지막에 newnode노드 추가.
}

연결리스트 출력

void printList(linkedlist_h* L)
{
	ListNode* p;
	p = L->head;
	while (p != NULL)
	{
		printf("%4d", p->data);
		p = p->link;
	}
	printf("\n");
}

case 1: 만약 연결리스트 중간에 노드를 삽입하는 함수를 구현한다면?

핵심 아이디어를 기억할 필요가 있다.

1. 새로 메모리 할당을 받은 노드를 newnode가 가르킨다. 노드 newnode의 data필드에 30을 설정한다.
2. p의 link 필드가 30 다음 노드, 즉 40을 저장하고 있는 노드를 가르키도록 한다.
3. 20을 포함하고 있는 노드의 link필드가 newnode를 가르키도록 한다.

void insertAfter(linkedlist_h* L, int x, ListNode* p)
{
	ListNode* newnode;
	newnode = (ListNode*)malloc(sizeof(ListNode));
	if (L->head == NULL)
	{
		newnode->link = NULL;
		L->head = newnode;
	}

	else if (p == NULL) // 여기서 P가 가르키는 의미는 첫번째 노드다.
	{
		L->head = newnode;
	}
	else
	{
		newnode->link = p->link;
		p->link = newnode; //앞 p
	}


	//head ----> 첫번째로 노드가 삽입될 경우 

	//head ----> node(p) -----> ooo(newnode)

	//head ----->node(p) ------>oooo -------> node(p)
}

case2: 마지막 노드를 삭제한다면?

노드를 삭제하려면 삭제하려는 노드의 바로 이전 노드 링크를 변경해야 하므로 previous라는 포인터를 더 만들어 삭제하려는 노드의 앞 노드를 유지해야된다.

void nodedelete(linkedlist_h* L)
{
	ListNode* previous;//이전 previous 경우
	ListNode* current;//현재 노드를 가르키는 경우 


	if (L->head == NULL)
	{
		return;
	}

	if (L->head->link == NULL)
	{
		// head --> oo(이 노드를 삭제하려고함)
		free(L->head);
		L->head = NULL;
		return;
	}
	else
	{
		previous = L->head;
		current = L->head->link;
		while (current->link != NULL)
		{
			previous = current;
			current = current->link;
		}
		free(current);
		previous->link = NULL;
	}
	// head 값 자체가 없는 경우 
	// head --> oo <삭제하는 경우>
	// head --> node --> ooo <삭제하는 경우>

}

case3 : 삭제하고자 하는 데이터가 저장된 노드 삭제하는 함수는?

1. (10,20,30,40,50,60)이 저장된 연결 리스트에서 30을 찾아 제거하기 위해 deleteNode(L. 30) 형태로 호출했다는 가정이다.

void deletenode(linklist_h* L, int x)// int x는 삭제하는 매개변수다.
{
	ListNode* previous;
	ListNode* current;


	previous = L->head;
	current = previous->link;
	// 중간 노드를 삭제한다는 의미는
	// head ----> previous -----> current(삭제하려는 부분)
	// 탐색(while)을 진행하면서 (조건에 맞으면) ==> x삭제
	while(previous != NULL){
		if (current->data == x)
		{
			break;
		}
		previous = previous->link;
		current = previous->link;
	}

	//본격적으로 삭제하는 부분 

	if (current != NULL)
	{
		previous->link = current->link;
		free(current);
		return 1;
	}
	else
	{
		return 0;
	}

}