자료구조 - 연결리스트의 응용

 

 

1. 연결 리스트의 변형

 

단순 연결 리스트는 링크가 하나만 있고, 각각의 노드는 후행 노드만을 가리키는 구조이다

특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 선행 노드는 헤드부터 재검색해야 한다.

 

→ (선행과 후행) 두개의 링크를 가지는 이중 연결 리스트가 등 - 장

 

2. 원형 연결 리스트

리스트의 마지막 원소의 링크는 null 이다 

마지막 원소의 링크를 첫번째 헤드로 연결시키게 되면 원형 연결 리스트가 된다

한방향으로 모든 노드가 연결되어 노드 간 접근성이 좋다

 

- 원형 연결 리스트의 생성

// 원형 연결리스트 노드 구조 정의
typedef struct ListNode {
    char int[10]; 	   // 숫자형 데이터 10개 정도의 공간을 할당받고
    struct ListNode* link; // 노드 구조의 자료형을 가진 링크를 선언
} listNode;

// 헤드 노드 구조 정의
typedef struct {
    listNode* head;
} linkedList_h;

// 원형 연결리스트 헤드 노드 생성
linkedList_h* createLinkedList_h(void){
    linkedList_h* H; // 헤드변수 H 선언
    H = (linkedList_h*)malloc(sizeof(linkedList_h)); // 메모리 할당하고
    H → head = NULL; // head 초기값 정의
    return H;
}

 

**ListNode 포인터는 노드 전체를 가리키는 포인터 변수이다

 

 

- 원형 연결 리스트의 첫번째 노드 삽입

원형 연결리스트의 첫번째에 노드 삽입을 한다. (삽입된 노드는 헤드가 된다)

→ 노드를 순회하면서 마지막 노드를 찾고, 거기에 추가할 노드 삽입을 한다. 그리고 삽입한 노드를 헤드로 임명한다

void addFirstNode(linkedList_h* H, int x) {
    // 준비물 - 템프노드, 새로 추가할 노드
    listNode* tempNode;
    listNode* newNode;

    // 뉴노드의 초기값 세팅
    NewNode = (listNode)malloc(sizeof(listNode)); // 리스트형으로 메모리 할당 후
    NewNode → data = x;    // 매개변수 받아온 x를 data 에 넣고
    NewNode → link = NULL; // link를 NULL 에 추가요

    // 헤드가 비어있는 경우 (그냥 뉴노드만 추가)
    if(H → head == NULL){
        H → head = NewNode; 	   // 헤드 포인터를 뉴노드로 지정하고
        NewNode → link = NewNode;  // 링크를 NewNode 로 해준다(원형이니까)
        return;
    }

    // 헤드값이 존재하면
    tempNode = H → head; //temp 를 헤드로 넣어주고

    // 헤드를 만나기 전까지 순회 (마지막 노드를 찾아야 하므로)
    while(tempNode → link != H → head) { // temp 의 다음 주소가 헤드가 아니면
        tempNode = tempNode → link;      // temp 자리에 다음 노드를 저장한다
    }

    // 템프 노드가 마지막 값이 될 때
    NewNode → link = tempNode → link; // 새로 추가할 노드의 링크를 temp 의 링크로 바꾸고
    tempNode → lnk = NewNode;  	      // temp의 링크를 새로 추가할 노드를 향하게 만든다
    H → head = NewNode; 	      // 헤드를 뉴노드로 변경한다
}

 

 

- 원형 연결 리스트의 중간 노드 삽입 

매개변수로 받은 이전 노드의 링크를 새로 추가할 노드로 변경해주면 된다 (주소이전)

// 매개변수로 헤드, 이전 노드, 추가할 데이터를 받는다 
void addMiddleNode(linkedList_h* H, listNode* prevNode, int itData) {

    // 새로 추가할 노드 세팅
    listNode* NewNode; // 선 - 언
    NewNode = (listNode*)malloc(sizeof(listNode)); // 할 - 당
    NewNode → data = itdata; // 데이터 저 - 장
    NewNode → link = NULL;   // 링크 너 - 얼

    // 이전 노드 뒤에 추가
    Newnode → link = prevNode → link; // 새로 추가할 노드의 링크 설정
    prevNode → link = NewNode; // 이전 노드의 다음을 NewNode로 변경
    return;
}

 

 

- 원형 연결 리스트의 노드 삭제

매개변수로 받은 (삭제할 노드의)이전 노드가 가리키는 값을 삭제할 노드가 가리키는 값으로 대체해줘서 

