[자료구조-리스트] 1. 링크드 리스트_코드

- 링크드 리스트의 주요 연산 - 

@ 노드 생성/소멸

# 세가지 종류의 메모리 영역
- 정적 메모리(Static Memory) : 전역 변수나 정적 변수등이 저장되는 곳
- 자동 메모리(Automatic Memory) : 지역 변수가 저장되는 곳
    [스택, 코드 블록안에서 생성및 소멸 됨]
- 자유 저장소(Free Store)
 => 중요!![가비지 컬렉터가 없다면 메모리 릭이 생길 수 있음]
 => 프로그래머가 직접 메모리를 관리하는 영역

# 자유 저장소 할당 함수

 void* malloc(size_t size);  

- void* 만능 포인터, 어떠한 형도 가르킬 수 있다.
- size_t는 typeof문을 이용하여 unsigned int의 별칭으로 선언되어 있음.


# 노드 생성 함수

 Node* SLL_CreateNode(ElementType NewData)  
 {  
      Node* NewNode=(Node*)malloc(sizeof(Node));  
      NewNode->Data = NewData;  
      NewNode->NextNode = NULL;  
      return NewNode;  
 }  

# 자유 저장소 소멸 함수

 void free(void *memblock);  

# 노드 소멸 함수

 void SLL_DestoryNode(Node* Node)  
 {  
      free(Node);  
 }  

@ 노드 추가

# 노드 추가 함수

 void SLL_AppendNode(Node** Head, Node* NewNode)  
 {  
      if((*Head)==Null)  
      {  
           *Head=NewNode;  
      }  
      else  
      {  
           Node* Tail=(*Head);  
           while(Tail->NextNode!=Null)  
           {  
                Tail=Tail->NextNode;  
           }  
           Tail->NextNode=NewNode;  
      }  
 }  

# 활용

 Node* List=NULL;  
 Node* NewNode = NULL;  
   
 NewNode = SLL_CreateNode(117);  
 SLL_AppendNode(&List, NewNode);  
   
 NewNode = SLL_CreateNode(118);  
 SLL_AppendNode(&List, NewNode);     

@ 노드 탐색
- 탐색 연산은 링크드 리스트가 갖고 있는 약점 중의 하나입니다.

# 탐색 함수

 Node* SLL_GetNodeAt(Node* Head, int Location)  
 {  
      Node* Current=Head;  
      int idx=0;  
      while(Current!=NULL&&(--Location)>=0)  
      {  
           Current=Current->NextNode;  
      }  
      return Current;  
 }  

#탐색 함수 사용

 Node* List=NULL;  
 Node* MyNode = NULL;  
   
 SLL_AppendNode(&List, SLL_CreateNode(117));  
 SLL_AppendNode(&List, SLL_CreateNode(117));   

 MyNode = SLL_GetNodeAt(List, 1);
 printf("%d\n",MyNode->Data);  

# 노드 삭제

 void SLL_RemoveNode(Node** Head, Node* Remove)  
 {  
      if(*Head == Remove)  
      {  
           *Head= Remove->NextNode;  
      }  
      else  
      {  
           Node* Current = *Head;  
           while(Current != NULL && Current->NextNode!=Remove)  
           {  
                Current= Current->NextNode;       
           }  
           if(Current != NULL)  
                Current->NextNode = Remove->NextNode;  
      }  
 }  

# 노드 삽입

 void SLL_InsertAfter(Node* Current, Node* NewNode)  
 {  
      NewNode->NextNode=Current->NextNode;  
      Current->NextNode - NewNode;  
 }  

# 노드 수 세기

 int SLL_GetNodeCount(Node* Head)  
 {  
      int Count = 0;  
      Node* Current = Head;  
      while(Current != NULL)  
      {  
           Current = Current->NextNode;  
           Count++;  
      }  
      return Count;  
 }  

