연결 데이터 표현(포인터, 연결리스트)

포인터 -> Java에는 존재하지 않는 개념

 

• 포인터의 정의
  - 포인터 변수는 다른 변수의 주소를 가지고 있음
  
  
• 사용되는 연산자
  - & : 변수의 주소는 & 연산자를 변수에 적용시켜 추출할 수 있음
  - * : 포인터 변수가 가리키는 메모리의 내용을 추출하거나 변경할 때 사용

* 포인터에 대한 연산

int A[6], int *p;

p = &A[3], A = [10, 15, 20, 22, 26, 28]

- p : A[3]의 주소, 포인터를 의미

- *p : 22, 포인터가 가리키는 값

- *p++ : 22를 출력 후 p는 A[4]의 주소를 기억

- *p-- : 22를 출력 후 p는 A[2]의 주소를 기억

 

 

 

 

동적 메모리 할당 -> Java의 new 연산자

 

- 동적 메모리 할당은 프로그램에서 필요한 만큼의 메모리를 시스템으로부터 할당 받아서 사용하고, 사용이 끝나면 시스템에 메모리를 반납
- 정적 메모리 할당은 프로그램이 시작되기 전에 미리 정해진 크기의 메모리를 할당 받는 것으로 메모리 크기가 미리 결정되면 프로그램 실행 중간에 크기가 변경될 수 없음
- 정적 메모리 할당은 간단하게 메모리를 할당할 수 있지만 경우에 따라 비효율적

 

* void *malloc(int size) : size 바이트만큼의 메모리 블록을 할당, 새로운 메모리 블록의 시작 주소를 반환

* void free(void *ptr) : 동적으로 할당되었던 메모리 블록을 반납

* sizeof 연산자 : 변수나 타입의 크기를 숫자로 반환한 것

 

 

 

 

연결리스트

 

 

• 연결리스트의 정의
  - 선형리스트의 논리적인 순서와 메모리내의 물리적인 순서가 일정하지 않음 (기억공간에 독립적)
  - 각 노드는 링크 부분을 가지며, 이 링크 부분에 그 노드와 관련성이 있는 다른 노드의 주소를 기억시켜 리스트를 구성
  - 임의의 위치에 있는 노드를 삭제하거 삽입할 때 데이터들이 대이동이 일어나지 않아 유용
  - 검색을 위한 접근시간은 느림
  
  
• 단순 연결리스트
  - 외부 단편화가 발생하지 않아 기억공간의 효율성이 좋음
  - 포인터만큼의 기억공간의 낭비가 발생
  - 탐색은 시작 노드부터 시작되어야 하며, 탐색시간은 포인터를 이용하여 순차적으로 따라가야 하므로 O(n)
  - 노드를 삽입, 삭제하는 경우 선행 노드를 알아야만 가능

 

 ▶︎ 삽입 연산
before 노드와 after 노드 중간에 new 노드를 삽입한다고 가정

insert_node(L, before, new)
if L = NULL //연결리스트 L이 공백이면
	then L <- new //새로운 노드를 첫번째로
    else new.link <- before.link //after 노드를 new 노드 뒤에
    	before.link <- new //new 노드를 before 노드 뒤에
// *after 노드를 가리키는 포인터가 before.link에 저장되어 있음

 

▶︎ 삭제 연산

반대로 new 노드를 삭제한다고 가정

remove_node(L, before, new)
if L <> NULL
    then before.link <- new.link //after 노드를 before 뒤에 연결
    destroy(new)

 

• 원형 연결리스트
  - 연결리스트의 마지막 원소의 연결 부분에 null이 아니라 첫 노드의 주소를 연결
  - 한 방향으로 모든 노드가 원형으로 연결되어 있기 때문에 한 노드에서부터 다른 어떤 노드로도 접근할 수 있음
  - 헤더를 두지 않는 경우 무한 루프에 빠질 수 있으므로 주의

 

• 이중 연결리스트
  - 하나의 노드에 forward와 backward의 위치를 나타내는 2개의 포인터를 가지고 있기 때문에 서로 반대 방향으로 선행할 수 있음
  - 임의 노드의 포인터가 파괴되었을 때 복구 가능
  - 2개의 포인터에 의한 메모리 낭비가 많이 발생

 

▶︎ 삽입 연산

노드 new_node를 before 노드 오른쪽에 삽입한다고 가정

void dinsert_node(DlistNode *before, DlistNode *new_node)
{
new_node -> left = before; //new_node의 left에 노드 before의 주소 저장
new_node -> right = before -> right; //new_node의 right에 노드 before의 right의 값을 저장
before -> right -> left = new_node; //before의 right 노드의 left에 new_node의 주소 저장
before -> right = new_node; //before의 right에 새로운 노드 new_node의 주소 저장
}

 

▶︎ 삭제 연산

반대로 new_node를 삭제한다고 가정

void dremove_node(DlistNode *before, DlistNode *new_node)
{
if(new_node == before) return;
new_node -> left -> right = new_node -> right; //new_node의 right를 new_node의 왼쪽 노드의 right에 저장
new_node -> right -> left = new_node -> left; //new_node의 left를 new_node의 오른쪽 노드의 left로 저장
free(new_node);
}