[자료구조] 연결 리스트

리스트의 개념

• 리스트
  • 물품이나 사람의 이름 따위를 일정한 순서로 적어 놓은 것
  • 어떤 정의에 의해서 결정된 논리적인 순서의 나열
  • 리스트의 순서는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되고 어떤 정의에 의해서 결정된 논리적인 순서, 혹은 리스트에 나타나는 원소들 간의 의미적인 순서를 의미함
• 배열
  • 인덱스로 표현되는 추상적 순서가 원소의 메모리 공간(메인 메모리, DDR)의 물리적인 위치와 일치함
  • 배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서

배열을 이용한 리스트의 구현

배열의 확장

초기 배열 선언에서 충분히 크게 하면 어느 정도는 배열의 추가 확장을 피할 수 있겠지만(메모리 낭비), 원소를 리스트의 중간에 삽입하기 위해서는 리스트의 원소값을 하나씩 뒤로 밀어야 하는 상황이 발생함(연산 시간의 증가)

배열을 이용한 리스트의 원소 삽입/삭제

• 배열로 구현된 리스트는 원소의 순서가 연속적인 물리적 주소에 저장됨
  • 원소를 삽입하거나 삭제하기 위해서는 해당 원소의 위치 뒤에 있는 모든 원소를 뒤로 물리거나 앞으로 당겨야만 됨
  • 리스트 원소값의 이동은 원소수가 많을수록 프로그램의 수행시간을 증가시킴
• 리스트의 원소 삽입은 프로그램의 실행 중에 메모리 할당을 필요로 하는 경우도 발생시킴
• 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있음
• 자료의 삽입과 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발함

포인터를 이용한 리스트의 구현

• 노드(node): 리스트의 원소값(데이터) + 다음 원소를 가리키는 정보(포인터)
• 노드는 데이터 요소(원소값)와 리스트의 다음 노드를 지시하는 포인터(주소, 링크(link))로 구성됨

포인터 변수

리스트의 생성: 정수값 data와 링크 link로 구성된 노드의 생성

struct linked_list_node {
    int data;
    struct linked_list_node* link;
};

연결 리스트의 삽입과 삭제

• 노드의 삭제
  • 삭제할 노드의 선행 노드의 링크 필드를 삭제할 노드의 후행 노드를 가리키게 한다.
  • 삭제할 노드를 메모리에 반환한다.
• 노드의 삽입
  • 메모리 공간을 할당받고 삽입할 내용을 저장하여 삽입할 x 노드를 생성합니다.
  • x 노드의 링크 부분이 후행 노드가 될 j 노드를 가리키게 합니다.
  • 삽입될 x 노드의 선행 노드가 될 i 노드의 링크 필드가 x 노드를 가리키게 합니다.

연결 리스트의 여러 가지 연산

연결 리스트의 생성

typedef struct ListNode { // 단순 연결 리스트의 노드 구조 정의
    int data;
    struct ListNode* link;
} listNode;

typedef struct { // 리스트의 헤드(fist) 노드 구조 정의
    listNode* head;
} linkedList_h

linkedList_h* createdLinkedList_h(void) { // 연결리스트 생성
    linkedList_h* H;
    H = (linkedList_h*)malloc(sizeof(linkedList_h));
    H -> head = Null;
    return H;
}

노드 삽입

void addNode(linkedList_h* H, int x) {
    // 리스트 마지막 노드에 삽입 연산하며, x값은 100이라고 가정함
    listNode* NewNode;
    listNode* LastNode;
    NewNode = (listNode*)malloc(sizeof(listNode));
    NewNode -> data = x;
    NewNode -> link = NULL;

    if(H -> head == NULL) { // 현재 리스트가 공백인 경우
        H -> head = NewNode;
        return;
    }
    LastNode = H -> head;
    while(LastNode -> link != NULL) LastNode = LastNode -> link;
    LastNode -> link = NewNode;
}