# 전체 소스

 #include <stdio.h>  
 #include <stdlib.h>  
 typedef int ElementType;  
 typedef struct tagNode  
 {  
      ElementType Data;  
      struct tagNode* NextNode;  
 } Node;  
 Node* SLL_CreatedNode(ElementType NewData);  
 void SLL_DestroyNode(Node *Node);  
 void SLL_AppendNode(Node** Head, Node* NewNode);  
 void SLL_InsertAfter(Node* Current, Node* NewNode);  
 void SLL_InsertNewHead(Node** Head, Node* NewHead);  
 void SLL_RemoveNode(Node** Head, Node* Remove);  
 Node* SLL_GetNodeAt(Node* Head, int Location);  
 int SLL_GetNodeCount(Node* Head);  
  Node* SLL_CreateNode(ElementType NewData)   
  {   
    Node* NewNode=(Node*)malloc(sizeof(Node));   
    NewNode->Data = NewData;   
    NewNode->NextNode = NULL;   
    return NewNode;   
  }   
  void SLL_DestroyNode(Node* Node)   
  {   
    free(Node);   
  }   
  void SLL_AppendNode(Node** Head, Node* NewNode)   
  {   
    if((*Head)==NULL)   
    {   
       *Head=NewNode;   
    }   
    else   
    {   
       Node* Tail=(*Head);   
       while(Tail->NextNode!=NULL)   
       {   
         Tail=Tail->NextNode;   
       }   
       Tail->NextNode=NewNode;   
    }   
  }   
 void SLL_InsertAfter(Node* Current, Node* NewNode)  
 {  
      NewNode->NextNode = Current->NextNode;  
      Current->NextNode = NewNode;  
 }  
 void SLL_InsertNewHead(Node** Head, Node* NewHead)  
 {  
      if(*Head==NULL)  
      {  
           (*Head)=NewHead;  
      }  
      else  
      {  
           NewHead->NextNode=(*Head);  
           (*Head)=NewHead;  
      }  
 }  
 void SLL_RemoveNode(Node** Head, Node* Remove)  
 {  
      if(*Head == Remove)  
      {  
           *Head= Remove->NextNode;  
      }  
      else  
      {  
           Node* Current = *Head;  
           while(Current != NULL && Current->NextNode!=Remove)  
           {  
                Current= Current->NextNode;       
           }  
           if(Current != NULL)  
                Current->NextNode = Remove->NextNode;  
      }  
 }  
 /* 노드 탐색 */  
 Node* SLL_GetNodeAt(Node* Head, int Location)  
 {  
      Node* Current = Head;  
      while(Current!=NULL && (--Location)>=0)  
      {  
           Current = Current -> NextNode;  
      }  
      return Current;  
 }  
 int SLL_GetNodeCount(Node* Head)  
 {  
      int Count = 0;  
      Node* Current = Head;  
      while(Current != NULL)  
      {  
           Current = Current->NextNode;  
           Count++;  
      }  
      return Count;  
 }  
 int main(void)   
 {  
      int i=0;  
      int Count=0;  
      Node* List=NULL;  
      Node* Current=NULL;  
      Node* NewNode=NULL;  
      for(i=0;i<5;i++)  
      {  
           NewNode=SLL_CreateNode(i);  
           SLL_AppendNode(&List,NewNode);  
      }  
      NewNode = SLL_CreateNode(-1);  
      SLL_InsertNewHead(&List, NewNode);  
      NewNode = SLL_CreateNode(-2);  
      SLL_InsertNewHead(&List, NewNode);  
      Count=SLL_GetNodeCount(List);  
      for(i=0; i<Count; i++)  
      {  
           Current = SLL_GetNodeAt(List,i);  
           printf("List[%d] : %d\n",i,Current->Data);  
      }  
      printf("\nInserting 3000 After [2]...\n\n");  
      Current = SLL_GetNodeAt(List, 2);  
      NewNode = SLL_CreateNode(3000);  
      SLL_InsertAfter(Current, NewNode);  
      Count=SLL_GetNodeCount(List);  
      for(i=0; i<Count; i++)  
      {  
           Current = SLL_GetNodeAt(List,i);  
           printf("List[%d] : %d\n",i,Current->Data);  
      }  
      printf("\nDestroying List..\n");  
      for(i=0;i<Count;i++)  
      {  
           Current=SLL_GetNodeAt(List,0);  
           if(Current!=NULL)  
           {  
                SLL_RemoveNode(&List,Current);  
                SLL_DestroyNode(Current);  
           }  
      }  
      return 0;  
 }