[자료구조-리스트] 2. 더블 링크드 리스트_개념

@ 더블 링크드 리스트

 - 더블 링크드 리스트는(Doubly Linked List)는 링크드 리스트의 탐색 기능을 개서난 자료구조 입니다.( 양방향 검색 가능)

 # 노드 구성

포인터 (이전 노드)

데이터

포인터 (다음 노드)

- 앞뒤로 노드 이동이 가능

# C언어로 표현하는 더블 링크드 리스트의 노드

- 노드 구조체

 typedef struct tagNode
 {  
      int Data;  
      struct Node* NextNode;  
 }  

- 노드 구조체 방식 1[선언]

 struct Node MyNode;  

- 노드 구조체 방식 2 [정의]

 typedof struct tagNode  
 {  
      int Data;  
      struct tagNode* NextNode;  
 } Node;  

- 노드 구조체 방식 2 [선언]

 Node MyNode;  

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

[자료구조-리스트] 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;  
 }  

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

# 리스트 특징

- 배열과 달리 유연하게 크기를 바꿀 수 있는 자료 구조

- 리스트는 스택과 큐, 그리고 트리와 같은 자료구조를 이해할 수 있는 기반이 된다

@ 링크드 리스트

 - 링크드 리스는 리스트를 구현하는 여러 가지 기법 중에서도 가장 간단한 방법으로 꼽히는 자료구조입니다.

 # 노드(Node) : 리스트 내의 각요소

 - 노드를 연결해서 만드는 리스트를 링크드 리스트라고 합니다.

 # 노드 구성

데이터	포인터 (다음 노드)

- 데이터와 포인터로 이루어진 노드들을 연결시켜놓으면 링크드 리스트가 됩니다.

- 첫번째 노드를 헤드라하고 마지막 노드를 테일이라고 합니다.

# C언어로 표현하는 링크드 리스트의 노드

- 링크드 리스트의 노드는 C언어로 표현하면 다음과 같은 구조체로 나타낼 수 있습니다.

- 노드 구조체 방식 1[정의]

 struct Node  
 {  
      int Data;  
      struct Node* NextNode;  
 }  

- 노드 구조체 방식 1[선언]

 struct Node MyNode;  

- 노드 구조체 방식 2 [정의]

 typeof struct tagNode  
 {  
      int Data;  
      struct tagNode* NextNode;  
 } Node;  

- 노드 구조체 방식 2 [선언]

 Node MyNode;  

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

- 노드 생성/소멸
- 노드 추가
- 노드 탐색
- 노드 삭제
- 노드 삽입

# 링크드 리스트 단점

- 다음 노드를 가리키려는 포인터 때문에 각 노드마다 4byte의 메모리가 추가로 필요합니다.
- 특정 위치에 있는 노드를 얻는데 드는 비용이 크며 속도도 느립니다.

# 링크드 리스트 장점

- 새로운 노드의 추가/삽입/삭제가 쉽고 빠릅니다. 배열은 요소를 삽입하거나 제거하기가 어렵습니다.
- 현재 노드의 다음 노드를 얻어오는 연산에 대해서는 비용이 발생하지 않습니다.