싱글 링크드 리스트 삽입 3가지 방법

싱글 링크드 리스트에서 삽입을 크게 아래 3가지 방법으로 구현한다.

 

1. head 포인터를 전역변수

2. main안 로컬 변수로 head 포인터

3. 로컬 변수 head 포인터이나 삽입 함수에서 리턴 없이 구현

 

1. head 포인터를 전역변수

1-1) head에 노드 삽입

#include <stdio.h>
#include <stdlib.h>
struct Node {
	int data;
	Node* next;
};
Node* head;

void InsertAtHead(int x)
{
	Node* tmp = (Node*)malloc(sizeof(Node));
	tmp->data = x;
    tmp->next=NULL;


	if(head!=NULL)
		tmp->next = head;

	head = tmp;
	return;
}

int main(void)
{
	InsertAtHead(1);
	InsertAtHead(2);
	InsertAtHead(3);
	InsertAtHead(4);
	InsertAtHead(5);
	
	Node* cur = head;
	while (cur != NULL)
	{
		printf("%d, ", cur->data);
		cur = cur->next;
	}

}

 

실행 결과

head에 1, 2, 3, 4, 5 순서대로 삽입을 했으니 head에서부터 출력을하면 5, 4, 3, 2, 1 순으로 나온다.

 

1-2) 마지막에 노드 삽입

#include <stdio.h>
#include <stdlib.h>
struct Node {
	int data;
	Node* next;
};
Node* head;

void InsertAtTail(int x)
{
	Node* tmp = (Node*)malloc(sizeof(Node));
	tmp->data = x;
	tmp->next = NULL;

	if (head == NULL) // head가 NULL인경우
	{
		head = tmp; // 생성된 노드를 head로 한다.
		return;
	}

	Node* tail = head;
	while (tail->next != NULL) // 마지막 노드를 찾는다.
	{
		tail = tail->next;
	}

	tail->next = tmp; // 마지막 노드의 다음을 생성된 노드로.
	return;

}

int main(void)
{
	InsertAtTail(1);
	InsertAtTail(2);
	InsertAtTail(3);
	InsertAtTail(4);
	InsertAtTail(5);
	
	Node* cur = head;
	while (cur != NULL)
	{
		printf("%d, ", cur->data);
		cur = cur->next;
	}

}

 

실행 결과

마지막 위치에 1, 2, 3, 4, 5를 삽입했으니 head부터 출력하면 1, 2, 3, 4, 5가 출력된다.

 

 

아래의 방법2, 3에서 tail은 방법1과 동일하니 생략하겠습니다.

2. main안 로컬 변수로 head 포인터

#include <stdio.h>
#include <stdlib.h>
struct Node {
	int data;
	Node* next;
};

Node* InsertAtHead(Node* head, int x)
{
	Node* tmp = (Node*)malloc(sizeof(Node));
	tmp->data = x;
	tmp->next = NULL;

	if(head!=NULL)
		tmp->next = head;

	head = tmp;
	return head;
}


int main(void)
{

	Node* head=NULL;

	head = InsertAtHead(head, 1);
	head = InsertAtHead(head, 2);
	head = InsertAtHead(head, 3);
	head = InsertAtHead(head, 4);
	head = InsertAtHead(head, 5);

	Node* cur = head;
	while (cur != NULL)
	{
		printf("%d, ", cur->data);
		cur = cur->next;
	}
}

노드 생성시
tmp->next = NULL; 를 꼭 해주자.

안해주면 next에 쓰레기 값이 들어간다.

 

실행 결과

 

 

* 여기서 head 포인터의 주소값이 바뀔까?

( head에 담긴 주소값이 아니라 포인터 head 자체의 주소값을 말한다.  )

Node* InsertAtHead(Node* head, int x)
{
	...
	return head;
}

뭔가 매개변수 head가 새로운 stack 메모리에 생성되어 head를 반환하여 그게 또 main의 head가 되어

head=InsertAtHead(...) 할때마다 main의 head 자체의 주소값이 바뀔것 같지만

안바뀐다.

 

예제를 실행해보자

int main(void)
{
	Node* head = NULL;
	printf("%p\n", &head);
	head = InsertAtHead(head, 1);
	printf("%p\n", &head);
}

Insert하기전 head의 주소값과 Insert한 후의 주소값을 출력해보겠다.

 

실핼 결과

주소값은 그대로이다.

 

왜냐하면,

처음 main에서 호출하기전  head의 위치는 100이라고 가정하자

Insert함수의 매개변수에 있는 head의 위치는 110이다.

여기에 새로 만들어진 tmp 노드의 주소 값은 heap영역에 위치 200으로 저장되어있고

매개변수의 head(위치:110)가 200을 가리키게 된다.

이때 return head를하면 head의 주소값이 반환되는것이 아닌 head(위치:110)에 들어있는

tmp의 주소값 200이 반환되어 main head에 200이 들어가는것이다.

매개변수의 head(위치:110)는 함수 종료시 사라진다.

 

아래의 코드로 작성해도 main head의 주소값은 안변한다.

Node* InsertAtHead(Node* head, int x)
{
	Node* tmp = (Node*)malloc(sizeof(Node));
	//head = tmp;
	return tmp;
}

 

 

3. 로컬 변수 head 포인터이나 삽입 함수에서 리턴 없이 구현

#include <stdio.h>
#include <stdlib.h>
struct Node {
	int data;
	Node* next;
};

void InsertAtHead(Node** phead, int x)
{
	Node* tmp = (Node*)malloc(sizeof(Node));
	tmp->data = x;
	tmp->next = NULL;

	if (*phead != NULL)
		tmp->next = *phead;

	*phead = tmp;
}


int main(void)
{

	Node* head = NULL;
	InsertAtHead(&head, 1);
	InsertAtHead(&head, 2);
	InsertAtHead(&head, 3);
	InsertAtHead(&head, 4);
	InsertAtHead(&head, 5);


	Node* cur = head;
	while (cur != NULL)
	{
		printf("%d, ", cur->data);
		cur = cur->next;
	}

}

 

 

실행 결과

 

마찬가지로 head 자체의 주소값은 변경되지 않는다.

 

 

방법3은 결과적으로 아래의 메모리 구조를 가짐