연결리스트 - 삽입하기

1. 연결리스트의 맨 앞에 새로운 노드 삽입하기

 

다음과 같은 알고리즘을 기억하면 좋다.

 

1) 새로운 노드를 만들고 추가할 데이터를 저장한다.

2) 새로운 노드의 next 필드가 현재의 head 노드를 가리키도록 한다.

3) 새로운 노드를 새로운 head 노드로 한다.

 

 

 

 

 

다음과 같이 코드를 작성할 수 있다.

 

Node *tmp = (Node *)malloc(sizeof(Node));   // 새로운 노드 생성
tmp->data = “Ann”;   // (1) 추가할 데이터 저장
tmp->next = head;    // (2) 새로운 노드의 next 는 기존의 head를 가리키게 한다
head = temp          // (3) head 는 temp 로 한다

 

 

 

 

 

이와 관련 함수 작성

1) head = 전역변수

 

void add_first(char *item)
{
 	Node *temp = (Node *)malloc(sizeof(Node));
 	temp->data = item;
 	temp->next = head;
 	head = temp;    // ***
}

 

add_first 함수는 "맨 앞에 새로운 노드를 삽입하는 함수"이고 매개변수는 "추가하고 싶은 문자열"을 의미한다.

head 가 전역변수일 경우(Node *head = NULL) 위와 같이 코딩이 가능하지만, head가 지역변수라면 문제가 발생할 수 있다. 

 

 

즉, 지역변수란 이런 경우를 말한다.

↓

main(){
	Node* head;  // head는 main 함수의 지역변수
    	.
    	.
    	add_first("Ann", head);
    	..

 

그니까 main() 안에서 head 변수가 연결리스트의 첫번째 주소를 가리키고 있는데 이때 add_first 호출할 때 이 head에 저장되어 있는 값을 매개변수로 넘겨주면 문제가 발생한다. C언어는 기본적으로 "Call by value" 의 원칙을 가지고 있기 때문이다. (=head 값만 복사될 뿐 실제 head 값이 변경되지 않는다는 뜻) 

 

 

따라서 지역변수일 경우 다음과 같이 작성해주자.

 

2) head = 지역변수

 

void add_first(Node **ptr_head, char *item)
{
 	Node *temp = (Node *)malloc(sizeof(Node));
 	temp->data = item;
 	temp->next = *ptr_head;
 	*ptr_head = temp;
}

 

ptr_head 는 head 의 주소를 가지고 있는 변수이다. 그래야 head 값 변경이 가능해진다.

또한 이렇게 구현할 경우 이 함수는 다음과 같이 호출되어야 한다.

 

add_first(&head, item_to_store);   // add_first 함수 호출

 

 

 

또 다른 방법 (return 문 활용)

 

Node *add_first(Node *head, char *item)   // 반환값이 주소이므로 Node * 타입이다.
{
 	Node *temp = (Node *)malloc(sizeof(Node));
 	temp->data = item;
 	temp->next = head;
 	return temp;   // 새로운 head 노드의 주소를 리턴한다.
}

 

이렇게 구현할 경우 이 함수는 다음과 같은 식으로 호출되어야 한다.

 

head = add_first(head, item_to_store);

 

 

 

 

---

2. 어떤 노드 뒤에 새로운 노드 삽입하기

 

다음과 같은 알고리즘을 기억하면 좋다. 위와 비슷한 알고리즘이다.

 

1) 새로운 노드를 만들고 데이터를 저장한다.

2) 새로운 노드의 next 필드가 prev의 다음 노드를 가리키도록 한다.

3) prev의 다음 노드를 새로운 노드로 만든다.

 

 

 

 

 

 

다음과 같이 코드를 작성할 수 있다.

 

Node *tmp = (Node *)malloc(sizeof(Node)); 
tmp->data = data_to_store; 
tmp->next = prev->next;   // ***
prev->next = tmp;

 

 

 

 

 

이와 관련한 함수를 작성해보면 다음과 같다.

 

int add_after(Node *prev, char *item)   /* 삽입에 성공하면 1, 실패하면 0 반환 */
{
 	if (prev==NULL) 
 		return 0; 
        
 	Node *tmp = (Node *)malloc(sizeof(Node));
 	tmp->data = item;
 	tmp->next = prev->next;
 	prev->next = tmp;
    
 	return 1;
}

 

연결리스트에 새로운 노드를 삽입할 때 삽입할 위치의 바로 앞 노드의 주소가 반드시 필요하다. 즉 어떤 노드의 뒤에 삽입하는 것은 간단하지만, 반대로 어떤 노드의 앞에 삽입하는 것은 간단하지 않다.