본문 바로가기

Datastructure/[4] 리스트

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

728x90
반응형

이중 연결리스트의 ADT

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

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

 

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

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

udangtangtang-cording-oldcast1e.tistory.com

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

이중 연결리스트의 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;
}
728x90
반응형
댓글