CS/자료구조

[ 자료구조 ] linked list 연결 리스트 , k값을 가진 노드 삭제 삽입 함수

psy_er 2021. 10. 29. 00:55
728x90

[ 자료구조 ] linked list 연결 리스트 , k값을 가진 노드 삭제 삽입 함수

리스트는 아무 곳에서나 삽입, 삭제가 일어날 수 있다.

 

k값을 가진 노드 삭제 함수

데이터 값이 k인 노드를 찾는다.

before : k값을 가진 노드의 앞 노드이다.

temp : k값을 가진 노드이다. 이 알고리즘에서 찾는 삭제할 노드이다.

 

before의 링크를 k값을 가지는 링크로 바꾼다. 그리고 반복문을 빠져나온다.

#include <stdio.h>
#include <malloc.h>

struct node {
    int data;
    struct node * link;
};

typedef struct node list_node;
typedef list_node * list_ptr;

void delete(list_ptr p, int k)
{
    list_ptr temp, before; // before는 temp앞 노드를 가리킨다.
    if(!p) return; // p가 null일경우 아무것도 반환하지 않는다. p가 참조하는 리스트가 없다는 뜻
    
    before = NULL 
    for(temp = p; temp!=NULL; temp = temp->data){  // temp!=NULL을 그냥 temp로 바꿀수 있다. 양수=true
    	if(temp->data == k){ // temp의 data가 k인 것을 찾기
            before->link = temp->link; // k를 찾은 뒤, before의 링크를 temp의 링크로 바꾸기
            break;
        }
        before = temp; // k값을 찾을때까지 현재 노드의 주소를 before에 저장한다.
    }
}

int main()
{
    list_ptr p;
    p = create(4);
    print_list(p); // 10 20 30 40
    delete(p,30);
    print_list(p); // 10 20 40
}

 

 

728x90

 

 

Quiz) 만약 맨 처음 노드의 데이터가 k이면 어떻게 해야 하는가?

퍼스트의 링크 값을 퍼스트의 넥스트의 링크로 바꾼다.

// 리스트의 첫 노드, 삭제될 노드의 앞 노드, 삭제될 노드

void delete(list_ptr * p, list_ptr before, list_ptr temp) 
{
    if(temp == *p) // 삭제될 노드가 리스트의 첫 노드일때
        *p = temp->link; // 첫번째 노드의 값을 삭제될 노드의 링크로 바꾼다.
    else // 삭제될 노드가 리스트의 첫 노드가 아닐때
        before->link = temp->link; // 삭제될 앞 노드의 링크값을 현재 링크로 바꾼다. 
        free(node);
}

 

 

k값을 가진 노드 삽입 함수

데이터를 찾아가다가 자신보다 큰 데이터를 만나면, 큰 데이터를 가지는 노드 앞에 새로운 노드를 삽입해야 한다.

 

k = 35를 대입

// 데이터 값 35를 가진 노드를 새로 생성해 삽입한다.

 

temp1 : 새로 생성되는 노드 참조 포인터

// 따라서 데이터 값 35를 가지는 노드를 생성한다.

 

temp : k 보다 큰 값을 찾는 포인터, 노드를 순서대로 참조하다가 k 보다 큰 데이터를 만나면 멈춘다.

// 따라서 데이터 값 40을 가지는 노드를 참조한다.

// temp1 보다 큰 데이터 값을 가지는 뒤 노드

 

before : temp의 앞을 가리키는 포인터

// 따라서 데이터 값 30을 가지는 노드를 참조한다.

// temp1 보다 작은 데이터 값을 가지는 앞 노드

 

#include <stdio.h>
#include <malloc.h>

struct node {
    int data;
    struct node * link;
};

typedef struct node list_node;
typedef list_node * list_ptr;

