chapter01 자료구조 리스트 (c언어)

1.1.1. 리스트의 개념

헤드 : 첫번째 노드

테일 : 마지막 노드

리스트의 길이 : 헤드부터 테일까지의 노드 개수

 

갖춰야할 연산 : Append(추가), Insert(삽입), Remove(제거), GetAt(반환)

 

1.1.2 리스트와 배열 비교

배열 : 배열의 크기를 지정해 줘야 하고 생성한 후에 그 크기를 변경할 수 없다.

리스트 : 배열 처럼 집합 보관 기능을 가지면서도 크기를 바꿀 수 있는 자료구조

 

1.2 링크드 리스트

구조

데이터	다음 노드를 가리키는 포인터

구현

노드를 표현하는 방법 : 구조체로 나타낼 수 있다.

#include <stdio.h>

typedef int ElementType;

struct Node{
  ElementType Data; //데이터
  struct Node* NextNode; //다음 노드포인터
}

ElementType이 int형인 노드를 가진 링크드 리스트 (나중에 필요한 자료형으로 바꿔도 되는 부분)

 

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

Node라는 별칭을 가진 노드 구조체를 선언하였다. 

 

인스턴스 생성

int main() {

  Node MyNode; 
  return 0;
}

 

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

첫번째 : 자료구조를 구축하기 위한 연산 - 노드 생성, 소멸, 추가, 삭제, 삽입

두번째 : 자료구조에 저장된 데이터를 활용하기 위한 연산 - 탐색

 

(노드소멸 : 메모리에서 노드를 없애는 연산

노드삭제 : 리스트에서 노드를 제외하는 연산)

 

링크드리스트의 노드는 자동메모리(스택)와 자유 저장소(힙) 둘 중 어느곳에 생성하는 곳이 좋을까?

자동 메모리에 생성하면 return문이 실행 된 후에 자동메모리에 의해 제거된다.

따라서 return값이 가리키는 주소에는 아무것도 남아있지 않게 된다. 따라서 자유저장소에 저장!

 

메모리를 할당하는 malloc()함수 : 할당한 메모리의 시작 주소를 반환하는 함수다.

즉 우리가 노드를 생성한 함수를 통해 반환 받는 것은 노드가 저장되어있는 주소! 

(그래서 앞으로는 포인터 파티가 열릴 예정, 당황하지 않아도 됨!

malloc()함수가 메모리의 시작 주소를 반환하기 때문에 어쩔 수 없다는 것만 알아 두면 된다~)

 

malloc 함수 사용

void *malloc(size_t size);

반환 타입 : void* 즉, 모든 타입의 메모리를 가리킬 수 있는 만능 포인터

malloc()의 매개변수는 size 하나 뿐이다. size는 malloc()이 할당해야 하는 메모리의 크기

sizeof연산자의 반환형이기도 한 size_t는 typedef로 선언한 unsined int의 별칭이다.

 

구조체의 size만큼 자유저장소에 메모리 생성

Node* NewNode = (Node*)malloc(sizeof(Node));

1. sizeof연산자가 측정한 노드 구조체의 크기만 한 메모리를 자유저장소에 확보

2. NewNode 포인터에 그 메모리 주소를 저장

 

SLL : Singly Linked List

노드 생성 연산(10번 보기)

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);
}

 

노드 추가 연산

SLL_CreateNode()함수를 이용하여 자유 저장소에 노드를 생성한 다음,

새로 생성한 노드의 주소를 테일의 NextNode 포인터에 저장하면 된다.

Node* 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;
  }
  
}

(함수에서 매개변수를 포인터로 하면 포인터가 가리키는 변수값을 직접 바꿀 수 있기 때문에 포인터로 매개변수를 받는다)

 

함수의 사용

int main() {
  Node* List=NULL;
  Node* NewNode = NULL;
  NewNode = SLL_CreateNode(117); // 자유저장소에 노드 생성
  SLL_AppendNode(&List, NewNode); // 생성한 노드를 list에 추가
  NewNode = SLL_CreateNode(119); // 자유저장소에 또 다른 노드 생성
  SLL_AppendNode(&List, NewNode); // 생성한 노드를 List에 추가
  return 0;
}

 

노드 탐색 연산

임의의 위치에 있는 노드를 찾아 반환하는 함수. 단, 배열과 달리 헤드부터 시작해서 노드의 개수만큼 거쳐야만 원하는 요소에 접근할 수 있다.

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

사용

int main() {
  Node* List=NULL;
  Node* MyNode = NULL;
  SLL_AppendNode(&List, SLL_CreateNode(117));
  SLL_AppendNode(&List, SLL_CreateNode(119));

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

 

노드 삭제 연산

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;
}// Current 노드는 탐색 연산으로 찾고 수행

노드 카운트 연산

int SLL_GetNodeCount(Node* Head){
  int Count = 0;
  Node* Current = Head;

  while (Current != NULL){
    Current = Current->NextNode;
    Count ++;
  }
  return Count;
}

 

1.3 더블 링크드 리스트

링크의 방향이 양방향

 

(링크드리스트와 구현이 비슷하여 일단 생략)

1.4 환형 링크드 리스트

더블링크드리스트와의 차이

• 테일은 헤드의 '이전 노드'이다
• 헤드는 테일의 '다음 노드' 이다

주요 연산 : 노드 추가, 노드 삭제

 

노드 추가연산

void CDLL_AppendNode(Node** Head, Node* NewNode){
  if((*Head) == NULL){
    *Head = NewNode;
    (*Head)->NextNode = *Head;
    (*Head)->PrevNode = *Head;
  }
  else {
    //테일과 헤드 사이에 NewNode 삽입
    Node* Tail = (*Head)->PrevNode;

    Tail->NextNode->PrevNode = NewNode;
    Tail->NextNode = NewNode;

    NewNode->NextNode = (*Head);
    NewNode->PreveNode = Tail;
  }
}

 

노드 삭제연산

Void CDLL_RemoveNode(Node** Head, Node* Remove){
  if (*Head ==Remove){
    (*Head)->PrevNode->NextNode = Remove->NextNode;
    (*Head)->NextNode->PrevNode = Remove->PrevNode;

    *Head = Remove->NextNode;

    Remove->PrevNode = NULL;
    Remove->NextNode = NULL;
  }
  else {
    Remove->PrevNode->NextNode = Remove->NextNode;
    Remove->NextNode->PrevNode = Remove->PrevNode;

    Remove->PrevNode = NULL;
    Remove->NextNode = NULL;
  }
}