Week1_ Review

1. 이중연결리스트를 이용한 영문자 리스트 ADT

 

<4가지 연산>

-add(L, r, e): list의 순위 r에 원소 e 추가

-delete(L, r): list의 순위 r에 위치한 원소 삭제

-get(L, r): list의 순위 r에 있는 원소 반환

-print(L): list의 모든 원소를 출력

*순위 정보가 유효하지 않으면 "invalid position" 출력, 해당 연산 무시

 

->연산 이름은 각각 A, D, G, P 로 주어짐.

 

---

 

STEP1 [자료구조 선언]

 - 일단 "구조체"가 필요해요! 이 구조체를 왜 만드냐구요?

 

'노드 하나가 담을 원소(영문자)',

'이전 노드를 가리키는 링크', 

'다음 노드를 가리키는 링크'

 

이 3가지 정보를 포함할 노드의 구조로 구조체가 가장 적절해보이네요~

 

혹시 typedef 가 뭐였는지 잊으셨나요? 구조체 선언 복습하고 오기~

https://dojang.io/mod/page/view.php?id=409

typedef struct node {
    struct node* prev; //이전 노드를 가리키는 노드
    char elem;  //원소
    struct node* next; //다음 노드를 가리키는 노드

}node;

 => 이제 이 노드들이 포함된 하나의 '리스트'를 만들어보아요~ 어떻게? 또 구조체로!

 

*우리가 만들 연결리스트는 헤더 및 트레일러 노드가 있어요!! 이 노드들은 데이터를 가지지 않는 특별한 노드들입니다!

 

typedef strcuct list{
    node *head;  //헤더 노드
    int position; //총 노드 개수
    node *tail;  //트레일러 노드
}list;

 

STEP2 [연산 함수 만들기]

**본격적으로 리스트를 만들기 전에 꼭 해야 할 것이 있어요! 그건 바로 리스트 초기화!!!!

거의 모든 자료구조(연결리스트, 트리 등등)는 삽입이나 삭제 같은 연산을 하기 전에 초기화하는 작업이 필요해요~

 

1) 리스트 초기화하기

 

1. 헤더 노드, 트레일러 노드 각각 선언해주고 동적할당~

 

2. 1에서 만들어준 헤더를 리스트의 헤더 위치에 연결! 헤더 노드도 이전 노드 링크와 다음 노드 링크가 있겠죠? 

헤더 노드는 리스트의 가장 맨 앞 노드니까(이 노드의 이전 노드는 존재하지 않으므로) header->prev = NULL; 이 됩니다.

다음 노드 링크는 어떻게 될까요? 

우리가 만든 리스트는 아직까지 "헤더랑 트레일러 노드"밖에 없으니까, 헤더 다음 노드는 트레일러 노드네요! 

그러니까 header->next = header;

 

3. 1에서 만들어준 트레일러도 2처럼 리스트의 트레일러 위치에 연결해주고, 이전 노드 링크와 다음 노드 링크를 처리해주세요!

 

4. 마지막으로 잊지 말기!! 헤더, 트레일러 노드 이렇게 노드 2개가 리스트에 있으니까 L->position = 2; 가 되겠네요!

void init(list *L){
    node *header, *tailer;
    header = (node*)malloc(sizeof(node));
    tailer = (node*)malloc(sizeof(node));        ///1
    
    L->head = header;
    header->prev = NULL;
    header->next = tailer;   ///2
    
    L->tail = tailer;
    tailer->prev = header;
    tailer->next = NULL;    ///3
    
    L->position = 2;       ///4
}

 

2) add함수 만들기

 

1. 필요한 변수들 선언

2. 순위와 문자 입력받기 -> 입력받은 순위가 유효하지 않은 경우

3. 임시 노드 생성 + 리스트의 헤드에 연결, 이 임시 노드를 입력받은 순위(자리)로 이동이동~~

4. 새 노드 생성 + 동적할당 후 요소에 입력받은 문자 삽입

5. 노드들 앞뒤를 서로 연결

6. 노드 add했으므로 잊지 말고 노드 개수++

 

**헷갈리는 포인트 정리!!!

 Q1. 2에서 (p->position)-1 < r 이 무슨 뜻인가요??

 A1. 예를 들어 지금 총 노드 개수 5개라고 해봅시다. (헤더 노드, S, t, r, 트레일러 노드 이렇게 5개!)

만약에 r = 3을 입력받으면, 우리는 5-1=4 > 3 이니까 순위 정보는 유효하죠! (순위가 유효하네! = 그 순위에 노드 있네!)

But.... r = 5 를 입력받으면, 5-1=4 < 5 이므로 "invalid position"을 출력하게 되네요.

 

또다른 예를 들어볼까요? 현재 총 노드 개수가 2개, 헤더 노드와 트레일러 노드밖에 없다고 해봅시다.

만약 r = 1을 입력받으면, 2-1=1 = 1 이므로 순위가 유효하네요.

 

아 그니까 (p->position)-1 의 의미가 뭐냐고요 (p->position)-1 은 노드 '사이'를 의미합니다.

노드가 5개면(헤더, 트레일러 포함) 노드 '사이'는 4개가 있네요. 아래 표에서 초록색 체크 표시!! 새로운 노드를 이미 있던 노드들 사이에 집어넣을 건데, 존재하지도 않는 곳에 집어넣을 순 없겠죠? 예를 들어 트레일러 노드 다음 같은..

 

 