자연스럽게 삭제할 노드를 기억(memory)에서 지워버린다

// 매개변수로 헤드와 이전 노드를 받는다
void deleteCircularNode(linkedList_h* H, listNode* prevNode) {

    // 삭제할 노드 초기값 세팅
    listNode* delNode;
    delNode = prevNode → link;	      // 삭제할 노드는 prevNode가 향하는 노드이다 (바로 너너)
    prevNode → link = delNode → link; // prevNode의 링크는 삭제할 노드의 다음 순서를 가리킨다

    // 삭제할 노드가 헤드라면
    if(delNode == H → head) {
        H → head = delNode → link;    // 헤드는 삭제할 노드의 다음 값이 된다
    }

    free(delNode); // 이젠 삭제할 노드를 보내 주자
}

 

 

 

3. 이중 연결 리스트

기존 연결리스트는 단방향의 링크만 가지고 있다.

특히 포인터를 이용한 경우 다음 순서(후행) 노드는 알기 쉽지만 이전 순서(선행) 노드는 알기 어렵다

이중연결 리스트는 특정 노드의 선행 노드를 찾거나 리스트 원소들의 역순 검색을 쉽게 하기 위해 제안되었다

→ 한 노드가 { 왼쪽 포인터와 + 오른쪽 포인터 + 데이터 } 를 가진다 (헤드도 마찬가지)

 

- 이중 연결 리스트의 생성

// 노드 구조체 정의
typedef struct ListNode {
    struct ListNode* LeftLink; // 왼쪽링크
    int data[10]; // 그리고 데이터	 +
    struct ListNode* RightLink;// 오른쪽 링크
} listNode;

// 헤드 구조체 정의
typedef struct {
    listNode* LeftHead; // 역순검색을 위한 헤드
    listNode* RightHead;// 정방향 검색을 위한 헤드
} linkedList_h;

// 헤드 노드 생성
linkedList_h* createLinkedList_h(void) {
    // 헤드 선언 및 초기화
    linkedList_h* H; // H 라는 변수에 헤드 선언 
    H = (linkedList_h*)malloc(sizeof(linkedList_h)); // 요 값에 메모리 할당
    H → LeftHead = NULL; // 왼쪽 포인터 초기값 세 - 팅
    H → RightHead = NULL;// 오른쪽 포인터 초기값 세 - 팅
    return H;
}

 

 

 

- 이중 연결 리스트의 삽입

// 매개변수로 헤드, 이전 노드, 추가할 값을 받는다
void addDBLNode(linkedList_h* H, listNode* prevNode, int x){

	// 새로 추가할 노드 세팅
	listNode* NewNode; // 변수선언하고
    NewNode = (listNode*)malloc(sizeof(listNode)); // 메모리 할당
    NewNode → LeftLink = NULL; // 왼쪽 포인터 초기값 세팅
    NewNode → data =x; // 데이터 x 로 저장 
    NewNode → RightLink = NULL; // 오른쪽 포인터 초기값 세팅
    
	// 오른쪽(다음순서) 링크 수정 
    NewNode → RightLink = prevNode →  RightLink; // 새로 추가할 노드의 오른쪽 링크를 이전노드가 가리키는 오른쪽 링크로 교체
    prevNode → RightLink = NewNode; // 이전 노드의 오른쪽 링크(다음순서)를 뉴 노드로 변경한다

	// 왼쪽(이전순서) 링크 수정
    NewNode → LeftLink = prevNode; // 새로 추가할 노드의 왼쪽 링크를 이전노드로 변경 (이건 당연하지)
    NewNode → RightLink → LeftLink = NewNode; // 뉴노드의 오른쪽 링크(= 다음 순서노드)의 왼쪽 링크(이전순서)를 새로운 노드로 변경
}

 

 

 

- 이중 연결 리스트의 노드 삭제

삭제 연산은 스르륵 지우듯 연결고리를 하나씩 바꾸며 삭제한다

// 헤드와 삭제할 노드를 매개변수로 받는다
void deleteDBLNode(linkedList_h* H, listNode* delNode){
    // 삭제할 노드의 왼쪽(이전)노드의 다음 값을 = delNode의 오른쪽 링크(다음노드)로 변경
    delNode → LeftLink → RightLink = delNode → RightLink;

    // 삭제할 노드의 오른쪽(다음)노드의 이전 값을 = delNode의 왼쪽 링크(이전 노드)로 변경
    delNode → RightLink → LeftLink = delNode → LeftLink;
}