[Data Structures & Algorithms] 원형 연결 리스트와 이중 연결 리스트 (원형 연결 리스트 & 이중 연결 리스트의 연산 알고리즘)

🎪 원형 연결 리스트란?

단순 연결 리스트에서 마지막 노드가 리스트의 첫 번재 노드를 가리키게 하여 구조를 원형으로 설정한 리스트를 원형 연결 리스트라고 한다.

단순 연결 리스트이 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여, 링크를 따라 반복 순회할 시 이전 노드에 접근할 수 있다.

 

---

 

❤️ 원형 연결 리스트 알고리즘_ 1) 삽입 연산

① 첫 번째 노드로 삽입하기

insertFirstNode(CL, x)

    new <- getNode(); //메모리 할당
    new.data <- x; //값 지정
    
    if (CL = NULL) //공백 리스트인 경우
    {
        CL <- new; //포인터 CL이 new를 가리키게 설정
        new.link <- new; //new가 자기 자신을 가리키게 설정 (원형 연결 리스트니까)
    }
    else //공백 리스트가 아닌 경우
    {
        temp <- CL; //첫 번째 노드 주소를 임시 순회 포인터 temp에 저장
        
        while (temp.link != CL) //마지막 노드까지 반복문 수행하며 이동
        {
            temp <- temp.link;
        }
        
        new.link <- temp.link; //마지막 노드의 링크값을 new의 링크에 저장
        temp.link <- new; //포인터 new 값을 포인터 temp가 가리키고 있는 마지막 노드의 링크에 저장
        CL <- new; //노드 new값을 리스트 포인터 CL에 저장
    }
    
end insertFirstNode()

 

 

② 중간 노드로 삽입하기

insertMiddleNode(CL, pre, x)

    new <- getNode(); //메모리 할당
    new.data <- x; //값 지정
    
    if(CL = NULL) //공백 리스트인 경우
    {
        CL <- new; //새 노드 주소를 리스트 포인터에 저장
        new.link <- new; //마지막 노드의 링크 필드에 new값 저장
    }
    else //공백 리스트가 아닌 경우
    {
        new.link <- pre.link; //노드 pre의 다음 노드를 new의 다음 노드로 연결
        pre.link <- new; //삽입할 노드 주소를 노드 pre의 링크에 저장
    }
    
end insertMiddleNode()

 

---

 

❤️ 원형 연결 리스트 알고리즘_ 2) 삭제 연산

deleteNode(CL, pre)

    if (CL == NULL) then error; //공백 리스트인 경우 오류 처리
    else //공백 리스트가 아닌 경우
    {
        old <- pre.link; //pre의 다음 노드 주소를 삭제할 노드 old로 지정
        pre.link <- old.link; //old의 다음 노드를 old의 이전 노드와 연결
        
        if (old == CL) //삭제할 노드가 리스트의 첫 번째 노드인 경우
        {
            CL <- old.link; //노드 old의 링크값을 리스트 포인터(CL)에 저장
        }
        
        returnNode(old); //삭제한 노드 old의 메모리 반환
    }
    
end deleteNode()

 

---

 

🎪 이중 연결 리스트란?

 

위 그림과 같이 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트를 이중 연결 리스트라고 한다.

 

이중 연결 리스트의 노드 구조
llink (Left Link) 필드	rlink (Right link) 필드
좌측 노드와 연결하는 포인터	우측 노드와 연결하는 포인터

 

---

 

❤️ 이중 연결 리스트의 구조체 정의

typedef struct Dnode
{
    struct Dnode *llink;
    char data[5];
    struct Dnode *rlink;
}

 

---

 

❤️ 이중 연결 리스트 알고리즘_ 1) 삽입 연산

① 삽입할 노드 준비  ==  메모리 할당
② 새 노드의 데이터 필드에 값 저장  ==  값 지정
③ 새 노드 기준 좌측 노드의 rlink 에 있던 값을 새 노드의 rlink 에 저장
④ 좌측 노드의 rlink에 새 노드의 주소 저장
⑤ 새 노드 기준 오른쪽 노드의 llink에 있던 값을 새 노드의 rlink 에 저장
⑥ 우측 노드의 llink 에 새 노드의 주소 저장
⑦ 노드를 순서대로 연결

 

① 데이터 필드값이 x인 노드 new를 포인터 pre가 가리키는 노드의 다음 노드로 삽입하는 연산

insertNode(DL, pre, x)

    new <- getNode();
    new.data <- x;
    
    new.rlink <- pre.rlink;
    pre.rlink <- new;
    new.llink <- pre;
    new.rlink.llink <- new;
    
end insertNode()

 

---

 

❤️ 이중 연결 리스트 알고리즘_ 2) 삭제 연산

① 삭제할 노드의 우측 노드와 좌측 노드를 각각 찾기
② 삭제할 노드의 우쪽 노드 주소를 삭제할 노드 기준 좌측 노드의 rlink에 저장
③ 삭제할 노드의 왼쪽 노드의 주소를 삭제할 노드 기준 우측 노드의 llink에 저장
④ 노드를 순서대로 연결

 

deleteNode(DL, old)

    old.llink.rlink <- old.rlink;
    old.rlink.llink <- old.llink;
    
    returnNode(old);

end deleteNode()