이번주 과제 - singly linked list 구현하기
Singly linked list
- node를 사용하여 구현한 리스트인데
- array list와 달리, 엘리먼트 간의 연결 link을 이용해서 리스트를 구현한 것이다.
- array list는 각 요소를 element라고 하지만,
- linked list에서는 node, vertex라고 한다.
- 장점 :
- 동적으로 메모리 사용 가능함
- 메모리를 효율적으로 사용할 수 있다.
- 데이터 재구성이 용이하다.
- 대용량 데이터 처리하는 데 적합하다.
Node
typedef struct Node{ int data; Node *next; } Node;구성요소 1. 사용자가 추가한 데이터 내용
구성요소 2. 다음 노드와의 연결
cf. 마지막 노드는 NULL로 저장한다.
→ 배열 리스트와 달리, 연속된 공간에 저장되어있지 않음
대신, 다음 노드의 주소를 저장해서 탐색할 수 있음
노드를 선언할 때는
Node *head; Node *tail; int *data; //Node는 typedef로 데이터타입으로 만든 구조체이기 때문에 //노션에서 인식 못함연결 리스트 LINKED LIST
연결 리스트의 기본적인 세 함수는
초기화, 삽입, 삭제임.
초기화
- head node → 주소 NULL
- tail node → 주소 NULL
를 설정한다.
Node *head; //head 선언 Node *tail; //tail 선언 void init(void){ head = new Node; //이때 head 포인터에 Node 구조체로 동적할당한다. tail = new Node; //tail에도 마찬가지로 적용 head->next=NULL; //이때 head의 next에는 NULL 할당 tail->next=NULL; //INIT이니까 얘도 마찬가지로 적용 }- 여기서 new는 동적 메모리 할당을 위한 연산자로 malloc과 같은 작업을 수행한다.
- head = new Node ↔ '주소를 저장할 포인터' = new '할당하고 싶은 크기의 자료형'이라는 뜻이므로head라는 포인터에 앞서 정의한 typedef Node 구조체라는 자료형으로 동적 할당한다는 의미
- *** 이건 c++ 기준,
- c에서는 (Node *)malloc(sizeof(Node)); 라고 선언해주어야 한다.
삽입
- 노드를 추가하고 싶다면?맨 앞에 노드를 추가
- tail을 이용함
- tail
- 탐색을 통해 원하는 위치 찾음
- 앞 주소
- 뒷 주소가 가리키는 주소를 수정함
- 원하는 위치에 추가하기
void Addnode(int data){ //동일하게 노드 생성해줌 Node *newNode = (Node *)malloc(sizeof(Node)); //초기화 newNode->data = data; newNode->next = NULL; tail->next = newNode; }- 맨 뒤에 노드를 추가
void Addnode(int data){ //추가할 노드 만들기 Node *NewNode = (Node *)malloc(sizeof(Node)); NewNode->data = data;//Addnode에서 input으로 가져온 data int를 대입 NewNode->next = NULL; //노드가 하나도 없으면 head에 연결하기 if(head->next == NULL){ head->next = NewNode; //차이점은 newNode->next가 NULL로 유지되느냐 아니냐의 여부 } else{ //새로 추가되는 노드의 다음주소 --> 현재 head가 가리키는 주소 NewNode->next = head->next; //head가 가리키는 주소 --> 새로 추가된 노드 head->next = NewNode; } }-
- 노드별로 자기 정보 data, 다음 노드를 가리키는 포인터로 구성된다.
- 따라서 이때 head가 추가하는 노드를 가리키도록 하고,
- 원래 head가 가리키던 노드를 추가하는 노드가 가리키도록 변경한다.
삭제
삭제할 노드의 앞 노드, 뒷 노드를 연결해준다.
** 노드 메모리 free 해주어야 함
void RemoveNode(int remove_data){ Node *cur = head->next; Node *pre = head; //탐색을 통해 삭제할 노드를 cur이 가리키게 하고 //삭제할 노드의 바로 전 노드를 pre가 가리키게 합니다. while(cur->data != remove_data){ pre = cur; cur = cur->next; } //pre가 가리키느 노드의 다음 주소 --> cur이 가리키는 다음 주소 pre->next = cur->next; //cur이 가리키는 노드 free free(cur); free(pre); }
자료구조 : 연결리스트 (Linked list)
자료를 저장하는 방법 중 크게 배열과 연결리스트가 있습니다. 그럼 언제 배열을 사용하고 언제 연결리스트를 쓸까요? 먼저 두 자료구조의 장, 단점에 대해 알아보겠습니다. 표1 배열, 연결리스트 장점 및 단점 배열은 접근이 빠르고 간단합니다. n번째 인덱스에 접근할 경우 arr[n]을 사용하면 빠른 시간에 접근할 수 있습니다.
과제를 해보자
스켈레톤 코드
// singly linked list // singly linked list, append, insert, delete를 구현하라 #include <stdio.h> #include <stdlib.h> typedef struct __node{ int data; struct __node *next; } node; typedef struct __list{ node* head; int cnt; }list; void clear_list(list*); void append_node(list*); void insert_node(list*); void delete_node(list*); void print_list(list*); void reverse_list(list*); void sort_list(list*); int main(void){ printf("\033[2J\033[H"); // clear screen printf("\t**week10 practice**\n"); list *L = (list*)malloc(sizeof(list)); if (!L) printf("Failed to Init.\n"); // error 확인 L->head=NULL; L->cnt = 0; while(1){ printf("a : append i : insert d : delete\nr : reverse s : sort p : print \nq : quit\n"); printf("Press key : "); char c = getchar(); getchar(); //remove \n printf("\033[2J\033[H"); //clear screen switch(c){ case 'a' : append_node(L); break; case 'i' : insert_node(L); break; case 'd' : delete_node(L); break; case 'r' : reverse_list(L); break; case 's' : sort_list(L); break; case 'p' : print_list(L); break; case 'q' : clear_list(L); return 0; default : printf("Invalid key\n"); } } return 0; } /* void Addnode(int data){ //추가할 노드 만들기 Node *NewNode = (Node *)malloc(sizeof(Node)); NewNode->data = data; NewNode->next = NULL; //노드가 하나도 없으면 head에 연결하기 if(head->next == NULL){ head->next = NewNode; } else{ //새로 추가되는 노드의 다음주소 --> 현재 head가 가리키는 주소 NewNode->next = head->next; //head가 가리키는 주소 --> 새로 추가된 노드 head->next = NewNode; } } */ void append_node(list *L){ //node N 선언 node *N = (node*)malloc(sizeof(node)); if (!N){ printf("Failed to create a node\n"); return; } int n; printf("Data : "); scanf("%d", &n); getchar(); // remove \n N->data = n; N->next = L-> head; L-> head = N; L->cnt++; printf("\033[2J\033[H"); printf("\t Append Succeeded\n"); } void delete_node(list *L){ if (L-> cnt==0){ //element가 0인 경우 printf("Empty\n"); return; } int idx; node *curr = L->head; //node delete var 1 node *prev = NULL; //node delete var 2 printf("Index(0~) : "); scanf("%d", &idx); getchar(); printf("\033[2J\033[H"); if (idx > L->cnt-1 || idx<0){ printf("Invalid Index\n"); } else if (idx == 0){ L->head = L->head->next; free(curr); } else { while (idx--){ prev = curr; curr = curr->next; } prev->next = curr->next; free(curr); } L->cnt--; printf("\t Delete Succeeded\n"); } void insert(list *L){ } void print_list(list *L){ if (L->cnt ==0){ printf("Empty\n"); return; } node *t=L->head; while(t){ printf("%d ", t-> data); t = t->next; } printf("\n"); } void clear_list(list *L){ while (L->head){ node *tmp = L->head; L->head = L->head->next; free(tmp); } free(L); } void reverse_list(list *L){ return; } void sort_list(list *L){ return; } 진행중인 곳
// singly linked list // singly linked list, append, insert, delete를 구현하라 #include <stdio.h> #include <stdlib.h> typedef struct __node{ int data; struct __node *next; } node; typedef struct __list{ node* head; int cnt; }list; void clear_list(list*); void append_node(list*); void insert_node(list*); void delete_node(list*); void print_list(list*); void reverse_list(list*); void sort_list(list*); int main(void){ printf("\033[2J\033[H"); // clear screen printf("\t**week10 practice**\n"); list *L = (list*)malloc(sizeof(list)); if (!L) printf("Failed to Init.\n"); // error 확인 L->head=NULL; L->cnt = 0; while(1){ printf("a : append i : insert d : delete\nr : reverse s : sort p : print \nq : quit\n"); printf("Press key : "); char c = getchar(); getchar(); //remove \n printf("\033[2J\033[H"); //clear screen switch(c){ case 'a' : append_node(L); break; case 'i' : insert_node(L); break; case 'd' : delete_node(L); break; case 'r' : reverse_list(L); break; case 's' : sort_list(L); break; case 'p' : print_list(L); break; case 'q' : clear_list(L); return 0; default : printf("Invalid key\n"); } } return 0; } /* void Addnode(int data){ //추가할 노드 만들기 Node *NewNode = (Node *)malloc(sizeof(Node)); NewNode->data = data; NewNode->next = NULL; //노드가 하나도 없으면 head에 연결하기 if(head->next == NULL){ head->next = NewNode; } else{ //새로 추가되는 노드의 다음주소 --> 현재 head가 가리키는 주소 NewNode->next = head->next; //head가 가리키는 주소 --> 새로 추가된 노드 head->next = NewNode; } } */ void append_node(list *L){ //node N 선언 node *N = (node*)malloc(sizeof(node)); if (!N){ printf("Failed to create a node\n"); return; } int n; printf("Data : "); scanf("%d", &n); getchar(); // remove \n N->data = n; N->next = L-> head; L-> head = N; L->cnt++; printf("\033[2J\033[H"); printf("\t Append Succeeded\n"); } void delete_node(list *L){ if (L-> cnt==0){ //element가 0인 경우 printf("Empty\n"); return; } int idx; node *curr = L->head; //node delete var 1 node *prev = NULL; //node delete var 2 printf("Index(0~) : "); scanf("%d", &idx); getchar(); printf("\033[2J\033[H"); if (idx > L->cnt-1 || idx<0){ printf("Invalid Index\n"); } else if (idx == 0){ L->head = L->head->next; free(curr); } else { while (idx--){ prev = curr; curr = curr->next; } prev->next = curr->next; free(curr); } L->cnt--; printf("\t Delete Succeeded\n"); } void insert(list *L){ } void print_list(list *L){ if (L->cnt ==0){ printf("Empty\n"); return; } node *t=L->head; while(t){ printf("%d ", t-> data); t = t->next; } printf("\n"); } void clear_list(list *L){ while (L->head){ node *tmp = L->head; L->head = L->head->next; free(tmp); } free(L); } void reverse_list(list *L){ return; } void sort_list(list *L){ return; }으렵다
Uploaded by Notion2Tistory v1.1.0