배열 & 단순 연결 리스트

신동화·2020년 12월 14일

단순 연결 리스트 배열 연결 리스트

배열

데이터를 순차적으로 입력시키며, 물리적 주소 또한 순차적이다.
배열의 크기는 처음에 결정되고, 변경이 불가능하다.
크기가 고정적이고 인덱스를 가지고 있어, 검색속도가 빠르다.
삽입/삭제 작업이 번거롭다.(배열 중간에 삽입할 경우, 모든 값을 이동시켜야 하고 배열이 꽉 찼을 경우, 메모리 재 할당이 필요함)

연결 리스트

원소들 간의 논리적 순서를 위한 자료구조
원소들 간의 순서는 논리적으로 지켜지며, 물리적 위치는 상관하지 않는다.
메모리 할당/해제를 통해 유연한 크기변경이 가능하다.
할당된 인덱스는 없으며, 위치를 기억하고 있다.
특정 데이터에 접근하기 위해 연결된 위치들을 따라서 접근해야 하기 때문에 검색 속도가 느리다.
삽입, 삭제 시 리스트의 위치만 변경하기 때문에 속도가 빠르다.
일반적으로 포인터 변수를 이용하여 연결 리스트를 구성한다.

<리스트 예시>

단순 연결 리스트 구현

연결 리스트 생성

typedef struct listNode {	// Node 구조 정의
	int data[10];	// 데이터 공간
	struct listNode* link;	// 다음 노드를 가리키기 위한 변수
} listNode;

typedef struct {	// 헤드노드 구조 정의(첫 번째 노드를 가리키는 역할)
	listNode* head;
} headNode;
 
headNode createLinkedList(void) {	// 연결 리스트 생성(헤드노드 하나를 생성하여 반환)
	headNode* H;
	H = (headNode*)malloc(sizeof(headNode*));
	H -> head = NULL;
	return head;
}

리스트의 마지막에 노드 추가

void addNode(headNode* H, int x) {	// 노드 추가
	listNode* newNode;
	listNode* lastNode;
	newNode = (listNode*)malloc(sizeof(listNode));
	newNode -> data = x;
	newNode -> link = NULL;
 
	if(H -> head == NULL) {	// 현재 리스트가 공백인 경우
		H -> head = newNode; // H가 가리키는 헤드노드가 추가된 노드를 가리킨다.
		return;
	}
 
	lastNode = H -> head;
	while(lastNode -> link != NULL) lastNode = lastNode -> link; // 마지막 노드 찾기
	lastNode -> link = newNode; // 마지막 노드에 추가된 노드 연결
}

리스트의 마지막 노드 삭제

void deleteNode(headNode* H) {	// 마지막 노드 삭제 연산
	listNode* prevNode;
	listNode* delNode;
	if(H -> head == NULL) return;	// 빈 리스트인 경우 삭제할 노드가 없으므로 종료
	if(H -> head -> link == NULL) {	// 리스트에 노드가 한 개인 경우
		free(H -> head);	// 메모리 해제 후 리턴
		H -> head = NULL;
		return;
	}
	else {	//리스트에 노드가 2개 이상인 경우
		prevNode = H -> head;
		delNode = H -> head -> link;
		while(delNode -> link != NULL) {
			prevNode = delNode;
			delNode = delNode -> link;
	}
		free(delNode);
		prevNode -> link = NULL;
	}
}

특정 노드 뒤에 삽입

// 삽입할 선행 노드(prevNode)에 대한 포인터를 매개변수로 받아서 처리
void addItNode(headNode* H, listNode* prevNode, int x) {
	listNode* newNode;
	newNode = (listNode*)malloc(sizeof(listNode));
	newNode -> data = x;
	newNode -> link = NULL;

	newNode -> link = prevNode -> link;
	prevNode -> link = newNode;
	return;
}

특정 노드 삭제

// 삭제할 노드(delNode)와 선행 노드(prevNode)를 받아서 처리
void deleteItNode(headNode* H, listNode* prevNode, listNode* delNode) {
	prevNode -> link = delNode -> link;
	free(delNode);
	return;
}

특정 노드 검색

void searchNode(headNode* H, int x) {	//데이터 필드 값이 x인 노드 검색
	listNode* tempNode;
	tempNode = H -> head;

	while(tempNode -> data != x) {
		tempNode = tempNode -> link;
	}
 
	printf("Search Successful.\n");
}