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

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

 

 

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

• 새로운 노드를 만들고 데이터를 저장한다.
• 새로운 노드의 next 필드가 prev의 다음 노드를 가리키도록 한다.
• 새로운 노드를 prev의 다음 노드로 만든다.

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

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

typedef struct node Node;

Node *head = NULL;

void main(){
    Node *temp = (Node*)malloc(sizeof(Node));
    temp -> data = data_to_store;
    temp -> next = prev->next;
    prev -> next = temp;
}

• 연결 리스트에 새로운 노드를 삽입할 때 삽입할 위치의 바로 앞 노드의 주소가 필요한데
  • 어떤 노드의 뒤에 삽입하는 것은 삽입할 위치의 바로 앞 노드를 알 수 있어 간단하지만
  • 어떤 노드의 앞에 삽입하는 것은 삽입할 위치의 앞 앞 노드의 주소를 알아야 하기 때문에 간단하지 않다.
    • 앞 앞 노드의 주소를 알 수 없는 것은 아니다.
    • 연결 리스트의 시작 주소를 아는 head가 있기 때문에 노드들을 순차적으로 타고 넘어가면 알 수 있지만
    • 번거롭기 때문에 어떤 노드의 뒤에 삽입하는 방법을 주로 사용

1-1. 함수형

//삽입에 성공하면 1, 아니면 0을 반환
int add_after(Node *prev, char *item){
    if(prev == NULL)
        return 0;

    Node *temp = (Node *)malloc(sizeof(Node));
    temp -> data = item;
    temp -> next = prev -> next;
    prev -> next = temp;

    return 1;
}

 

2. 첫 번째 노드의 삭제

• head가 현재 head 노드가 가리키는 노드(= 첫 번째 노드)의 다음 노드를 가리키게 만든다.

//head는 전역변수
//삭제된 노드의 주소를 리턴
Node * remove_first(){
    //연결된 노드가 하나도 없다면
    if(head == NULL){
        return NULL;
    }
    else{
        Node *temp = head;
        head = head -> next;
        return temp;
    }
}

 

3. 어떤 노드의 다음 노드 삭제하기

• prev의 다음 노드가 null이 아니라면
• prev의 next 필드가 현재 next 노드의 다음 노드를 가리키게 만든다.

//head는 전역변수
//삭제된 노드의 주소를 리턴
Node * remove_after(Node *prev){
    Node *temp = prev -> next;
    //prev가 가리키는 노드가 마지막 노드라면
    if(temp == NULL){
        return NULL;
    }
    else{
        prev -> next = temp -> next;
        return temp;
    }
}

• 단순 연결 리스트에서 어떤 노드를 삭제할 때는 삭제할 노드의 바로 앞 노드의 주소가 필요하다.
  • 삭제할 노드의 주소만으로는 삭제할 수 없다.

 

 

 

 

---

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

https://www.youtube.com/watch?v=0kddqbHGGsM&feature=emb_imp_woyt