[자료구조] 원형연결리스트, 이중연결리스트

단순연결리스트 = 선형연결리스트 = 체인

• 각각의 노드가 하나의 포인터를 갖는 구조로 포인터는 다음 노드를 가리킨다. 
• 포인터를 이용해 순차탐색하므로 시간 복잡도는 O(n)
• 마지막 노드의 링크는 null로 표현
• 해싱 기법에서 오버 플로 처리시 체이닝 기법에서 이용된다.

연결리스트 삽입

void insert(listPointer *first, listPointer x)
{
    /*
    입력데이터가 10인 노드를 fisrt의 노드 뒤에 삽입
    */
    listPointer temp;
    MALLOC(temp, sizeof(*temp));
    temp -> data = 10;
    if (*first)
    {
    	temp->link = x->link;
        x->link = temp;
    }
    else 
    {
    	temp->link = NULL;
    	*first = temp;
    }
}

 

연결리스트 삭제

void delete(listPointer *first, listPointer trail, listPointer node)
{
    /* 
    리스트로부터 노드를 삭제.
    trail은 삭제될 x노드의 선행노드.
    first는 리스트 시작노드.
    */
    if (trail)
    {
    	trail->link = x->link;
    }
    else 
    {
    	*first = (*first)->link;
        free(x);
    }
}

연결리스트 역순만들기

listNode reverse(ListNode *head)
{
    //순회포인터 p, q, r;
    ListNode *p, *q, *r;
    
    p = head; // 역순으로 만들 리스트 
    q = null; // 역순으로 만들 노드
    while(p != null){
        r = q; // 역순으로 된 리스트
    	q = p; // r-q-p순으로 차례로 따라감
        p = p->link; // 다음노드
        q->link = r; // q의 링크 방향 변경
    }
    return q; // 역순으로 된 리스트의 헤드 포인터
}

---

 

원형연결리스트 = 단순연결원형리스트

• 단순연결리스트의 마지막노드가 null link를 갖는 대신에 리스트에서 처음 노드의 포인터를 갖도록 구성한 리스트
• 빠른 리스트의 반환을 위해 원형 리스트 사용 
• head 노드는 마지막 노드를 가르키는데, 리스트 길이에 상관없이 첫번째 노드앞이나 마지막노드뒤에 일정한 시간으로 노드를 삽입 할 수 있음
• 원형이기때문에 어느 한 노드로부터 다른 모든노드에 접근 가능

 

 

원형 연결리스트 노드 삽입 (1) 앞에 노드 삽입

void insertFront(listPointer last, listPointer node)
{
    /* 리스트의 마지막 노드가 last인 원형리스트의 앞에 노드를 삽입 */
   if(!(*last)) // 리스트가 공백일 경우, last가 새로운 노드를 가리키도록 변경
   {
       *last = node;
       node->link = node;
   }
   else { // 리스트가 공백이 아닐 경우, 리스트 앞에 노드 삽입
       node->link = (*last)->link;
       (*last)->link = node;
   }
}

 

원형 연결리스트 노드 삽입 (2) 뒤에 노드 삽입

void insertTrail(listPointer last, listPointer node)
{
    // 리스트의 마지막 노드가 last인 원형리스트에 뒤에 노드 삽입
    if(!last){
        // 리스트가 비었을 경우, last가 새로운 노드 가리키도록 변경
        last = node;
        node->link = node
    } 
    else {
        // 리스트가 공백이 아닌 경우 리스트 뒤애 노드 삽입
        node->link = last->link;
        last->link = node;
        last = node;
    }
}

 

원형 연결리스트 노드 전체 삭제

void erase(pointer ptr)
{
    // ptr이 가리키는 원형 리스트 삭제
    pointer temp;
    if(ptr){
        temp = ptr->link;  // 포인터가 가리키는 리스트 링크 저장
        prt->link = avail; // 링크 변경 빈 리스트 가리킴
        avail = temp;
        ptr = null; // 포인터 Null 처리
    }
}

 

원형 연결리스트 길이 계산

int length (listPointer last)
{
    //원형 리스트의 last 길이를 계산
    listPointer temp;
    int count = 0;
    if(last) {
       temp = last;
       do {
           count++;
           temp = temp->temp;
       } while(temp!=last); // 마지막 노드에서 시작해서 다시 마지막노드일때까지 카운트
   }
   return count;
}

---

 

이중연결리스트

• 원형리스트가 뒤로 순회할 수없다는 점과 삭제하고자 하는 노드에 대해 포인터만으로 삭제가 불가능한 점을 보완
• 노드에 대해 다음 노드, 이전 노드 모두 알 수 있도록 하여 한 가지 방향이 아닌 양쪽 방향의 탐색이 가능하게 구성한 것 
• 각 노드에 왼쪽, 오른쪽 2개의 포인터가 있음, 각 포인터는 좌우 노드를 가리키는 구조. -> 두 개의 링크 보관으로 기억공간 낭비
• 양방향 검색 가능하므로 속도 빠르고 선행노드 검색 쉬움. 리스트 운행에 따른 알고리즘 간단 
• 한 노드의 포인터가 파괴되었을 때 복구 가능
• 운영체제 동적 메모리 관리에 가장 적합
• 임의의 노드 x 가 있으면 x = RLLINK(LLINK(x)) = LLINK(RLINK(x))

 

이중연결리스트 노드 삽입

// 오른쪽 노트 삽입
void insert(head, item, x)
{
    // x노드는 삽입노드 y의 선행노드 
    call getnode(Y)
    data(y) <- item
    if (head==null)
    	head = Y
        y->rlink = null;
        y->llink = null;
    else
    	y->rlink = x->rlink // 1
        y->llink = x // 2 
        x->rlink->llink = y // 3
        x->rlink = y // 이 과정은 앞에 1,3보다 뒤에 이뤄져야함 
}

// 왼쪽 노드 삽입
void insert(head, item, x)
{
    // x노드는 삽입노드 y의 선행노드 
    call getnode(Y)
    data(y) <- item
    if (head==null)
    	head = Y
        y->rlink = null;
        y->llink = null;
    else
    	y->llink = x->llink // 1
        y->rlink = x // 2 
        x->llink->rlink = y // 3
        x->llink = y // 이 과정은 앞에 1,3보다 뒤에 이뤄져야함 
}

 

 

이중연결리스트 노드 삭제

void delete(nodePointer node, nodePointer deleted)
{
    //이중연결리스트에서 삭제
    if (node == deleted){
        print("이미 삭제 완료");
    }
    else{
        //왼쪽노드(삭제 노드의 선행노드)의 링크제거
        deleted->llink->rlink = deleted->rlink;
        //오른쪽노드(삭제 노드의 후행노드)의 링크제거
        deleted->rlink->llink = deleted->llink;
        free(deleted); //메모리할당해제
    }
}

 

head 노드 : 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드. 헤드 포인터와 구별하기!!!

공백상태에서는 헤드노드만 존재한다. 

• 헤드노드에는 첫 번째 노드 포인터, 리스트 길이, 참조계수(자신을 참조하고 있는 포인터수), 마지막노드 포인터를 주로 포함하고 있다.

---

참조

https://slidesplayer.org/slide/17833747/