이전 글 CPU 스케줄링 프로그램 구현을 위해 자료구조의 이중 연결 리스트를 활용해야 한다는 사실을 알게되었다.
내 생각과 다르게 스케줄링을 구현하는 것이 이렇게 어려웠나 싶었다..
그래도 앞으로의 발전을 위해 거부감없이 다 공부할 것이다!
이중 연결 리스트는 말 그대로 리스트인데 이중으로 연결되어 있는 리스트를 의미한다.
이중 연결 리스트를 알기 전 단순 연결 리스트도 알 필요가 있다.
단순 연결 리스트와, 이중 연결 리스트의 간단한 정의를 알아보자!
단순 연결 리스트(Singly Linked List)
- 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료 구조
- 동적 메모리 할당을 받아 노드를 저장하고, 노드는 레퍼런스를 이용하여 다음 노드를 단 방향으로 가리키도록 만들어 노드들을 한 줄로 연결 시킴
이중 연결 리스트(Doubly Linked List)
- 하나의 노드에서 두 개의 링크를 갖게 되는데 선행 노드와 후속 노드에 주소를 각각의 링크에 연결시켜 양방향 검색이 가능하게끔 하는 리스트
- 기존의 단순 연결 리스트의 단점인 단방향 흐름을 2개의 링크 필드를 이용하여 양 방향으로 움직일 수 있게 만든 것
CPU 스케줄링을 표현하기 위해서 앞 노드와, 뒤 노드의 정보를 알 필요성이 있다.
이중 연결 리스트의 노드 정보는 다음과 같다.
말 그대로 data의 양쪽으로 Left link(왼쪽 노드)과 Right link(오른쪽 노드) 정보가 필요하다.
우리는 이 Left link와 data와 Right link를 합쳐 노드라고 부른다.
가볍게 이중 연결 리스트 정의와, 초기화, 삽입/삭제/해제 과정을 코드로 작성하겠다!
이중 연결 리스트 정의
typedef int element; // element 형은 자유롭게 지정
typedef struct DListNode {
struct DListNode* llink; // 왼쪽 링크
struct DListNode* rlink; // 오른쪽 링크
element data;
}DListNode; // 구조체 별칭을 DListNode로
이중 연결 리스트 초기화
void init(DListNode* head)
{
// 헤드의 양쪽 링크는 자기 자신으로...(원형 링크 연결)
head->rlink = head;
head->llink = head;
}
int main()
{
// malloc() 함수: 요청한 크기의 메모리를 동적으로 할당하여 반환해 줌, 메모리 크기 전달 필요
DListNode* head = (DListNode*)malloc(sizeof(DListNode)); // 헤드 노드(메모리 할당)
init(head);
}
이중 연결 리스트 삽입
void dinsert(DListNode* prev, element data) { // 이전(왼쪽) 노드 정보와 element
DListNode *new = (DListNode*)malloc(sizeof(DListNode)); // 노드 생성
new->data = data; // data 삽입
new->rlink = prev->rlink; // 이전(왼쪽) 노드가 가리켰던 rlink를 새로운 노드가 가리킴
new->llink = prev; // 새로운 노드의 llink를 prev로
prev->rlink->llink = new; // 이전 노드가 가리킨 rlink의 llink를 new로
prev->rlink = new; // 이전 노드의 rlink를 새로운 노드로...
}
위 과정을 거치면 새로운 노드가 생성되고 양쪽 노드 사이에 위치하며 정보 등록이 완료된다.
이중 연결 리스트 삭제
void ddelete(DListNode* head, DListNode* removed) {
if (removed == head) return; // 삭제할 노드가 헤드 노드라면 함수 종료(헤드 노드를 종료하면 안 됨!)
else {
removed->llink->rlink = removed->rlink; // 삭제할 노드의 llink의 rlink 정보를 삭제할 노드의 rlink로
removed->rlink->llink = removed->llink; // 삭제할 노드의 rilnk의 llink 정보를 삭제할 노드의 llink로
free(removed); // 메모리 해제
}
}
전체 메모리 해제
void free_node(DListNode* head) {
DListNode* p = head->rlink; // p 노드를 head 노드의 rlink로 설정
DListNode* next; // next 노드 정의
while (p != head) { // 헤드 노드가 아닐 때까지 반복
next = p->rlink; // next 노드를 p의 rlink로 설정
free(p); // p 노드 메모리 해제
p = next; // next 노드를 p 노드로... -> 한 칸씩 오른쪽으로 이동되며 메모리 해제
}
}
이상으로 이중 연결 리스트의 간단한 정의와 필요한 정보(노드, link 등)을 정리해 보았다!
자료구조를 처음 접해보는 나로서 되게 막막했지만, 하나씩 익혀보니 그렇게 어려운 내용은 아니다 라고 생각이 들었다...(그렇게 합리화 중...)
그래도 모르는 내용을 익혀가니 뿌듯하면서 발전한 느낌이 들었다
이중 연결 리스트를 활용해서 CPU 알고리즘을 다시 수정하여 작성해 나가야겠다!