[4] 리스트 ⑥ 이중 연결리스트 : ADT

이중 연결리스트의 ADT

이중 연결리스트의 ADT에 포함된 함수와 설명은 아래 링크를 참조한다.

https://udangtangtang-cording-oldcast1e.tistory.com/232

[5] 리스트 ② 이중 연결리스트 : 알고리즘

해당 포스팅에서 각 함수의 로직과 방향 지정에 대해 이해하기 쉽도록 포스팅을 진행했다.

이중 연결리스트의 ADT 구현

<자료구조 실습> - 연결리스트 (1)

※ 입출력에 대한 안내는 아래의 [더 보기] 란을 확인한다.

- 특별한 언급이 없으면 문제의 조건에 맞지 않는 입력은 입력되지 않는다고 가정하라. - 특별한 언급이 없으면, 각 줄의 맨 앞과 맨 뒤에는 공백을 출력하지 않는다.
- 출력 예시에서 □는 각 줄의 맨 앞과 맨 뒤에 출력되는 공백을 의미한다.
- 입출력 예시에서 ↦ 이후는 각 입력과 출력에 대한 설명이다.

 

연결리스트 1주 차 : 연결리스트의 응용 1 - 리스트 구현

이중연결리스트 + 헤더 및 트레일러 노드(문제 1 참고 내용)

 

1. 연결리스트 구조

• 각 노드에 저장되는 정보
• elem: 원소
• prev: 이전 노드를 가리키는 링크 - next: 다음 노드를 가리키는 링크

2. 이중연결리스트 초기화
◦ 초기에는 헤더 및 트레일러 노드만 존재 ◦ O(1) 시간 소요

 

3. 이중연결리스트 순회

◦ 연결리스트의 모든 원소들을 방문
◦ 순회하면서 필요한 작업 수행(예를 들면 출력) ◦ O(n) 시간 소요

 

4. 이중연결리스트에서 삽입

◦ 이중연결리스트의 지정된 순위 r에 원소 e를 삽입

 

5. 이중연결리스트에서 삭제
◦ 이중연결리스트로부터 지정된 순위 r의 노드를 삭제하고, 원소를 반환 ◦ O(n) 시간 소요

 

[ 문제 1 ] 위에서 설명한 이중연결리스트를 이용하여 영문자 리스트 ADT를 구현하시오.

• 다음 네 가지 연산을 지원해야 함 (순위는 1부터 시작한다고 가정) - delete(list, r) : list의 순위 r에 위치한 원소를 삭제한다 (주교재의 remove와 동일) - print(list) : list의 모든 원소를 저장 순위대로 공백없이 출력한다. 을 무시한다.
• ※ 순위 정보가 유효하지 않으면 화면에 에러 메시지 "invalid position" 출력하고, 해당 연산
• - get(list, r) : list의 순위 r에 위치한 원소를 반환한다.
• - add(list, r, e) : list의 순위 r에 원소 e를 추가한다.
• 입력에 대한 설명 (아래 입출력 예시 참조)
  • 각 연산의 내용이 한 줄에 한 개씩 입력되고, 한 개의 줄에는 연산의 종류, 순위, 원소 순 서로 입력된다.
  • 연산의 종류: 연산 이름의 맨 앞 영문자가 대문자 A, D, G, P로 주어진다.
  • 순위: 양의 정수
  • 원소: 영문자(대문자, 소문자 모두 가능)

코드 예시

5 A 1 S A 2 t A 3 r A 3 a P	Star
9 A 1 D A 2 a A 3 Y D 1  P G 3  A 1 S P G 3	ay invalid position Say y

이중 연결리스트 ADT의 코드

#include <stdio.h>
#include <stdlib.h>
/*
실행 가능 확인 24.03.27
*/
typedef struct Node {
    //연결리스트 본체: 가지고 있는 데이터 값과 전/후방 연결위치 저장
	int data;
	struct Node* next;
	struct Node* pre;
}Listnode;

typedef struct list {
    //리스트의 정보 :  리스트의 헤드노드와 테일 노드의 설정 구조체
	int size;
	Listnode* head;
	Listnode* tail;
}list_info;

void add(list_info* list,int rank,char data)
{
	Listnode* curr = list->head;
	for (int i = 0; i < rank; i++) {
        /*
        rank위치까지반복(curr) 
        -> curr은 새로 생성할 new의 다음 노드가 되어야함.: new->next = curr;
        -> curr의 뒷 노드는 new의 뒷 노드가 되어야함: new->pre = curr->pre;
        -> curr의 뒷 노드의 다음 노드는 new가 되어야함: (curr->pre)->next = new;
        -> curr의 뒷 노드는 new가 되어야함: curr->pre = new;
        */
		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++;

}

void delete(list_info* list,int rank)
{
	Listnode* del = list->head;
	for (int i = 0; i < rank; i++) {
		del = del->next; // rank의 위치까지 반복
	}
    /*
    1. "지울 노드의 뒷 노드"의 다음 노드는 "지울 노드의 다음 노드"가 되어야함.
    2. " '지울 노드의 다음 노드'의 '뒷 노드'"는 "지울 노드의 이전 노드"가 되어야함
    */
	(del->pre)->next = del->next;
	(del->next)->pre = del->pre;
	list->size--;
}

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);
}

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

int main()
{
	list_info* list = (list_info*)malloc(sizeof(list_info));
	list->head = (Listnode*)malloc(sizeof(Listnode));
	list->tail = (Listnode*)malloc(sizeof(Listnode));
	list->head->pre = NULL;
	list->head->next = list->tail;
	list->tail->pre = list->head;
	list->tail->next = NULL;
	list->size = 0;

	int n;
	scanf("%d",&n);getchar();

	char operator ;
	for (int i = 0; i < n; i++) {
		scanf("%c", &operator);
		if (operator=='A') {
			int r;char data;
			scanf("%d %c", &r, &data);getchar();
			if ((r > list->size + 1) || (r < 1)) {printf("invalid position\n");}
            else add(list,r, data);
		}
		else if (operator=='D') {
			int r;
			scanf("%d", &r);getchar();
			if ((r > list->size) || (r < 1)) {printf("invalid position\n");}
			else delete(list, r);
		}
		else if (operator=='G') {
			int r;
			scanf("%d", &r); getchar();
			if (r > list->size) {printf("invalid position\n");}
			else get(list, r);
		}
		else if (operator=='P') {
			getchar();
			print(list);
		}
	}
	return 0;
}