void insert(list_ptr p, int k){
    list_ptr temp, before, temp1; // 순서대로 temp1 뒤 노드, temp1의 앞 노드, temp1 새로운 노드 포인터이다.
    if(!p) return; // p가 NULL이면 아무것도 반환하지 않는다.
    
    before = NULL; // 새로생긴 temp1의 앞 노드를 before에 저장한다? NULL로 초기화
    for(temp = p; temp != NULL; temp = temp->link){
        if(temp->data > k){
            temp1 = (list_ptr)malloc(sizeof(list_node)); // 새로 생긴 노드 동적 할당
            temp1->data = k; // 새로 생긴 노드에 k값 데이터 대입
            temp1->link = temp; // (2) temp1(새로운)의 링크에 temp(뒤 노드)대입, 뒤를 연결
            before->link = temp1; // (1) before(앞 노드)의 링크에 temp1(새로운) 노드 대입, 앞을 연결
            break; // (temp->data)=40 일때 멈춘다
        }
        before = temp; // temp가 계속 값을 찾을때까지 반복 연결됨
    }
}
int main()
{
    list_ptr p;
    p = create(4);
    print_list(p); // 10 20 30 40
    insert(p, 35);
    print_list(p); // 10 20 30 35 40
}

 

 

(1) 앞 노드(before) 링크에 새 노드 (temp1) 대입

(2) 새 노드 (temp1)의 링크에 뒤 노드(temp) 대입

 

 

728x90

 

 

구조체 포인터의 포인터를 가진 노드 삽입 함수

변경하고 싶은 데이터를 값을 main 함수와 주고받을 때 구조체 포인터의 주소 값(*ptr)을 함수에 넘겨준다(&ptr).

list_ptr *ptr = 구조체 포인터의 포인터이다.

 

 

구조체 포인터의 포인터를 준다

포인터가 가리키는 노드 30 다음에 새로운 노드 50을 삽입하려고 한다.

구조체 포인터의 포인터를 주는 것은 before을 알려주는 것과 같다.

 

변경해야 할 것 1 : 노드 30의 링크 주소,

변경해야 할 것 2 : 새 노드 50의 링크에 노드 20을 가리키는 링크 생성

 

 

연결 리스트 CASE

void insert(list_ptr *ptr, list_ptr aptr, int x){
    list_ptr = temp;
    temp = (list_ptr)malloc(sizeof(list_node));
    
    temp->data = 50;
    if(*ptr){ // 연결리스트가 빈리스트가 아닌 경우
        temp->link = aptr->link; 현재 노드의 링크값을 앞 노드의 링크값으로 바꾼다.
        aptr->link = temp; 앞노드의 링크가 현재 노드를 가리키도록 한다.
    } 
    else { // 연결리스트가 비어있는 경우
        temp->link = NULL; *ptr = temp;
    }

 

1. 연결 리스트가 비어있는 경우

ptr 값이 변경된다.

따라서 prt 대신 ptr의 주소 값 *ptr을 인자로 받아야 한다.

함수에서 ptr 값 변경을 위해 주소를 전달하는 것이다.

 

 

2. 연결 리스트가 빈 리스트가 아닐 경우

 

현재 링크를 전 링크로 바꾸고

temp->link = aptr->link

전 링크가 현재 노드를 참조하도록 바꾼다

aptr->link = temp;

 

 

728x90

 

 

구조체 포인터의 포인터 

void insert (list_ptr *ptr, list_ptr node)

int main(){
   insert (&ptr, node); }

 

 

ptr의 주소 값을 인자로 전달하는 경우

#include <stdio.h>
#incldue <malloc.h>
struct node{
    int data;
    struct node * link; // 자기참조 구조체
};
typedef struct node list_node;
typedef list_node * list_ptr;

void create1(list_ptr * ptr) // 구조체 포인터의 포인터를 받음
{
    list_ptr temp = NULL;
    temp = (list_ptr)malloc(sizeof(list_node)); // 새로운 temp 노드에 동적할당
    temp->data = 10;
    temp->link = NULL;
    *ptr = temp;
}
int main()
{
    list_ptr ptr = NULL; // 구조체 포인터 선언
    create1(&ptr); // 구조체 포인터의 주소값 전달
    printf("%d\n", ptr->data);
}
728x90