[4] 리스트 ④ 이중 연결리스트 : 알고리즘

이중 연결리스트의 알고리즘 

이중 연결 리스트는 두 방향으로 연결되어 있다. 따라서 나와 연결된 다음 노드와 내 이전 노드를 알 수 있다. 따라서 역행하여 노드를 확인하거나 추가/수정에 용이하다.

 

이중 연결리스트는 next 구조체 포인터, pre 구조체 포인터 그리고 노드가 저장하는 데이터 값을 가지는Listnode(필자가 선언한 변수명) 구조체와 리스트의 헤드와 테일 노드 그리고 리스트의 크기를 저장하는 list_info(필자가 선언한 변수명)  구조체로 이루어진다.

 

이때 헤드노드와 엔드노는 더미데이터를 가지고 있는데 이는 데이터를 가지고 있지 않고 노드 정보만 가지고 있다는 뜻이다.

 

· head(머리 더미) = 데이터 없이 첫번째 노드를 가르킨다.

· tail(꼬리 더미) = 데이터 없이 꼬리 자신을 가르킨다.

 

이때 아래 코드를 확인하자.

list->head->pre = NULL;
list->head->next = list->tail;
list->tail->pre = list->head;
list->tail->next = NULL;
list->size = 0;

 

즉 head 와 tail에서 head 노드의 다음 노드는 list->head->next = list->tail; 를 통해 tail 노드를 가리키고 list->tail->next = NULL;에서 확인할 수 있듯 tail 노드의 next 값은 NULL값을 가리킨다.

 

이중 연결리스트의 순서도는 아래와 같다.

 

1. 연결리스트 구조체(Listnode , list_info) 생성하기
2. list_info 구조체를 참조하는 헤드노드와 테일 노드를 동적으로 생성

3. 헤드노드와 테일 노드의 next, pre 방향 설정 
4. 반복문을 수행하며 새로운 노드(new)를 생성
5. new을 head와 tail사이에 연결
6. new의 값을 업데이트
7. 연결리스트 ADT 수행

이중 연결리스트의 함수 : add 함수

add 함수의 기본 로직은 아래와 같다.

rank위치까지반복(curr)
-> curr은 새로 생성할 new의 다음 노드가 되어야함.: new->next = curr;
-> curr의 뒷 노드는 new의 뒷 노드가 되어야함: new->pre = curr->pre;
-> curr의 뒷 노드의 다음 노드는 new가 되어야함: (curr->pre)->next = new;
-> curr의 뒷 노드는 new가 되어야함: curr->pre = new;

 

① 삽입하고자 하는 위치 바로 앞까지 간다. (i < rank)

② 이때의 노드가 NULL이 아니라면, 이 노드를 임시로 생성(저장)한다. 이때의 노드를 curr라고 하자.

③ 새로운 노드를 동적할당하여 생성한다. 이때의 노드를 new라고 하자

④ new에 데이터를 담고, 이 노드의 next를 curr의 next로 저장한다.

⑤ new의 pre값을  curr의 pre값으로 지정한다.

⑥ 현재 노드의 이전값의 다음 노드를 new로 지정한다.

⑦ 현재 노드의 이전값을 new로 지정한다.

⑧ 리스트의 사이즈를 증가한다.

 

코드 순서는 아래 Table과 같다.

 

//생략 new->data = data; new->next = curr; new->pre = curr->pre; (curr->pre)->next = new; curr->pre = new; list->size++;

코드는 아래의 [코드 블럭] 란을 확인한다.

void add(list_info* list,int rank,char data)
{
	Listnode* curr = list->head;
	for (int i = 0; i < rank; i++) {curr = curr->next;}
	Listnode* new = (Listnode*)malloc(sizeof(Listnode)); //새로 추가할 노드
	
    new->data = data;
	new->next = curr;
	new->pre = curr->pre;
	(curr->pre)->next = new;
	curr->pre = new;
	list->size++;
}

이중 연결리스트의 함수 : delete 함수

delete 함수의 기본 로직은 아래와 같다.

 

① 삭제하고자 하는 노드 바로 앞까지 이동한다. (i < rank)

② 다음 노드가 NULL이 아니라면 이 노드를 임시로 저장한다. 이때의 노드를 del 라고 하자.

③ "지울노드의 이전 노드"의 다음 노드 방향에 "지울 노드의 다음 노드 방향"으로 지정한다.

④ "지울 노드의 다음 노드의 이전 노드 방향"을 "지울노드의 이전 노드 방향"으로 지정한다.

⑤ 리스트의 사이즈를 줄인다.

 

코드 순서는 아래 Table과 같다.

 

//생략 (del->pre)->next = del->next; (del->next)->pre = del->pre; list->size--;

코드는 아래의 [코드 블럭] 란을 확인한다.

void delete(list_info* list,int rank)
{
	Listnode* del = list->head;
	for (int i = 0; i < rank; i++) {del = del->next; }
	(del->pre)->next = del->next;
	(del->next)->pre = del->pre;
	list->size--;
}

이중 연결리스트의 함수 : get 함수

get 함수의 기본 로직은 아래와 같다.

 

① get(값 확인)하고자하는 하는 노드 바로 앞까지 이동한다. (i < rank)

② 다음 노드가 NULL이 아니라면 이 노드를 임시로 저장한다. 이때의 노드를 p 라고 하자.

③ p에 저장된 값을 출력한다.

 

코드는 아래의 [코드 블럭] 란을 확인한다.

void get(list_info* list,int rank) {
	Listnode* p = list->head;
	for (int i = 0; i < rank; i++) {
		p = p->next; // rank 위치의 노드로 이동
	}
	printf("%c", p->data);
}

 

이중 연결리스트의 함수 : print 함수

print 함수의 로직은 순회중 노드의 next값이 NULL이 아닐 때까지 반복하여 리스트에 저장된 값을 출력한다.

코드는 아래의 [더보기] 란을 확인한다.

void print(list_info* list) {
	Listnode* p = list->head->next;
	while (p != list->tail) { 
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}