#29 [C 자료구조] 연결 리스트 연결 및 역순 만들기

오늘은 연결 리스트를 연결하고 또 이의 역순을 만드는 방법을 배워볼 것이다. 내가 배워야 한다.

문득 든 생각인데, 파이썬 할 때는 자료구조는 생각지도 않고 그저 알고리즘만 생각했다. 그러나 c언어를 공부하면서 배우는 자료형 공부도 끝이 없는 것 같다. 쉽게 클래스로 쉽게 쉽게 해결했던 것들이, 사실은 기본적이고 필수적인 프로그래밍의 기초였던 것이다.

뭐, 어쨌건 우리는 공부를 이어나가야 한다.

연결 리스트끼리 연결하기

 

1) 연결 리스트 스트럭쳐 만들기

typedef struct listNode listPointer;
typedef struct listNode {
	int data;
    listPointer *link;
}

이제는 눈감고도 만들 수 있는 연결 리스트 스트럭쳐

 

 

2)  두 개의 연결 리스트 세트를 만들고 이어 붙이기

listPointer* concatenate(listPointer *ptr1, listPointer *ptr2){
	listPointer *temp;
    if ( !ptr1 )
    	return ptr2;
    if ( !ptr2 )
    	return ptr1;
    for ( temp = ptr1; temp->link; temp = temp ->link ); // temp를 ptr1의 끝으로 이동
    	temp -> link = ptr2; //ptr2를 연결함
        return ptr1;
}

---

 

 

 

연결 리스트 역순 만들기 1

연결 리스트를 반대의 방향성으로 돌리는 것! 어렵지 않다. 지금까지 와 마찬가지로 temp와 while 문 등을 이용해서 리스트의 역순을 만들 수 있다.

처음엔 두 개의 새 노드를 이용해 바꿔보자.

시작해보자.

 

1) 연결 리스트 스트럭쳐 만들기

typedef struct listNode listPointer;
typedef struct listNode {
	int data;
    listPointer *link;
}

이제는 눈감고도 만들 수 있는 연결 리스트 스트럭쳐2222

 

2) 역순 만드는 함수 만들기

listPointer* invert(listPointer *lead){
	listPointer *middle, *tail; // 이 두 노드를 통해 역순으로 바꿀 것이다.
    middle = NULL; 
    
    while (lead) {
    	trail = middle; // 트레일은 미들을 따라감
        middle = lead; // 미들은 리드를 따라감 (첫 노드부터 시작)
        lead = lead -> link; // 리드는 자신의 뒷 노드를 따라감
        middle -> link = trail; // 미들은 트레일을 가리킴
    }
    return middl;
}

while문이 도는 구조를 그대로 시각화하면 다음과 같다.

첫 while문 돌 때

 

두 번째 while 문

세 번째 while 문

네 번째 while 문, lead = NULL

처음 볼 때는 순서가 헷갈릴 수 있는데 lead << middle << trail 이렇게 순서대로 따라가면서 링크를 바꿔준다고 생각하면서 잘 이해해보자. 다음은 다른 예시이다.

 

 

연결 리스트 역순 만들기 2

이 번엔 3개의 노드를 사용하여 역순 만드는 방식이다.

좀 더 직관적이고 쉽다.

 

1) 연결 리스트 스트럭쳐 만들기

typedef struct listNode NODE;
typedef struct listNode {
	int data;
    NODE *link;
}

이번엔 기존에 것을 head노드라 해보자

2) 세 노드로 역순 만드는 while 함수 구성

listPointer* invert(NODE *head){
	listPointer *current, *next, *previous // 이 두 노드를 통해 역순으로 바꿀 것이다.
    current = head; //첫 노드를 가리킴
    next = previous = NULL;
    
    while (current) {
    	next = current -> link; // next는 current의 다음 것
        current -> link = previous; // current의 링크는 previous를 가리킴
        previous = current; // previous는 current의 노드를 가리킴
        current = next; // current는 next노드를 가리킴
    }
    head = previous; //역전 시켜줌
    return head;
}

첫 while 문 실행 후

두 번째 while 문

세 번째 while 문

 

4번째 회문

여기서는 current와 next값 둘 다 NULL이 되고 previous만 마지막 노드를 가리킨다.

 

오늘은 여기 까지! 당분간 포스팅을 멈추고 쉬어야겠다. 뜨어엉. 왜냐하면

ㅎ