void additNode(linkedList_h* H, listNode* prevNode, int itdata) {
    // 리스트 중간에 노드를 삽입하는 연산이며, itdata값은 150이라고 가정함
    listNode* NewNode;
    NewNode = (listNode*)malloc(sizeof(listNode));
    NewNode -> data = itdata;
    NewNode -> link = NULL;

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

노드 삭제

void deleteNode(linkedList_h* H) { // 리스트 마지막 노드 삭제
    listNode* prevNode;
    listNode* delNode;
    if(H -> head == NULL) return; // 공백 리스트인 경우, 삭제 연산 중단
    if(H -> head -> link == NULL) { // 리스트에 노드가 한 개인 경우
        free(H -> head); // 첫 번째 노드의 메모리를 해제
        H -> head = NULL;
        return;
    }
    else { // 리스트에 노드가 여러 개 있는 경우
        prevNode = H -> head;
        delNode = H -> head -> link;
        while(delNode -> link != NULL) {
            prevNode = delNode;
            delNode = delNode -> link;
        }
        free(delNode);
        prevNode -> link = NULL;
    }
}

void findandDeleteNode(linkedList_h* H, int itdata) {
    // 연결 리스트에서 특정 노드를 검색하여 삭제하고자 하는 연산, itdata=200
    listNode* prevNode;
    listNode* delNode;

    if(H -> head == NULL) return; // 공백 리스트
    prevNode = H;
    delNode = H -> head;

    while(delNode != NULL) {
        if(delNode -> data == itdata) {
            deleteNode(H, prevNode, delNode);
            return;
        }
        else {
            prevNode = delNode;
            delNode = delNode -> link;
        }
    }
}

void deleteitNode(linkedList_h* H, listNode* prevNode, listNode* delNode) {
        // 연결 리스트에서 데이터의 값이 200인 노드(delNode)를 삭제하는 연산
    prevNode -> link = delNode -> link;
    free(delNode);
    return;
}

연결 리스트의 변형

• 단순 연결 리스트의 문제점: 하나의 링크만 있고, 각각의 노드의 링크는 후행 노드만을 가리키는 구조 → 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점이 발생함
• 이중 연결 리스트: 선행 노드를 가리키는 링크와 후행 노드를 가리키는 링크를 가짐 → 특정 노드에서 선행 노드와 후행 노드에 직접적으로(간단한 프로그램 코드를 통해) 접근할 수 있음
• 원형 연결 리스트: 연결 리스트를 살펴보면, 가장 마지막 노드의 링크 필드는 언제나 ‘NULL’ 값임
  • 리스트의 마지막 원소 뒤에는 아무 원소도 없기 때문에 연결 리스트의 마지막 노드의 링크 필드는 언제나 NULL 값임
  • 그래서 마지막 노드의 링크 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 원형 연결 리스트가 제안됨

원형 연결 리스트

연결리스트의 마지막 노드의 링크 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 원형 연결 리스트가 제안됨

원형 연결 리스트의 생성

typedef struct ListNode { // 원형 연결 리스트의 노드 구조 정의
	int data;
	struct ListNode* link;
} listNode;

typedef struct { // 원형 연결 리스트의 **헤드 노드** 구조 정의
	listNode* head;
} linkedList_h;

linkedList_h* createLinkedList_h(void) { // 원형 연결 리스트의 헤드 노드 생성
	linkedList_h* H;
	H = (linkedList_h*)malloc(sizeof(linkedList_h));
	H -> head = NULL;
	return H:
}

원형 연결 리스트의 노드 삽입

void addFirstNode(linkedList_h* H, int x) {
// 원형 리스트 첫 번째 노드 삽입 연산, x값은 100이라고 가정함
	listNode* tempNode;
	listNode* NewNode;
	NewNode = (listNode*)malloc(sizeof(listNode));
	NewNode -> data = x;
	NewNode -> link = NULL;

	if(H->head == NULL) { // 현재 원형 연결 리스트가 공백인 경우
		H -> head = NewNode;
		NewNode -> link = NewNode;
		return;
	} else { // 현재 원형 연결 리스트가 공백이 아닌 경우
		tempNode = H -> head;
		
		while(tempNode -> link != H -> head) tempNode = tempNode -> link;
	
		NewNode -> link = tempNode -> link;
		tempNode -> link = NewNode;
		H -> head = NewNode;
	}
}

void addMiddleNode(linkedList_h* H, listNode* prevNode, int itdata) {
// 원형 리스트 중간 노드로 삽입 연산, itdata 값은 110이라고 가정함
	listNode* NewNode;
	NewNode = (listNode*)malloc(sizeof(listNode));
	NewNode -> data = itdata;
	NewNode -> link = NULL;
		
	NewNode -> link = prevNode -> link;
	prevNode -> link = NewNode;
	return;
}

원형 연결 리스트의 삭제 노드 탐색

void finddelCircularNode(linkedList_h* H, int itdata) {
	//원형 연결 리스트에서 삭제하려는 노드를 탐색하는 연산
	// itdata 값은 90이라고 가정함
	listNode* tempNode;
	listNode* prevNode;
	prevNode = H;
	
	if(H -> head == NULL) { // 공백인 경우
		printf("Circular Linked List is EMPTY");
		return;
	} else {
		tempNode = H -> head; // 첫 번쨰 노드부터 검색하기 위함
		do {
			if(tempNode -> data == itdata) { // 찾는 노드값 검색
				return deleteCircularNode(H, prevNode); 
				// 찾았다면 삭제 함수 호출하며 검색 함수는 끝
			} else {
				prevNode = tempNode;
				tempNode = tempNode -> link;
			}
		} while(tempNode != H -> head);
	}
	// 마지막 노드가 검색했는데 없는 경우라면
	printf("Search Fail"); // 검색 실패 메시지 출력
	return;
}

원형 연결 리스트의 노드 삭제

void deleteCircularNode(linkedList_h* H, listNode* prevNode) {
	// 원형 연결 리스트에서 데이터의 값이 90인 노드를 삭제하려는 연산
	listNode* lastNode;
	listNode* delNode;

	lastNode = H -> head;

	while(lastNode -> link != H -> head) lastNode = lastNode -> link;
	
	delNode = prevNode -> link;
	prevNode -> link = delNode -> link;

	if(delNode == H -> head) lastNode -> link = H -> head;
	free(delNode);
}

이중 연결 리스트

단순 연결 리스트는 어떤 노드를 찾았을 경우, 그 특정 노드의 후행 노드는 쉽게 찾을 수 있었지만, 어떤 특정노드의 선행 노드를 찾으려면 복잡한 방법이 필요함

이중 연결 리스트의 노드 구조

• 양쪽 방향으로 순회할 수 있도록 링크 필드가 두 개 필요함 → 시작점(head)도 두 개의 링크(Lhead, Fhead)가 필요
• 이중 연결 리스트의 노드 구조: 두 개의 링크 필드(Llink, Rlink)와 한 개의 데이터 필드

이중 연결 리스트의 정의 및 생성

typedef struct ListNode {
// 이중 연결 리스트의 노드 구조 정의
	struct ListNode* Llink;
	int data;
	struct ListNode* Rlink;
} listNode;

typedef struct { // 이중 연결 리스트의 헤드 노드 구조 정의
	listNode* Lhead;
	listNode* Fhead;
} linkedList_h;

linkedList_h* createLinkedList_h(void) {
	// 원형 연결 리스트의 헤드 노드 생성
	linkedList_h* H;

	H = (linkedList_h*)malloc(sizeof(linkedList_h));
	H -> Lhead = NULL;
	H -> Fhead = NULL;
	return H;
}

이중 연결 리스트의 노드 삽입

void addDNode(linkedList_h* H, listNode* prevNode, int x) {
	// 이중 연결 리스트 노드 삽입 연산, x 값은 200이라고 가정함
	listNode* NewNode;
	NewNode = (lintNode*)malloc(sizeof(listNode));
	NewNode -> Llink = NULL;
	NewNode -> data = x;
	NewNode -> Rlink = NULL;

	NewNode -> Rlink = prevNode -> Rlink;
	prevNode -> Rlink = NewNode;
	NewNode -> Llink = prevNode;
	NewNode -> Rlink -> Llink = NewNode;
}

이중 연결 리스트의 특정 노드 삭제

void deleteDNode(linkedList_h* H, listNode* delNode) {
	// 이중 연력 리스트에서 데이터의 값이 300인 노드(delNode)를 삭제하는 연산
	delNode -> Llink -> Rlink = delNode -> Rlink;
	delNode -> Rlink -> Llink = delNode -> Llink;
	free(delNode)
}