정적 메모리 할당, 동적 메모리 할당

정적 메모리 할당 

- 메모리의 크기를 프로그램 시작하기 전에 결정

- 실행 도중에 크기를 변경할 수 없다.

- 더 큰 입력이 들어온다면 처리하지 못함

- 더 작은 입력이 들어온다면 메모리 공간 낭비 

 

동적 메모리 라이브러리 함수

- 실행 도중 메모리를 할당 받는 것

- 필요한 만큼만 할당 받고 반납한다. 

- 메모리를 효율적으로 사용가능 

- 동적으로 할당된 메모리는 반드시 포인터에 저장 → 삽입, 반납 용이

 

Linked Representation

- 노드를 통해 다음 주소포인터를 넣어주는 방법

- 노드는 <항목, 주소> 쌍으로 구성

- 구성: 데이터 필드 - 데이터의 값 저장하는 곳, 링크 필드 - 포인터  

- 장점: 노드 삽입, 삭제가 용이하다.(포인터만 끊으면 되니까) 연속된 메모리 공간이 필요없다. 크기 제한이 없다.  

  단점: 구현이 어렵다(구조 복잡). 오류가 발생하기 쉽다. 자주 발생시 속도를 느리게 한다. 

 

연결 리스트의 구조

- 헤드 포인터 : 리스트의 첫 번째 노드를 가리키는 변수 (반드시 존재해야 한다. )

- 마지막 포인터: null값 넣어 리스트의 끝을 알려준다.  

 

연결 리스트의 종류

- 단순 연결 리스트: 링크필드가 하나인 경우. 가장 기본적인 연결 리스트 형태

- 원형 연결 리스트: 마지막 노드가 헤드포인터를 가리키는 것

- 이중 연결 리스트: 링크 필드가 두개 존재. 다음 노드도 가리키고 이전 노드도 가리킨다. 메모리가 많이 필요. 

 

연결 리스트로 구현한 스택

· 삽입 연산 (malloc)

- 가장 마지막에 삽입된 노드가 헤드 포인터 top이 된다. 

void push(Element e)

{

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

  p->data = e; // top노드에 p값 할당

  p->link = top; // p의 포인터 할당  

  top = p; // top은 삽입된 p가 된다. 

 

· 삭제 연산()

- pop 하고 top을 그 전 노드에 할당 

- 꺼내기 전에 노드에 값이 있는지 없는 지 먼저 확인(is_empty)

- 마지막에 반드시 메모리 반납 해줘야 한다. free(p)

Element pop()

{

  Node* p;

  Element e;

  if (is_empty()) error("에러"); // 공백상태인지 체크

 

  p = top; // 노드 p가 top 가리키도록

  top = p->link; // top이 이전 노드 가리키도록 

 

  e = p->data; // top에 e 데이터 할당

  free(p); // 메모리 반납

  return e; 

}

 

· 전체 노드 방문 연산

- 개수 파악 

- top에서 시작 null이 나올때까지 개수 count

int size()

{

  Node *p;

  int count = 0;

  for (p = top; p != NULL; p = p->link ) 연산끝난 후 다음노드로 넘어가라

          count++;

  return count;

 

연결리스트로 구현한 큐

· 삽입 연산

- 공백상태에서 삽입: front와 rear가 공백(null)인 상태에서 시작

 

- 비공백 상태에서 삽입 시작: rear만 이동시킨다.  

 

· 삭제 연산

- 노드가 두 개 이상

 

- 노드가 하나인 경우