[데이터 구조] 10차시 연결 데이터 표현

티스토리 뷰

전공 깍두기/데이터 구조 조각

[데이터 구조] 10차시 연결 데이터 표현 | 단순 연결 리스트 (2)

최삐뚤빼뚤씨 2024. 4. 19. 00:33

1. 단순 연결 리스트의 구체적 구현(C Implementation)

1) 리스트 생성 알고리즘

2) 원소를 첫 번째 노드로 삽입

3) 노드의 삽입

- 주어진 리스트 L에서 원소 값이 x인 노드를 p가 가리키는 노드 다음에 삽입

- 코드로도 확인해보자

insertNode(L, p, x)
	// 리스트 L에서, p 노드 다음에 원소 x를 삽입
    // p가 null인 경우는, 현재 pointing하는 노드가 없는 경우임
    
    newNode <- getNode();	// 공백 노드를 newNode가 지시
    newNode.data <- x;	// 원소 값 x를 저장
    
    if (L=null) then {	// (a) L이 공백 리스트인 경우
    	L <- newNode;	// newNode 포인터의 노드가 L의 첫 노드가 됨
        newNode.link <- null;
    }
    else if(p=null) then {	// (b) p가 null일 때는 L의 앞에 삽입
        newNode.link <- L;	// newNode 다음에 L을 위치시키고
        L <- newNode;	// L을 앞에 있는 newNode쪽으로 이동
    }
    else { // (c) 드디어, p가 가리키는 노드의 다음 노드로 삽입
    	newNode.link <- p.link;
        p.link <- newNode;
    }
end insertNode()

4) 리스트 L의 마지막에 노드 x를 삽입하는 경우(개념)
!! 리스트의 마지막 노드를 찾아야 함 !!

5) 리스트L의 마지막에 노드 x를 삽입하는 경우 (구현)

addLastNode(L, x)
	// 리스트 L의 끝에 원소 x를 삽입
    newNode <- getNode();	// x값을 가질, 새로운 노드 생성
    newNode.data <- x;
    newNode.link = null;
    
    if (L=null) then {	// L은 빈 리스트이므로, 만든 것을 최초 삽입
    	L <- newNode;
        return;
    }
    p <- L;	// p는 임시 순회 포인터로, L의 특정 위치를 찾는 용도로 사용
    
    while(p.link != null) do	// 루프 돌리며 L의 마지막 노드(null)를 찾음
    	p <- p.link;	// 다음 노드로 p 포인터를 옮기는 연산
        
    p.link <- newNode;	// 마지막 노드로 첨가
end addLastNode()

6) 리스트 L에서 p가 가리키는 노드의 다음 노드 q를 삭제

delete(L, p)
	// p가 가리키는 노드의 다음 노드를 삭제
    if (L=null) then error;	// L이 공백이면 에러
    if (p=null) then	// 가리키는 노드가 없으므로, L이 가리키는 것 삭제
    	q <- L;		// q가 삭제될 노드로 셋팅해야 함
    else {
    	q <- p.link;	// p 다음 노드를 q가 가리키도록 셋팅
        				// q는 삭제할 노드를 지시하고 있게 됨
        
        if(q=null) then return;	// 삭제할 노드가 없는 경우
        p.link <- q.link;	// 삭제 대상은 q에 맡기고, p는 전진함
    }
    returnNode(q);	// free(); 삭제한 노드를 자유 공간 리스트에 반환
end delete()

6) 리스트를 역순으로 만드는 알고리즘(개념)

L : lead -> 우측 List를 Leading

M: middle -> 좌측 List를 Leading

T: trail -> 리스트 생성을 돕는다.(reverse를 도움)

7) 리스트를 역순으로 만드는 알고리즘 구현

- 3개의 포인터를 이용하여 처리함: lead(가장 앞), middle(중간), trail(마지막에 따라감)

reverse(L)
	// L = (e1, e2, ... , en)을 L = (en, en-1, ... , e1)으로 변호나
    	// 순회 포인터로 lead, middle, trail을 사용한다.
    lead <- L;	// lead는 역순으로 변화시킬 리스트
    middle <- null;	// middle는 역순으로 변화될 노드
    
    while(lead != null) do {
    	trail <- middle; // trail은 역순으로 변화된 리스트
        				// trail은 middle을, middle은 lead를 차례로 따라간다.
        middle <- lead;	// middle이 현재 lead의 위치를 지킴
        lead <- lead.link;	// middle에게 맡기고, lead은 앞으로 전진함.
        middle.link <- trail;	// middle의 링크 방향을 역으로 바꾼다.
    }
    
    L <- middle;