Q2. 5번 과정(노드 서로 연결)이 헷갈려요..

 A2. 자, 차근차근 하나씩 살펴봅시다. 

아래처럼 리스트에 S, t, r이 이미 삽입된 리스트에서, 'r' 자리에 'a'를 삽입하는 상황이라고 해봐요.

	r=1	2	3
[ 헤더 ]	S	t	r	[트레일러]

새로 생성한 노드(newnode)(ex)요소가 'a'인 노드)도 당연히 이전 링크랑 다음 링크가 있을거예요!

이전 링크

a

다음 링크

새 노드의 이전 링크(prev)는 어디에다 연결하죠? 맞아요!

1) '입력받은 순위에 원래 있던' 노드(tmp) 친구('r')의 '이전 노드'('t')와 연결해주는 작업이 필요해요.  ex) t-a

 

2) 새 노드의 다음 링크(next)는요? '입력받은 순위에 원래 있던' 노드('r')와 연결해주세요!  ex) a-r

 

이제 끝인가요? 아니죠!!

3) '입력받은 순위의 노드'의 이전 노드(t)의 다음 링크(next),

4) '입력받은 순위의 노드'(r)의 이전 링크(prev)가 모두 newnode를 향하도록 해주면 진짜 끝!!!

   

void add(list *L){
    int i, r;
    char ch;     ///1
    
    scanf("%d %d",&r,&ch);
    getchar();
    if((L->position)-1 < r){
             printf("invalid position\n");
             return;
    }    ///2
    
    node *tmp;
    tmp = L->head;  
    
    for(i=0; i<r; i++)
         tmp = tmp->next;  ///3 
    
    node *newnode = (node*)malloc(sizeof(node));
    newnode->elem = ch;  ///4
    
    newnode->next = tmp;
    newnode->prev = tmp->prev;
    tmp->prev->next = newnode;
    tmp->prev = newnode;    ///5
    
    (L->position)++;   ///6
 }

 

3) del 함수 만들기

 

삭제 연산은 삽입 연산보다 좀더 간단해요!

 

1. 삭제할 위치 정보 입력받기

2. 헤더, 트레일러 제외 노드들 개수( =(L->position)-2 )가 1의 위치값보다 작은 경우 "invalid position" 출력

3. 임시 노드 선언 후 리스트의 헤더에 연결 + 삭제할 노드까지 tmp 이동시키기

4. 삭제할 노드의 '이전 노드'와 '다음 노드' 연결시키는 작업!! + 메모리 해제까지

5. 노드 개수 -1

void del(list *L){
    int i, order;
    scanf("%d", &order);
    getchar();       ///1
    
    if((L->position)-2< order){
          printf("invalid position\n");
          return;
    }               ///2
    
    node *tmp;
    tmp = L->head;
    for(i=0; i<order; i++) tmp = tmp->next;        ///3
    
    tmp->prev->next = tmp->next;
    tmp->next->prev = tmp->prev;
    free(tmp);     ///4
    
    (L->position)--;       ///5

 

4) get_entry 함수 만들기

1. 탐색할 위치 정보 입력받기

2. 헤더, 트레일러 제외 노드들 개수( =(L->position)-2 )가 1의 위치값보다 작은 경우 "invalid position" 출력

3. 임시 노드 선언 후 리스트의 헤더에 연결 + 탐색할 노드까지 tmp 이동시키기

4. 탐색한 노드 출력

void get_entry(list *L){

    int i, num;
    scanf("%d", &num);
    getchar();       ///1
    
    if((L->position)-2 <num){
       printf("invalid position\n");
       return;
    }              ///2
    
    node *tmp;
    tmp = L->head;
    for(i=0;i<num;i++) tmp=tmp->next;    ///3
    
    printf("%c\n", tmp->elem);   ///4
    
  }

4) print함수 만들기

1. 임시 노드 tmp 선언하여 리스트의 헤더와 연결

2. 헤더, 트레일러 제외하고 노드의 elem 출력

  **이때 헤더 다음 노드부터 출력하기 위해 처음 반복문 시작할 때(i=0일 때) tmp = tmp->next 로 시작.

void print(list *L){
    int i;
    node*tmp=L->head; //1
    
    for(int i; i<(L->position)-2); i++){
          tmp = tmp->next; //head 다음부터 시작 
          printf("%c",tmp->elem);
    }     
    printf("\n"); //2
    
 }

 

STEP3 [메인함수 구성]

 

1. 리스트 선언

2. 리스트 초기화

3. 연산 횟수 n 입력받기

4. n번 동안 연산

int main() {
	list* L = (list*)malloc(sizeof(list));
	init(L);

	int i,r,n;
	char ch;

	scanf("%d", &n);
	getchar();
	for (i = 0; i < n; i++) {
		scanf("%c", &ch);
		getchar();
		
		if (ch == 'A') {
			add(L);
			continue;
		}
		else if (ch == 'D') {
			del(L);
			continue;
		}
		else if (ch == 'G') {
			get_entry(L);
			continue;
		}
		else {
			print(L);
			continue;
		}
	}
	
	return 0;
}

후~~ 쉽지 않았다. 연결리스트는 역시 백번 말로 코드로 공부하는 것보다 혼자 손으로 그림 그려보면서 알고리즘 확인하는게 최선의.. 확실한 방법인 거 같네요! 코드가 길어 보이지만 함수끼리 비슷한 코드가 많아서 금방 외울 수 있을 거예요! 화이팅~~