[ 자료구조 ] 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
}
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) 대입
구조체 포인터의 포인터를 가진 노드 삽입 함수
변경하고 싶은 데이터를 값을 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;
구조체 포인터의 포인터
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);
}
'CS > 자료구조' 카테고리의 다른 글
[ 자료구조 ] 리스트와 연결 리스트 공통점과 차이점 총정리 (6) | 2021.11.01 |
---|---|
[ 자료구조 ] linked list 노드 삭제, 연결 리스트를 이용한 스택 큐 구현 (0) | 2021.10.30 |
[ 자료구조 ] linked list 연결 리스트 반복문으로 node 생성하기 (0) | 2021.10.29 |
[ 자료구조 ] 단순 연결 리스트 (0) | 2021.10.28 |
[ 자료구조 ] 연결리스트를 만들기 위한 구조체 선언과 typedef 활용 (1) | 2021.10.27 |