[자료구조 - C언어] 자료구조 제11강: 연결 리스트 - 개념과 기본 동작들(3)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

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

• 새로운 노드를 만들고 → 추가할 데이터를 저장
  • 배열) 공간을 미리 잡아두고 데이터를 수시로 채움
  • 연결 리스트) 필요할 때마다 동적 할당으로 노드를 생성 ~ 노드의 개수 = 데이터의 개수
• 새로운 노드의 next 필드가 현재 head 노드가 가리키는 노드를 가리키도록 한다.
  • 현재의 head 노드가 가리키는 노드의 주소는 head 노드에 저장되어 있다.
    • head노드는 첫 번째 노드를 가리킴
• 새로 생성한 노드를 새로운 head 노드로 한다
  • 이 과정을 앞선 과정보다 먼저하면 원래 가리키고 있었던 첫 번째 노드의 주소를 분실하기 때문에 순서에 유의

#include <stdio.h>
#include <stdlib.h>

struct node{
    char * data;
    struct node * next;
};

typedef struct node Node;

Node *head = NULL; 

void main(){
    Node *tmp =(Node *)malloc(sizeof(Node));
    tmp -> data  = "YJ";
    tmp -> next = head;
    head = tmp;
}

 

2. 함수형

2-1. 포인터 head가 전역변수인 경우

• 첫 번째 노드를 가리키는 포인터 head가 전역 변수인 경우에는
  • 코드 아무곳에서나 head에 액세스 할 수 있기 때문에 코드에 변화가 없다.

  //포인터 head가 전역변수
  //  코드의 아무곳에서나 head에 엑세스 할 수 있기 때문
  //char * item: 연결리스트에 추가할 데이터
  void add_first(char *item){
      Node *temp = (Node *)malloc(sizeof(Node));
      temp -> data = item;
      temp -> next = head;
      head = temp;
  }

 

2-2. 포인터 head가 전역 변수가 아닌 경우 - Node **ptr_head

• head가 전역변수가 아닐 때 (2-1)처럼 하면
  

  

  • 새로운 값을 맨 앞에 삽입해도 함수를 호출한 곳의 head는 여전히 같은 값을 가리킨다.

 

• 호출된 함수가 내가 가지고 있는 지역변수(= 호출한 곳의 head)의 값에 영향을 끼치게 하고 싶을 때
  변수의 값 대신 변수의 주소를 매개변수로 넘겨줄 것
  • 포인터 변수 head의 주소를 매개변수로 받는다
    • head노드의 주소를 값으로 넘겨주는 것이 아니라
    • head노드의 주소가 저장된 변수의 주소를 매개변수로 넘겨주면
      • 호출된 함수에서 head의 값을 변경할 수 있다.

//포인터 head가 지역변수
void add_first(Node **ptr_head, char *item){
    Node *temp = (Node  *)malloc(sizeof(Node));
    temp -> data = item;
    //현재 ptr_head가 가리키고 있는(= head)곳에 저장된 값
    // = head가 가리키는 첫 번째 노드의 주소
    temp -> next = *ptr_head;
    *ptr_head = temp;
}

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

 

2-3. 포인터 head가 전역 변수가 아닌 경우 - Node *head

//포인터 head가 지역변수
//새로운 head 노드의 주소를 return
Node *add_first(Node *head, char *item){
    Node *temp = (Node *)malloc(sizeof(Node));
    temp -> data = item;
    temp -> next = head;
    return temp;
}

//호출
head = add_first(head, item_to_store);

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?v=9Qi3PhBSzA0