[Data Structure] 연결리스트 Linked List

🌟 동적 데이터 구조

정적 데이터 구조란 🧍‍♂️

• 충분한 메모리가 할당 -> 메모리의 낭비 발생

동적 데이터 구조란 🏃‍♂️

• 프로그래밍 실행 중에 메모리가 커지거나 작아짐

• 필요에 따라 할당되고 반환

반드시 연속적인 공간에 저장될 필요가 없음 -> 포인터를 이용해 데이터 연결

---

🌟 동적 메모리 할당

• stdlib.h 헤더파일 사용

• 포인터 = malloc(크기)

• 성공하면 메모리 주소 반환, 실패하면 NULL 반환

사용법 📚

// 함수를 활용해 node 동적으로 생성하기
#include<stdio.h>
#include<stdlib.h>	// 동적메모리 할당을 위한 헤더파일
typedef int ELEMENT;
typedef struct node{
    ELEMENT data;
    struct node *next;	// 주소를 저장
}NODE;	// NODE라는 구조체 생성
NODE *createNode( ELEMENT data );
void printAll( NODE *ptr );
int main(){
    NODE *head;
    head = createNode( 10 );
    printAll( head );      
}
NODE *createNode( ELEMENT data ){
    NODE *new = (NODE *)malloc( sizeof(NODE) );
    new->data = data;
    new->next = NULL;
	  return new;
}
void printAll( NODE *ptr ){
    while( ptr ){	// NULL을 만날 때까지
        printf("%d\n", ptr->data);
        ptr = ptr->next;
    }
}

---

🌟 연결리스트 Linked List

리스트의 개념란 🤷‍♂️

순서에 따라 차례대로 저장하는 자료 구조

단순 연결 리스트란 🤷‍♂️

데이터와 포인터로 구성된 노드가 이어진 것

한 노드의 포인터가 다음 노드의 주소를 가짐

사용법 📚

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

typedef struct listNode{
   char data[4];
   struct listNode *link;
}listNode;

typedef struct {
   listNode * head;
}linkedList_h;

// 공백 연결 리스트를 생성
linkedList_h *createLinkedList_h();
// 연결 리스트의 전체 메모리를 해제하는 연산
void freeLinkedList_h(linkedList_h* L);
// 연결 리스트를 순서대로 출력하는 연산
void printList(linkedList_h *L);
// 첫번째 노드로 삽입하는 연산
void insertFirstNode(linkedList_h *L, char *x);
// 노드를 pre 뒤에 삽입하는 연산
void insertMiddleNode( linkedList_h *L, listNode *pre, char *x);
// 마지막에 노드를 삽입하는 연산
void insertLastNode( linkedList_h *L, char *x);
// 리스트에서 x 노드를 탐색하기( page173, 175 )
linkedList_h *searchNode(linkedList_h *L, char *x);
int main(){
   linkedList_h * L;
   listNode * p;

   printf("(1) 공백리스트 생성하기! \n");
   L = createLinkedList_h();
   printList( L );
   
   printf("(2) 리스트 처음에 [수]노드 삽입하기! \n");
   insertFirstNode( L, "수");
   printList( L );
   
   printf("(3) 리스트 마지막에 [금]노드 삽입하기! \n");
   insertLastNode( L, "금");
   printList( L );
   
   printf("(4) 리스트 첫 번째에 [월]노드 삽입하기! \n");
   insertFirstNode( L, "월");
   printList( L );
   
   printf("(5) 리스트에서 [수] 노드를 찾아 그 뒤에 [목] 삽입하기! \n");
   p = searchNode( L, "수");
   if( p == NULL ) printf("찾는 데이터가 없습니다.\n");
   else    insertMiddleNode( L, p, "목");
   printList( L );
   
   printf("(6) 리스트 공간을 해제하여 공백 리스트로 만들기! \n");
   freeLinkedList_h(L);
   printList( L );
   return 0;
}
// 공백 연결 리스트를 생성
linkedList_h *createLinkedList_h(){
   linkedList_h* L;
   L = (linkedList_h*)malloc(sizeof(linkedList_h));
   L -> head = NULL;	// head 생성
   return L;
}

// 연결 리스트의 전체 메모리를 해제하는 연산
void freeLinkedList_h(linkedList_h* L){
   listNode* p;
   while (L -> head != NULL) {
      p = L -> head;
      L -> head = L -> head -> link;
      free(p);
      p = NULL;
   }
}

// 연결 리스트를 순서대로 출력하는 연산
void printList(linkedList_h *L){
   listNode* p;
   printf ("L = (");
   p = L -> head;
   while (p != NULL) {	// 끝까지
      printf ("%s", p -> data);
      p = p -> link;
      if (p != NULL) printf (", ");
   }
   printf (") \n");
}

// 첫번째 노드로 삽입하는 연산
void insertFirstNode(linkedList_h *L, char *x){
   listNode* newnode;
   newnode = (listNode*)malloc(sizeof(listNode));
   strcpy(newnode -> data, x);	// x를 newnode의 data로 복사
   newnode -> link = L -> head;
   L -> head = newnode;
}

// 노드를 pre 뒤에 삽입하는 연산
void insertMiddleNode( linkedList_h *L, listNode *pre, char *x){
   listNode* newNode;
   newNode = (listNode*)malloc(sizeof(listNode));
   strcpy(newNode -> data, x);
   if (L->head == NULL) {
      newNode -> link = NULL;
      L -> head = newNode;
   }
   else if (pre == NULL) {
      L -> head = newNode;
   }
   else {
      newNode -> link = pre -> link;
      pre -> link = newNode;
   }
}
void insertLastNode( linkedList_h *L, char *x){
   listNode* newNode;
   listNode* temp;
   newNode = (listNode*)malloc(sizeof(listNode));
   strcpy(newNode -> data, x);
   if (L -> head == NULL) {
      L -> head = newNode;
      return;
   }
   
   temp = L -> head;
   while (temp -> link != NULL) temp = temp -> link;
   temp -> link = newNode;
}   

linkedList_h *searchNode(linkedList_h *L, char *x){
   listNode *temp;
   temp = L -> head;
   while (temp != NULL) {
      if (strcmp(temp -> data, x) == 0) return temp;
      else temp = temp -> link;
   }
   return temp;
}

---

당신의 시간이 헛되지 않는 글이 되겠습니다.
I'll write something that won't waste your time.