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

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

1) 리스트 생성 알고리즘

// 점 표기식만으로 리스트를 작성한 경우
L <- getNode(); // program에서는 "<-"이라는 표현은 "="와 같음
L.data <- "Cho"; // program에서는 strcpy((*L).data, "Cho");로 작성
L.link <- getNode(); // 왼쪽 표현은 알고리즘 표현임
L.link.data <- "Kim";
L.link.link <- null;

 

 

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

// 리스트 L의 첫 번째 노드로 data 값이 x인 노드를 삽입
addFirstNode(L, x)
	// 리스트 L의 첫 번째 노드로 원소 x를 삽입
    newNode <- getNode();	// (1) newNode = malloc(sizeof(node));를 표현함
    newNode.data <- y;		// (2) newNode.data = y; "y"라는 값을 넣음
    enwNode.link <- L;		// (3) old List의 주소는 L이 가지고 있었음
    L <- newNode;			// newNode가 L의 새로운 시작 노드가 됨
end addFirstNode()

 

 

 

3) 원소 값이 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를 삽입하는 경우 (개념)

(1) while(p.link != null) do // 리스트의 마지막 노드를 찾음
		p <- p.link;
        
(2) p.link <- newNode; // 마지막 노드로 첨가

 

 

 

 

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;
    if(p = null) then
    	q <- L;
    else {
        q <- p.link;
        
        if(q = null) then return;
        p.link <- q.link;
    }
    returnNode(q);
end delete()