end reverse()

8) 두 리스트를 연결하는 알고리즘

- 두 리스트 xlist과 ylist를 하나된 xlist로 만드는 알고리즘

addList(xlist, ylist)
	// xlist = (a1, a2, ... , an), ylist = (b1, b2, ... , bn)일 때,
    // NEW, list = (a1, a2, ... , an, b1, b2, ... , bm)을 생성
    
    case { // 둘 다 null일 때는?
    	xlist = null: return ylist;	//xlist가 null이므로, ylist를 반환하면 끝
        ylist = null: return xlist; //ylist가 null이므로, xlist를 반환하면 끝
        else: zlist <- xlist; // zlist는 순회 포인터
        	while(zlist.link != null) do
            	zlist <- zlist.link; // zlist 지칭 노드의 link가 null일 때까지 전진해가기(끝 노드 찾기)
            zlist.link <- ylist; // 찾았으면, 그 node의 null이었던 부분을 ylist에 연결
            return xlist;	// 최종적으로 완성된, xlist를 얻기
    }
    end addList()

9) 리스트 내 원소 값을 탐색하는 알고리즘

- 데이터 값이 x인 노드를 찾아 포인터를 반환하는 알고리즘

searchNode(L, x)
	p <- L;	// p는 받은 L을 따라가는 임시 순회 포인터로 선언
    
    while(p!=null) do {	// p가 끝이 아닐 때까지 계속 루프
    	if(p.data = x) then return p;	// p의 data 값이 "x"인 노드를 발견, 끝!
        p <- p.link;	// x 못 찾았으면, p 하나 전진
    }
    
    return p;	// 원소 값이 x인 노드가 없는 경우 null을 반환
    
end searchNode()

- 데이터 값이 x인 노드를 찾아 포인터를 반환하는 C 프로그램

10) 리스트의 마지막 노드를 삭제(개념)

- currentNode와 previousNode의 동작과정

1️⃣ currentNode 포인터는 삭제할 노드를 가리킴

2️⃣ currentNode 포인터는 전진, previousNode 포인터는 따라가면서 list keep함

3️⃣ currentNode 포인터가 어떤 노드를 가리키면 previousNode 포인터는 currentNode가 가리키는 노드의 바로 직전 노드를 가리키도록 함

4️⃣ currentNode가 currentNode -> link가 null인 것을 발견하면 마지막 노드임

5️⃣ 이것을 가리키게 될 때 previousNode는 마지막 두 번째 노드를 가리키게 됨

6️⃣ currentNode가 리스트의 마지막 노드를 삭제하면, previousNode가 마지막이 됨

11) 리스트의 마지막 노드를 삭제(구현)

void deleteLastNode(listNode* L){
	listNode* previous;	/* listNode에 대한 포인터 */
    listNOde* current;
    
    if(L == NULL) return;	// L이 empty list인 경우, 아무것도 하지 않음
    
    if(L->link == NULL) {	// L에 노드가 1개만 있는 경우
    	free(L);
        L = NULL;
    }
    else {					// L에 노드가 2개 이상 있는 경우
    	previous = L;		// 초기에 previous는 L의 1번째 노드를 지칭함
        current = L->link;	// 초기에 current는 L의 2번째 노드를 지칭함
        
        while(current->link != NULL) {	// current가 마지막 노드에 도달할 때까지 이동
        	previous = current;			// c 전진으로 노드를 잃지 않게, p가 list keep(백업)
            current = current -> link;	// 이제 c는 마음 놓고 전진 가능
        }
        free(current);	// c가 마지막 가리키고, 이제 이걸 없앰
        				// 그러므로, p가 지칭하는 것이 마지막이 됨
        previous->link = NULL;
        // 그러므로, 현재 p가 지시하는 노드에 null을 넣어 p를 마지막 노드를 만듦
    }
}

12) 연결 리스트의 출력(프린트)