연결구조, 연결리스트, 단일 연결리스트

연결리스트(linked list)

 

연결리스트 자료구조가 생기게 된 배경

선형리스트(ordered list)의 구현

원소들간의 논리적 관계가 순차적으로 인접해 있는 자료구조의 배열을 이용한 구현함

배열의 적합성	- 주기억장치의 물리적인 구조가 인접되게 구성됨 - 순차적인 기억장소의 표현은 임의의 원소를 탐색하거나 스택이나 큐를 사용할 경우 자료의 삽입/삭제 등의 작업에 효율적임
배열의 부적합성	- 여러 개의 선형리스트를 사용하는 경우 각 리스트를 최대 크기의 배열(선언문에 의해서 고정된 기억장소를 유지)에 저장해야 하기 때문에 기억장소의 낭비를 초래할 수 있음 - 순차적인 기억장소 표현이 선형리스트에 적용되면 삽입/삭제 시 자료이동에 따른 처리시간의 비효율성이 발생함

 

연결리스트 자료구조의 특징

순차 자료구조에서의 연산시산과 저장공간에 대한 문제를 개선하여 자료를 표현한 방법 - 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조를 말함

• 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식임 (비순차적 저장(기억장소의 어느곳에서든지)이 가능함
• 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음
• 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현함
• 크기의 변경이 유연하고 더 효율적으로 메모리를 사용할 수 있음
• 순차적인 기억장소의 표현에서 발생하는 이동에 따른 연산 소요시간을 해결할 수 있음

 

배열 구조와 연결리스트 구조의 표현

배열 구조	- 계산주소방법에 의해 배열 원소의 위치를 파악할 수 있음 - 순차적인 원소간의 관계에 대한 정보가 필요 없음
연결리스트 구조	- 순차 리스트의 원소를 찾기 위해 다음 원소에 대한 정보가 필요함(포인터 변수 이용, 추가 기억공간 요구) - 배열(임의처리, 직접처리)과 달리 임의의 원소를 처리하지 못하기 때문에 처음부터 연결을 따라 추적해야함(시간소요) - 포인터를 사용함으로써 노드의 삽입/삭제가 용이함 - 연속적인 기억공간이 없어도 저장이 가능함 - 알고리즘 구현(프로그램 복잡성)이 복잡함 - 노드 탐색 시 무한반복에 빠질 수 있음

 

연결리스트의 표현

데이터와 연결(link) 정보를 저장하기 위한 기억공간이 필요함

• 데이터 값 - 항목이 n개인 데이터 필드(1 < i < n) - 원소값을 저장 - 저장할 원소의 형태에 따라 하나 이상의 필드로 구성 가능
• 연결 값 - 항목이 n개의 연결 필드(1 < i < n) - 다음 노드의 주소를 저장하고 포인터 변수를 사용하여 주소 값을 저장, 하나 이상의 연결로 구성할 수 있음

논리적 표현

선형리스트와 연결리스트 구조의 물리적 저장 방법

- 요일 리스트 : week = (월,화,수,목,금,토,일)

물리적 저장 방법

 

동적 기억장소의 할당/해제

 

동적 기억장소의 할당

 

동적 기억장소 할당 함수 - malloc()

- 배열의 문제점을 해결

• 각 자료 원소는 서로 인접해 있지 않고 기억장소 내에서 어디든지 흩어져 존재함
• 삽입/삭제 시 원소 이동이 없음
• 포인터를 이용하여 노드를 동적으로 생성하므로 기억장소를 미리 확보할 필요 없음
• 기억장소의 크기는 일정한 크기로 제한되어 있기 때문에 malloc() 함수를 사용하여 동적 기억장소를 무한히 할당하여 사용하지는 못함

- 함수 원형 - void * malloc(size_t size);

• 동적 기억장소로 사용되는 힙(heap)으로부터 원하는 크기의 바이트를 할당 해주는 함수(<alloc.h>)
• 정상적으로 기억장소를 할당하는 경우에는 기억장소의 주소를 반환하고 비정상적인 경우에는 NULL을 반환함

int *pt;
pt = (int *) malloc(10);
pt = (int *) malloc(15*sizeof(int)); // 15개의 int를 위한 기억 장소를
// 할당해 그 시작 주소값을 반환함

 

동적 기억장소의 해제

 

동적 기억장소의 해제 함수 - free()

- 함수 원형 - void free(void *) : 할당된 기억 장소를 해제하여 힙(heap)에 반환함(<alloc.h>)

동적 기억장소의 할당과 해제의 구현

- malloc ()와 free () 함수를 사용한 프로그램

 

GitHub - dlfrnaos19/algorithm_with_c: learning algorithm

 

자유 공간리스트(free space list)

사용하기 전의 메모리나 사용이 끝난 메모리를 관리하기 위해 노드로 구성하여 연결한 리스트(리스트가 다 소모되어 없을 때는 malloc()을 사용)를 말함

자유 공간리스트

노드의 할당과 반환 알고리즘

자유 공간리스트 알고리즘

자유 공간리스트 새로운 노드 할당 과정

자유 공간리스트 반환 과정

 

단일 연결리스트

 

연결리스트 자료구조의 종류

• 단일 연결리스트
• 환형 연결리스트
• 이중 연결리스트
• 이중 환형 연결리스트

단일 연결리스트의 구조

노드가 하나의 연결 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결리스트를 의미함

• 노드 구조 - 데이터 필드와 1개의 연결 필드로 구성됨
• 자료 탐색은 한 방향으로만 진행

단일 연결리스트 구조

단일 연결리스트 ADT

ADT Linkedlist
데이터
0개 이상의 노드를 가진 유한순서 리스트(Element는 데이터 값)
연산자 및 연산내용 // L∈Linkedlist, n∈node, p∈position,
linkedlist() //연결리스트를 생성
~linkedlist() //연결리스트를 소멸
Element search(L, n) //연결리스트에서 주어진 노드 n을 탐색
Linkedlist insert(L, n) //연결리스트에 주어진 노드 n을 삽입
int remove(L, n) //연결리스트에서 주어진 노드 n을 삭제
remove_all(L) //연결리스트의 모든 노드를 삭제
position get_data(L, p) //p가 가리키는 현재 노드의 데이터를 출력
position get_nextnode(L, p) //p가 가리키는 현재 노드의 다음 노드를 출력
Element display() //연결리스트의 모든 노드를 출력
End Linkedlist

 

노드의 구현

구조체를 이용

구조체 노드

구조체 항목을 참조하는 방법

• 멤버 접근 연산자 - 각 멤버의 형태가 다르므로 멤버참조연산자(.)로 직접 멤버를 참조해야 함(배열은 배열요소의 형태가 같으므로 주소계산에 의해 각 멤버의 참조가 가능)
• 직접참조연산자(.), 간접참조연산자(->)
• struct list node(단순 구조체 변수), struct list *nodeptr(포인터형 구조체 변수);
• node.data = "100";
• nodeptr -> data = "100";
• (*nodeptr).data = "100"; // 구조체 포인터를 역참조한 뒤 .으로 멤버에 접근

 

GitHub - dlfrnaos19/algorithm_with_c: learning algorithm

 

단일 연결리스트의 노드 탐색

 

노드의 탐색 알고리즘

노드의 삽입/삭제 시 특정 노드를 찾고자 할 때 리스트의 노드를 처음부터 하나씩 순회하면서 노드의 데이터 필드 값과 x(찾고자 하는 노드)를 비교하여 일치하는 노드를 찾을 필요가 있음

searchNode(L, x){
temp = L; //최초 노드를 가리키기 위한 초기화
	while (temp != NULL){ //temp가 NULL이면 찾는 원소가 없음
		if (temp->data == x) return temp;
			temp = temp->link;
	}
	return temp;
}

노드의 탐색

노드의 삽입

첫 번째 노드로 삽입하는 알고리즘

insertFirstNode(L, x){
new = getNode(); //ⓐ 자유 공간리스트에서 새로운 노드 공간을 할당
new->data = x; //ⓑ 새 노드의 데이터 필드에 x를 저장
new->link = L; //ⓒ
L = new; //ⓓ}

노드 삽입

중간 노드(pre가 가리키는 다음 노드)로 삽입하는 알고리즘

insertMiddleNode(L, pre, x){
	new = getNode();
	new->data = x;
	if (L == NULL){ //ⓐ L이 공백 리스트인 경우
		L = new; // ⓑ
		new->link = NULL; //ⓒ
	}
	else{ // L이 공백 리스트가 아닌 경우
		pre = L; //ⓓ
		new->link = pre->link; //ⓔ
		pre->link = new; //ⓕ}
}

노드 삽입

노드의 삽입

노드의 삽입

 

노드의 삭제

포인터 pre가 가리키는 노드의 다음 노드를 삭제하는 알고리즘

deleteNode(L, pre){
	if (L == NULL) error;
	else{
		old = pre->link; //ⓐ
		if (old == NULL) return;
		pre->link = old->link; //ⓑ}
	return Node(old);
}

노드 삭제

노드의 생성과 출력 구현

단일 연결리스트의 생성과 노드들의 출력 프로그램

GitHub - dlfrnaos19/algorithm_with_c: learning algorithm